4 ms·
Distributed Consensus: Beating Impossibility with Probability One
- ComSubVie 13y agoThat's quite an interesting algorithm, especially the random selection part. I'd really like to read the original paper! I found a correctness-proof which includes peseudo-code in the papers "Correctness Proof of Ben-Or’s Randomized Consensus Algorithm"[1] and "The correctness proof of Ben-Or’s randomized consensus algorithm"[2]. [1] http://ecommons.cornell.edu/bitstream/1813/7336/1/98-1682.pdf http://ecommons.cornell.edu/bitstream/1813/7336/1/98-1682.pd... [2] http://www.cs.toronto.edu/~samvas/teaching/2221/handouts/benor-paper.pdf http://www.cs.toronto.edu/~samvas/teaching/2221/handouts/ben...
- fintler 13y agoA few links to the paper the author couldn't find: http://www.disi.unitn.it/~montreso/ds/papers/p27-ben-or.pdf http://www.disi.unitn.it/~montreso/ds/papers/p27-ben-or.pdf http://bayfiles.net/file/13Oqj/1Q46fJ/p27-ben-or.pdf http://bayfiles.net/file/13Oqj/1Q46fJ/p27-ben-or.pdf https://mega.co.nz/#!VU4nWbDK!NcqVDGI6iuE-EJ07sB9glV_UEPFlMVuYJ9G30c2JO04 https://mega.co.nz/#!VU4nWbDK!NcqVDGI6iuE-EJ07sB9glV_UEPFlMV... This entire concept has blown my mind. One of my basic assumptions of how consensus works was completely wrong.