Weak vs. Self vs. Probabilistic Stabilization

Details Weak vs. Self vs. Probabilistic Stabilization Weak vs. Self vs. Probabilistic Stabilization

2007-11-23

arxiv.org/abs/0711.3672v2

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

Self-stabilization is a strong property that guarantees that a network always resume correct behavior starting from an arbitrary initial state. Weaker guarantees have later been introduced to cope with impossibility results: probabilistic stabilization only gives probabilistic convergence to a correct behavior. Also, weak stabilization only gives the possibility of convergence. In this paper, we investigate the relative power of weak, self, and probabilistic stabilization, with respect to the set of problems that can be solved. We formally prove that in that sense, weak stabilization is strictly stronger that self-stabilization. Also, we refine previous results on weak stabilization to prove that, for practical schedule instances, a deterministic weak-stabilizing protocol can be turned into a probabilistic self-stabilizing one. This latter result hints at more practical use of weak-stabilization, as such algorthms are easier to design and prove than their (probabilistic) self-stabilizing counterparts.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-363142