Proving Time Bounds for Randomized Distributed Algorithms

Appears: Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (PODC), Los Angeles, CA, pages 314-323, August 1994.

Abstract: A method of analyzing time bounds for randomized distributed algorithms is presented, in the context of a new and general framework for describing and reasoning about randomized algorithms. The method consists of proving auxiliary statements of the form U->{t,p} U', which means that whenever the algorithm begins in a state in set U, with probability p, it will reach a state in set U' within time t. The power of the method is illustrated by its use in proving a constant upper bound on the expected time for some process to reach its critical region, in Lehmann and Rabin's Dining Philosophers algorithm.

Download:

Download the paper from the publisher.

Download an author-created copy of the paper.