Proving time bounds for randomized distributed algorithms

Details Proving time bounds for randomized distributed algorithms Proving time bounds for randomized distributed algorithms

1994-09-19

arxiv.org/abs/math/9409221v1

Mathematics

Combinatorics

19 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Proving time bounds for randomized distributed algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Proving time bounds for randomized distributed algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Proving time bounds for randomized distributed algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-255181