Ben-Or's "Another Advantage of Free Choice" beat Rabin's "Randomized Byzantine Generals" 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's case, a random oracle) makes the consensus problem possible again.
I wouldn't say that these algorithms were really ignored by Lamport when he wrote the Paxos paper. Again, they're solving a different problem in a different system model. If you want to pick on Lamport, talk about Liskov's Viewstamped Replication.
If anybody has a digital copy of Ben-Or's paper that isn'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.
Ben-Or's "Another Advantage of Free Choice" beat Rabin's "Randomized Byzantine Generals" 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's case, a random oracle) makes the consensus problem possible again.
I wouldn't say that these algorithms were really ignored by Lamport when he wrote the Paxos paper. Again, they're solving a different problem in a different system model. If you want to pick on Lamport, talk about Liskov's Viewstamped Replication.
If anybody has a digital copy of Ben-Or's paper that isn'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.