Title:	Randomized Wait-Free Consensus Using An Atomicity Assumption

Speaker: Ling Cheung

Place: 	32-G531
Time: 	10:30am-12
Date: 	Friday, October 13, 2006

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 perform a random 
choice and a write operation in one atomic step.  The expected total
work for our algorithm is shown to be O(N \log (\log N)), compared
with O(N^2) for the CIL algorithm, and O(N \log N) for the best
known weak adversary algorithm.  We also model check instances of
our algorithm using the probabilistic model checking tool PRISM.