Robert Shostak

Robert Eliot Shostak (born July 26, 1948, in Arlington, Virginia) is an American computer scientist and Silicon Valley entrepreneur.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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. 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.

Reception

Shostak received the Thoralf Skolem Award for "Deciding Combinations of Theories" Shostak is a brother of Seth Shostak, who is Senior Astronomer at the SETI Institute and who frequently appears on television and radio. 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.

Career

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.

Works

The collective results were published in 19791 in the seminal paper, Reaching Agreement in the Presence of Faults, which was awarded the 2005 Edsger W. Dijkstra Prize in Distributed Computing, as well as the 2013 Jean-Claude Laprie Award The same authors helped to popularize the interactive consistency problem in their 1982 paper, The Byzantine Generals Problem, 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. Blockchains underpin the integrity of cryptocurrencies such as Bitcoin.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1372613566 under CC BY-SA 4.0; modifications have been made.

References

1 claim could not be tied to a specific sentence and is listed in the table below instead.

  1. ↩Wikipedia “Robert Shostak” revision 1372613566 · retrieved 2026-10-20 publication date (×1) · confidence 0.95 revision URL