Dijkstra's Self-Stabilizing Algorithm in Unsupportive Environments

Details Dijkstra's Self-Stabilizing Algorithm in Unsupportive Environments Dijkstra's Self-Stabilizing Algorithm in Unsupportive Environments

2001-05-07

arxiv.org/abs/cs/0105013v1

Computer Science

Distributed, Parallel, and Cluster Computing

12 pages, uses eepic.sty

Scientific paper

The first self-stabilizing algorithm [Dij73] assumed the existence of a central daemon, that activates one processor at time to change state as a function of its own state and the state of a neighbor. Subsequent research has reconsidered this algorithm without the assumption of a central daemon, and under different forms of communication, such as the model of link registers. In all of these investigations, one common feature is the atomicity of communication, whether by shared variables or read/write registers. This paper weakens the atomicity assumptions for the communication model, proposing versions of [Dij73] that tolerate various weaker forms of atomicity. First, a solution for the case of regular registers is presented. Then the case of safe registers is considered, with both negative and positive results presented. The paper also presents an implementation of [Dij73] based on registers that have probabilistically correct behavior, which requires a notion of weak stabilization.

Affiliated with

Also associated with

No associations

Rating

Dijkstra's Self-Stabilizing Algorithm in Unsupportive Environments 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 Dijkstra's Self-Stabilizing Algorithm in Unsupportive Environments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dijkstra's Self-Stabilizing Algorithm in Unsupportive Environments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-558732