Mathematics – Combinatorics
Scientific paper
1994-09-19
Mathematics
Combinatorics
12 pages
Scientific paper
The correctness of most randomized distributed algorithms is expressed by a statement of the form ``some predicate of the executions holds with high probability, regardless of the order in which actions are scheduled''. In this paper, we present a general methodology to prove correctness statements of such randomized algorithms. Specifically, we show how to prove such statements by a series of refinements, which terminate in a statement independent of the schedule. To demonstrate the subtlety of the issues involved in this type of analysis, we focus on Rabin's randomized distributed algorithm for mutual exclusion [Rabin 82]. Surprisingly, it turns out that the algorithm does not maintain one of the requirements of the problem under a certain schedule. In particular, we give a schedule under which a set of processes can suffer lockout for arbitrary long periods.
No associations
LandOfFree
Proving probabilistic correctness statements: the case of Rabin's algorithm for mutual exclusion 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 probabilistic correctness statements: the case of Rabin's algorithm for mutual exclusion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Proving probabilistic correctness statements: the case of Rabin's algorithm for mutual exclusion will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-255175