Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

preprint · ArXiv.org · 2001

Dijkstra's Self-Stabilizing Algorithm in Unsupportive Environments

Shlomi Dolev, Ted Herman

Cited by 0Open access

Abstract

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.

Cite this paper

APA 7

Dolev, S., & Herman, T. (2001). Dijkstra's Self-Stabilizing Algorithm in Unsupportive Environments. ArXiv.org. https://doi.org/10.48550/arxiv.cs/0105013

MLA 9

Dolev, Shlomi, and Ted Herman. “Dijkstra's Self-Stabilizing Algorithm in Unsupportive Environments.” ArXiv.org, 2001, https://doi.org/10.48550/arxiv.cs/0105013.

Chicago

Dolev, Shlomi, and Ted Herman. 2001. “Dijkstra's Self-Stabilizing Algorithm in Unsupportive Environments.” ArXiv.org. https://doi.org/10.48550/arxiv.cs/0105013.

Harvard

Dolev, S. and Herman, T. (2001) ‘Dijkstra's Self-Stabilizing Algorithm in Unsupportive Environments’, ArXiv.org. Available at: https://doi.org/10.48550/arxiv.cs/0105013.

BibTeX
@misc{dolev2001dijkstra,
  title = {{Dijkstra's Self-Stabilizing Algorithm in Unsupportive Environments}},
  author = {Dolev, Shlomi and Herman, Ted},
  journal = {ArXiv.org},
  year = {2001},
  doi = {10.48550/arxiv.cs/0105013}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.

Related papers