&gt; Believe Ben Or&#x27;s algorithm was first.<p>Ben-Or&#x27;s &quot;Another Advantage of Free Choice&quot; beat Rabin&#x27;s &quot;Randomized Byzantine Generals&quot; by a couple of months in 1983. These algorithms show how much people over-extend results like FLP. The result is about a very particular system model, and the addition of even a very tiny extra piece (in Ben-Or&#x27;s case, a random oracle) makes the consensus problem possible again.<p>I wouldn&#x27;t say that these algorithms were really ignored by Lamport when he wrote the Paxos paper. Again, they&#x27;re solving a different problem in a different system model. If you want to pick on Lamport, talk about Liskov&#x27;s Viewstamped Replication.<p>If anybody has a digital copy of Ben-Or&#x27;s paper that isn&#x27;t partially cut off, please make it available. Both the copy in the ACM library and the only copy the author himself has are missing some of the right hand side.