Tools Overview Contact Us Publications Case Studies Manual Home


[AspnesH90] Aspnes, J. and Herlihy, M. Fast randomized consensus using shared memory. In Journal of Algorithms, 11: 441-461, 1990.
Downloads: bibAbstract. We give a new randomized algorithm for achieving consensus among asynchronous processes that communicate by reading and writing shared registers. The fastest previously known algorithm has exponential expected running time. Our algorithm is polynomial, requiring an expected O(n 4 ) operations. Applications of this algorithm include the elimination of critical sections from concurrent data structures and the construction of asymptotically unbiased shared coins.

Valid XHTML 1.1 Valid CSS! Powered by PHP