Randomization Adaptive Self-Stabilization

Details Randomization Adaptive Self-Stabilization Randomization Adaptive Self-Stabilization

2008-10-24

arxiv.org/abs/0810.4440v1

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

We present a scheme to convert self-stabilizing algorithms that use randomization during and following convergence to self-stabilizing algorithms that use randomization only during convergence. We thus reduce the number of random bits from an infinite number to a bounded number. The scheme is applicable to the cases in which there exits a local predicate for each node, such that global consistency is implied by the union of the local predicates. We demonstrate our scheme over the token circulation algorithm of Herman and the recent constant time Byzantine self-stabilizing clock synchronization algorithm by Ben-Or, Dolev and Hoch. The application of our scheme results in the first constant time Byzantine self-stabilizing clock synchronization algorithm that uses a bounded number of random bits.

Affiliated with

Also associated with

No associations

Rating

Randomization Adaptive Self-Stabilization 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 Randomization Adaptive Self-Stabilization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomization Adaptive Self-Stabilization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-698206