Proving Time Bounds for Randomized Distributed Algorithms

Authors: Nancy Lynch and Isaac Saias and Roberto Segala

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 the paper from the publisher.

Download an author-created copy of the paper.