3 ms·

(Before you down vote: I have a PhD in distributed systems and fault tolerance. Okay, now you can down vote for the duchebaggery of this prescript) I think a f

(Before you down vote: I have a PhD in distributed systems and fault tolerance. Okay, now you can down vote for the duchebaggery of this prescript) I think a fundamental and very underrated paper and concept (which actually predates Paxos, yet Lamport ignored or was unaware of) is the notion of randomized consensus protocols. Simpler than "structured" leader type algorithms. Believe Ben Or's algorithm was first.

athenot 10y ago
An illustration is bees vs. flies. A bee trapped indoors will go for the sun: a great algorithm for a forest/thicket but fatal in a house or car with windows. A fly will randmly try until it succeeds, meaning it is slower at escaping a thicket but will eventually find the open door even if it's opposite from the window.
mjb 10y ago
> Believe Ben Or's algorithm was first. 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.
- einarvollset 10y ago
  I disagree - an ex-colleague at Cornell wrote a paper proving equivalence. Will have to dig that up..
elviejo 10y ago
Where did You study your degree? I would be intereses in doing one.

athenot 10y ago

An illustration is bees vs. flies. A bee trapped indoors will go for the sun: a great algorithm for a forest/thicket but fatal in a house or car with windows. A fly will randmly try until it succeeds, meaning it is slower at escaping a thicket but will eventually find the open door even if it's opposite from the window.

mjb 10y ago

> Believe Ben Or's algorithm was first. 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.

einarvollset 10y ago
I disagree - an ex-colleague at Cornell wrote a paper proving equivalence. Will have to dig that up..

elviejo 10y ago

Where did You study your degree? I would be intereses in doing one.