%0 Journal Article %1 ling2006randomized %A Cheung, Ling %D 2006 %J Principles of Distributed Systems %K consensus modelchecking randomized sharedmemory %P 47--60 %T Randomized Wait-Free Consensus Using an Atomicity Assumption %U http://dx.doi.org/10.1007/11795490_6 %X We present a randomized algorithm for asynchronous wait-free consensus using multi-writer multi-reader shared registers. This algorithm is based on earlier work by Chor, Israeli and Li (CIL) and is correct under the assumption that processes can performa random choice and a write operation in one atomic step. The expected total work for our algorithm is shown to be O(N log(logN)), compared with O(N2) for the CIL algorithm, and O(N logN) for the best known weak adversary algorithm. We also model check instances of our algorithm using the probabilistic modelchecking tool PRISM.

@article{ling2006randomized, abstract = {We present a randomized algorithm for asynchronous wait-free consensus using multi-writer multi-reader shared registers. This algorithm is based on earlier work by Chor, Israeli and Li (CIL) and is correct under the assumption that processes can performa random choice and a write operation in one atomic step. The expected total work for our algorithm is shown to be O(N log(logN)), compared with O(N2) for the CIL algorithm, and O(N logN) for the best known weak adversary algorithm. We also model check instances of our algorithm using the probabilistic modelchecking tool PRISM.}, added-at = {2009-11-16T10:49:38.000+0100}, author = {Cheung, Ling}, biburl = {https://www.bibsonomy.org/bibtex/22c392c071688b7b7c928a78347a2a421/giuliano.losa}, description = {Randomized Wait-Free Consensus Using an Atomicity Assumption}, interhash = {db6e5b15e31fe8f383bb8f98c13f9614}, intrahash = {2c392c071688b7b7c928a78347a2a421}, journal = {Principles of Distributed Systems}, keywords = {consensus modelchecking randomized sharedmemory}, pages = {47--60}, timestamp = {2009-11-16T10:49:38.000+0100}, title = {Randomized Wait-Free Consensus Using an Atomicity Assumption}, url = {http://dx.doi.org/10.1007/11795490_6}, year = 2006 }