Robert Shostak

Last updated
Robert E. Shostak
Robert-shostak-2019-thumbnail.jpg
Born (1948-07-26) July 26, 1948 (age 75)
Arlington County, Virginia
Nationality American
Citizenship United States
Alma materA.B., A.M., Ph.D. Harvard
Known for
Awards
Scientific career
Fields Computer Science

Robert Eliot Shostak (born July 26, 1948, in Arlington, Virginia) is an American computer scientist and Silicon Valley entrepreneur. He is most noted academically for his seminal work in the branch of distributed computing known as Byzantine Fault Tolerance. He is also known for co-authoring the Paradox Database, and most recently, the founding of Vocera Communications, a company that makes wearable, Star Trek-like communication badges.

Contents

Shostak has authored more than forty academic papers and patents, and was editor of the 7th Conference on Automated Deduction. He has Erdős number 2 through his collaboration with Kenneth Kunen. [1] Shostak received the Thoralf Skolem Award for "Deciding Combinations of Theories" [2]

Shostak is a brother of Seth Shostak, who is Senior Astronomer at the SETI Institute and who frequently appears on television and radio.

Education

Robert Shostak was born in Arlington, Virginia, the son of Arthur and Bertha Shostak (née Gortenburg); his father was an electrical engineer. [3] He studied mathematics and computer science at Harvard College, graduating in 1970 with high honors. As part of his senior dissertation work, he designed and built one of the earliest personal computers using discrete RTL logic (microprocessors were not yet available) and a magnetic core memory. [4] He continued at Harvard to earn his A.M. degree and Ph.D. in Computer Science in 1974. While at Harvard he was awarded the Detur Book Prize, and fellowships from IBM and the National Science Foundation.

Career

Afterwards, Shostak joined the research staff in the Computer Science Lab (CSL) at SRI International (formerly the Stanford Research Institute) in Menlo Park, California. Much of his work there focused on automated theorem proving, and specifically on the development of decision procedure algorithms [5] [6] [7] [8] [9] for mechanized proof of the kinds of mathematical formulas that occur frequently in the formal verification of correctness of computer programs. [10]

In collaboration with CSL's Richard L. Schwartz and P. Michael Melliar-Smith, Shostak implemented a semi-automatic theorem prover incorporating some of these decision procedures. [11] The prover was used to verify correctness properties of an abstract specification of the SIFT (for Software Implemented Fault Tolerance) operating system and was later incorporated into SRIís Prototype Verification System. The work was published in the paper, SIFT: Design and analysis of a fault-tolerant computer for aircraft control [12] This paper was awarded the 2014 Jean-Claude Laprie Award in Dependable Computing [13] established by the IFIP Subgroup 10.4 on Dependable Computing.

Interactive Consistency and Byzantine Fault Tolerance

Perhaps Shostak's most notable academic contribution is to have originated the branch of distributed computing known as Byzantine fault tolerance, also called interactive consistency.

This work was also conducted in connection with the SIFT project at SRI. SIFT was conceived by John H. Wensley, who proposed using a network of general-purpose computers to reliably control an aircraft even if some of those computers were faulty. The computers would exchange messages as to the current time and state of the aircraft (each would have its own sensors and clock), and would thereby reach a consensus.

At the outset, it was unknown how many computers would be necessary to reach consensus if some n of them were faulty, and possibly acting in a 'malicious' manner to thwart consensus. Shostak formalized the problem mathematically and proved that for n faulty computers, no fewer than 3n+1 computers in total were needed for any algorithm that could guarantee consensus, or what he termed interactive consistency. He also devised an algorithm for n = 1, proving that four computers were sufficient using two rounds of message passing. His colleague Marshall Pease then generalized the result by constructing an algorithm for 3n+1 computers that works for all n > 0, thus showing that 3n+1 are sufficient as well as necessary.

Leslie Lamport later joined the CSL, and showed that if messages could be digitally signed, then only 3n are needed.

The collective results were published in 1979 in the seminal paper, Reaching Agreement in the Presence of Faults, [14] which was awarded the 2005 Edsger W. Dijkstra Prize in Distributed Computing, as well as the 2013 Jean-Claude Laprie Award [13]

The same authors helped to popularize the interactive consistency problem in their 1982 paper, The Byzantine Generals Problem, [15] which presents it in the form of a colorful allegory proposed by Lamport. In the allegory, the computers are replaced by Byzantine generals who needed to coordinate the timing of an attack on an enemy by exchanging messages borne by couriers. (The original formulation incorporated Albanian rather than Byzantine generals, but Jack Goldberg, the head of CSL, suggested that this might be interpreted as what might now be called cultural appropriation, hence the name was changed to Byzantine on the theory that this might be less likely to cause offense.)

The work on Byzantine agreement has spawned an entire sub-field of distributed computing with hundreds of published papers exploring extensions and applications of the original results. One of the most interesting of these is in the implementation of blockchains, in which interactive consistency is sought among a distributed network of computers. [16] Blockchains underpin the integrity of cryptocurrencies such as Bitcoin.

Entrepreneurial ventures

In 1984, Shostak and his colleague Richard Schwartz founded a Silicon Valley start-up company called Ansa Software. The company was financed by Ben Rosen of Sevin Rosen. Its product, a PC database called Paradox, was launched in 1985, and was among the first database products to run on IBM personal computers. Its user interface was based on Query by Example, a graphical method of formulating queries that had been conceived by Moshe Zloof at the IBM Watson Research Center. In September, 1987, Ansa Software was purchased by Borland International, which subsequently launched multiple Windows versions. A community of users still exists after more than thirty years. As of this writing, a third-party DOS version is still available for 64-bit Windows.

Shostak is also founder of Vocera Communications, which he started in March, 2000. The product, which facilitates hands-free communication among members of teams in hospitals and other enterprises, features wearable, speech-enabled badges much like Star Trek Communication Badges. [17] The company went public in 2012 (NYSE:VCRA) [18] and has a market capitalization of close to $1B as of this writing. Shostak served as CTO and chief architect until he retired in 2013, and was a board member until the company IPO.

Selected patents

Related Research Articles

<span class="mw-page-title-main">Leslie Lamport</span> American computer scientist and mathematician

Leslie B. Lamport is an American computer scientist and mathematician. Lamport is best known for his seminal work in distributed systems, and as the initial developer of the document preparation system LaTeX and the author of its first manual.

Self-stabilization is a concept of fault-tolerance in distributed systems. Given any initial state, a self-stabilizing distributed system will end up in a correct state in a finite number of execution steps.

<span class="mw-page-title-main">Concurrency (computer science)</span> Ability to execute a task in a non-serial manner

In computer science, concurrency is the ability of different parts or units of a program, algorithm, or problem to be executed out-of-order or in partial order, without affecting the outcome. This allows for parallel execution of the concurrent units, which can significantly improve overall speed of the execution in multi-processor and multi-core systems. In more technical terms, concurrency refers to the decomposability of a program, algorithm, or problem into order-independent or partially-ordered components or units of computation.

A Byzantine fault is a condition of a computer system, particularly distributed computing systems, where components may fail and there is imperfect information on whether a component has failed. The term takes its name from an allegory, the "Byzantine generals problem", developed to describe a situation in which, to avoid catastrophic failure of the system, the system's actors must agree on a concerted strategy, but some of these actors are unreliable.

<span class="mw-page-title-main">Barbara Liskov</span> American computer scientist

Barbara Liskov is an American computer scientist who has made pioneering contributions to programming languages and distributed computing. Her notable work includes the introduction of abstract data types and the accompanying principle of data abstraction, along with the Liskov substitution principle, which applies these ideas to object-oriented programming, subtyping, and inheritance. Her work was recognized with the 2008 Turing Award, the highest distinction in computer science.

A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes. This often requires coordinating processes to reach consensus, or agree on some data value that is needed during computation. Example applications of consensus include agreeing on what transactions to commit to a database in which order, state machine replication, and atomic broadcasts. Real-world applications often requiring consensus include cloud computing, clock synchronization, PageRank, opinion formation, smart power grids, state estimation, control of UAVs, load balancing, blockchain, and others.

In computer science, state machine replication (SMR) or state machine approach is a general method for implementing a fault-tolerant service by replicating servers and coordinating client interactions with server replicas. The approach also provides a framework for understanding and designing replication management protocols.

David Reeves Boggs was an American electrical and radio engineer who developed early prototypes of Internet protocols, file servers, gateways, network interface cards and, along with Robert Metcalfe and others, co-invented Ethernet, the most popular family of technologies for local area computer networks.

<span class="mw-page-title-main">Fingerprint (computing)</span> Digital identifier derived from the data by an algorithm

In computer science, a fingerprinting algorithm is a procedure that maps an arbitrarily large data item to a much shorter bit string, its fingerprint, that uniquely identifies the original data for all practical purposes just as human fingerprints uniquely identify people for practical purposes. This fingerprint may be used for data deduplication purposes. This is also referred to as file fingerprinting, data fingerprinting, or structured data fingerprinting.

Byzantine fault tolerant protocols are algorithms that are robust to arbitrary types of failures in distributed algorithms. The Byzantine agreement protocol is an essential part of this task. The constant-time quantum version of the Byzantine protocol, is described below.

The Brooks–Iyengar algorithm or FuseCPA Algorithm or Brooks–Iyengar hybrid algorithm is a distributed algorithm that improves both the precision and accuracy of the interval measurements taken by a distributed sensor network, even in the presence of faulty sensors. The sensor network does this by exchanging the measured value and accuracy value at every node with every other node, and computes the accuracy range and a measured value for the whole network from all of the values collected. Even if some of the data from some of the sensors is faulty, the sensor network will not malfunction. The algorithm is fault-tolerant and distributed. It could also be used as a sensor fusion method. The precision and accuracy bound of this algorithm have been proved in 2016.

A distributed operating system is system software over a collection of independent software, networked, communicating, and physically separate computational nodes. They handle jobs which are serviced by multiple CPUs. Each individual node holds a specific software subset of the global aggregate operating system. Each subset is a composite of two distinct service provisioners. The first is a ubiquitous minimal kernel, or microkernel, that directly controls that node's hardware. Second is a higher-level collection of system management components that coordinate the node's individual and collaborative activities. These components abstract microkernel functions and support user applications.

<span class="mw-page-title-main">Brendan Gregg</span> Australian computer scientist

Brendan Gregg is a computer engineer known for his work on computing performance. He works for Intel, and previously worked at Netflix, Sun Microsystems, Oracle Corporation, and Joyent. He was born in Newcastle, New South Wales and graduated from the University of Newcastle, Australia.

Daniel (Danny) Dolev is an Israeli computer scientist known for his research in cryptography and distributed computing. He holds the Berthold Badler Chair in Computer Science at the Hebrew University of Jerusalem and is a member of the scientific council of the European Research Council.

Susan Owicki is a computer scientist, Association for Computing Machinery (ACM) Fellow, and one of the founding members of the Systers mailing list for women in computing. She changed careers in the early 2000s and became a licensed marriage and family therapist.

Patrick Denis Lincoln is an American computer scientist leading the Computer Science Laboratory (CSL) at SRI International. Educated at MIT and then Stanford, he joined SRI in 1989 and became director of the CSL around 1998. He previously held positions with ETA Systems, Los Alamos National Laboratory, and MCC.

Massachusetts Computer Associates, also known as COMPASS, was a software company founded by Thomas Edward Cheatham Jr. and based in Wakefield, Massachusetts from approximately 1961 to 1991, focusing primarily on programming language design and implementation, especially source-to-source transformation. It was acquired in the late 1960s by Applied Data Research.

<span class="mw-page-title-main">Transition (computer science)</span>

Transition refers to a computer science paradigm in the context of communication systems which describes the change of communication mechanisms, i.e., functions of a communication system, in particular, service and protocol components. In a transition, communication mechanisms within a system are replaced by functionally comparable mechanisms with the aim to ensure the highest possible quality, e.g., as captured by the quality of service.

References

  1. ↑ W. W. Bledsoe; Kenneth Kunen; Robert E. Shostak (1985). "Completeness Results for Inequality Provers". Artificial Intelligence. 27 (3): 255–288. doi:10.1016/0004-3702(85)90015-3.
  2. ↑ "Skolem Award". cadeinc.org. Retrieved 2023-12-06.
  3. ↑ "1950 United States Federal Census". Ancestry.com. Retrieved 12 July 2022.
  4. ↑ Shostak, Robert (1970). "SIC: a small inexpensive digital Computer".
  5. ↑ Robert E. Shostak (1977). "On the SUP-INF Method for Proving Presburger Formulas". Journal of the ACM. 24 (4): 529–543. doi: 10.1145/322033.322034 . S2CID   16778115.
  6. ↑ Robert E. Shostak (1978). "An Algorithm for Reasoning About Equality". Communications of the ACM. 21 (7): 583–585. doi: 10.1145/359545.359570 . S2CID   1036470.
  7. ↑ Robert E. Shostak (1979). "A Practical Decision Procedure for Arithmetic with Function Symbols". Journal of the ACM. 26 (2): 351–360. doi: 10.1145/322123.322137 . S2CID   13502248.
  8. ↑ Robert E. Shostak (1981). "Deciding Linear Inequalities by Computing Loop Residues". Journal of the ACM. 28 (4): 351–360.
  9. ↑ Robert E. Shostak (1984). "Deciding Combinations of Theories". Journal of the ACM. 31 (1): 1–12. doi: 10.1145/2422.322411 . S2CID   5541114.
  10. ↑ A., MacKenzie, Donald (2001). Mechanizing proof : computing, risk, and trust. Cambridge, Mass.: MIT Press. pp.  268–272. ISBN   978-0262133937. OCLC   45835532.{{cite book}}: CS1 maint: multiple names: authors list (link)
  11. ↑ Shostak, Robert E.; Shostak, Richard L.; Melliar-Smith, P. Michael (1982). Loveland, Donald (ed.). STP: A Mechanized Logic for Specification and Verifications. Lecture Notes in Computer Science. Vol. 138. Springer, Berlin, Heidelberg. pp. 32–49. doi:10.1007/BFb0000050. ISBN   3-540-11558-7.{{cite book}}: |journal= ignored (help)
  12. ↑ Wensley, John H.; Lamport, L.; Goldberg, J.; Green, M. W.; Levitt, K. N.; Melliar-Smith, P. M.; Shostak, R. E; Weinstock, C. B. (October 1978). "SIFT: Design and analysis of a fault-tolerant computer for aircraft control". Proceedings of the IEEE. 66 (10): 1240–1255. doi:10.1109/PROC.1978.11114. S2CID   4020660.
  13. 1 2 "The Jean-Claude Laprie Award". jclaprie-award.dependability.org. Retrieved 2019-02-21.
  14. ↑ M. Pease; R. Shostak; L. Lamport (1979). "Reaching Agreement in the Presence of Faults". Journal of the ACM. 27 (2): 228–234. CiteSeerX   10.1.1.68.4044 . doi:10.1145/322186.322188. S2CID   6429068.
  15. ↑ L. Lamport; R. Shostak; M. Pease (1982). "The Byzantine Generals Problem". ACM Transactions on Programming Languages and Systems. 4 (1): 382–401. CiteSeerX   10.1.1.64.2312 . doi:10.1145/357172.357176. S2CID   55899582.
  16. ↑ Imran, Bashir (2017-03-17). Mastering blockchain : distributed ledgers, decentralization and smart contracts explained. Birmingham, UK. pp. 12, 30. ISBN   9781787129290. OCLC   981928401.{{cite book}}: CS1 maint: location missing publisher (link)
  17. ↑ Hesseldahl, Arik (March 16, 2004). "Your Trekkie Communicator is Ready". Forbes Magazine.
  18. ↑ Gallagher, Dan (March 28, 2012). "Vocera Communications jumps on IPO debut". MarketWatch.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.