Article

Free access

Token management schemes and random walks yield self-stabilizing mutual exclusion

Authors:

Amos Israeli,

Marc JalfonAuthors Info & Claims

PODC '90: Proceedings of the ninth annual ACM symposium on Principles of distributed computing

Pages 119 - 131

https://doi.org/10.1145/93385.93409

Published: 01 August 1990 Publication History

PDF eReader

References

[1]

Y. Afek and G.M. Brown, "Self- Stabilization of the Alternating-Bit Protocol", Proc. of the 8th IEEE Symposium on Reliable Distributed Systems, (1989), pp. 10-12.

Crossref

Google Scholar

[2]

R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lov~sz and C. Rackoff, "Random walks, Universal traversal sequences, and the complexity of maze problems", Proc of the 20th Annual Symposium on Foundations of Computer Science, (1979), pp. 218-223.

Digital Library

Google Scholar

[3]

G.M. Brown, M.G. Gouda, and C.L. Wu, "A Self-Stabilizing Token system", Proc. of the 20th Annual Hawaii International Conference on System sciences (1987), pp. 218-223.

Google Scholar

[4]

J.E. Burns and J. Pachl, "Uniform Self-Stabilizing Rings", Aegean Workshop On Computing, (1988), Lecture notes in computer science 319, pp. 391- 400.

Digital Library

Google Scholar

[5]

J.E. Burns, "Self-Stabilizing Rings without Demons", Technical Report GIT-ICS-87/36, Georgia Institute Of Technology.

Google Scholar

[6]

B. Chor, A. Israeli, and M. Li, "On Processor Coordination Using Asynchronous Hardware", Proc. of the Sixth A CM Symposium on Principles of Distributed Computing (1987), pp. 86-97.

Digital Library

Google Scholar

[7]

E.W. Dijkstra, "Self-Stabilizing Systems in Spite of Distributed Control", Communications of the ACM 17,11 (1974), pp. 643-644.

Digital Library

Google Scholar

[8]

S. Dolev, A. Israeli and S. Moran, "Self Stabilization of Dynamic Systems", These proceedings.

Digital Library

Google Scholar

[9]

D. Dolev and D. Koller,"Token Survival Achieving Reliability in ~ Tokei~ Ring" Preprint

Google Scholar

[10]

W. Feller, An Introduction to PT"obability Theory and Its Applications, Wi{- ley, (! 968).

Google Scholar

[11]

A. Israeli and M. Jalfon" "Self Stabilizing Ring Orientution", submitted for publication.

Google Scholar

[12]

A. Itai and M. Rodeh, "Probabilistic Methods for Breaking Symmetry in Distributed Networks", to appear in Information and Computation.

Google Scholar

[13]

S. Katz and K.J. Perry, "Selfstabilizing Extensions", These proceedings.

Google Scholar

[14]

H.S.M. Kruijer, "Self-stabilization (in spite of distributed control) in treestructured systems", Information Processing Letters 8,2 (1979), pp. 91-95.

Crossref

Google Scholar

[15]

D. Lehmann and M. Rabin, "On the Advantages of Free Choice" A Symmetric and Fully Distributed Solution to the Dining Philosophers Problem", Proc. 8th Principles of Programmin9 Languages (1981) pp. lax-ins.

Digital Library

Google Scholar

[16]

J.B. Rosser and L. Schoenfeld, "Approximate formulas for some functions of prime numbers", Illinois Journal of Math. V 6, (1962), pp. 64-94.

Google Scholar

[17]

P. L. Tchebycheff, "M&noire sur les nombres premiers", J. de math. pures et appliq. I, XVII (1852), reprinted in Oeuvres de P. L. Tchebycheff, by A. Markoff and N. Sonin, Chlesea, N.Y.

Google Scholar

[18]

M.Tchuente, "Sur l'auto-stabilisation dans un rdseau d'ordinateurs" RAIRO Inf. Theor. 15 ( 1981), pp. 4 7-66.

Google Scholar

Cited By

View all

Saxena AMondal K(2024)A Further Study on Weak Byzantine Gathering of Mobile AgentsProceedings of the 25th International Conference on Distributed Computing and Networking10.1145/3631461.3631551(22-31)Online publication date: 4-Jan-2024
https://dl.acm.org/doi/10.1145/3631461.3631551
Saxena AMondal K(2024)A Further Study on Weak Byzantine Gathering of Mobile AgentsTheoretical Computer Science10.1016/j.tcs.2024.114892(114892)Online publication date: Sep-2024
https://doi.org/10.1016/j.tcs.2024.114892
Agarwal CGuha SKřetínský JPazhamalai M(2024)PAC statistical model checking of mean payoff in discrete- and continuous-time MDPFormal Methods in System Design10.1007/s10703-024-00463-0Online publication date: 17-Aug-2024
https://doi.org/10.1007/s10703-024-00463-0
Show More Cited By

Index Terms

Token management schemes and random walks yield self-stabilizing mutual exclusion

Recommendations

Self-Stabilizing Mutual Exclusion in the Presence of Faulty Nodes
FTCS '95: Proceedings of the Twenty-Fifth International Symposium on Fault-Tolerant Computing

This paper presents the RatchetFT distributed fault-tolerant mutual exclusion algorithm for processor rings. RatchetFT is self-stabilizing, in that if mutual exclusion is lost due to any sequence of on-line failures and repairs of processors, mutual ...
Fair group mutual exclusion
PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing

In the group mutual exclusion problem [6], which generalizes mutual exclusion [2], a process chooses a session when it requests entry to the Critical Section. A group mutual exclusion algorithm must ensure that the mutual exclusion property holds: If ...
Lock-based self-stabilizing distributed mutual exclusion algorithms
ICDCS '96: Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96)

In 1974, Dijkstra introduced the notion of self-stabilization and presented a token circulation distributed mutual exclusion (DMX) protocol as the first self-stabilizing (SS) algorithm. Since then, many variations of SS DMX algorithms have been ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '90: Proceedings of the ninth annual ACM symposium on Principles of distributed computing

August 1990

411 pages

ISBN:089791404X

DOI:10.1145/93385

Chairman:
Cynthia Dwork
Univ. of Montreal, Quebec, Canada

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1990

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODC90

Sponsor:

PODC90: 9th Annual ACM Symposium in Principles of Distibuted Computing

August 22 - 24, 1990

Quebec, Quebec City, Canada

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

178
Total Citations
View Citations
851
Total Downloads

Downloads (Last 12 months)87
Downloads (Last 6 weeks)8

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Saxena AMondal K(2024)A Further Study on Weak Byzantine Gathering of Mobile AgentsProceedings of the 25th International Conference on Distributed Computing and Networking10.1145/3631461.3631551(22-31)Online publication date: 4-Jan-2024
https://dl.acm.org/doi/10.1145/3631461.3631551
Saxena AMondal K(2024)A Further Study on Weak Byzantine Gathering of Mobile AgentsTheoretical Computer Science10.1016/j.tcs.2024.114892(114892)Online publication date: Sep-2024
https://doi.org/10.1016/j.tcs.2024.114892
Agarwal CGuha SKřetínský JPazhamalai M(2024)PAC statistical model checking of mean payoff in discrete- and continuous-time MDPFormal Methods in System Design10.1007/s10703-024-00463-0Online publication date: 17-Aug-2024
https://doi.org/10.1007/s10703-024-00463-0
Dolev SKamei SKatayama YOoshita FWada K(2023)Neighborhood mutual remainder: self-stabilizing distributed implementation and applicationsActa Informatica10.1007/s00236-023-00450-861:1(83-100)Online publication date: 18-Dec-2023
https://doi.org/10.1007/s00236-023-00450-8
Eguchi ROoshita FInoue MTixeuil S(2023)Meeting Times of Non-atomic Random WalksStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-44274-2_22(297-311)Online publication date: 30-Sep-2023
https://doi.org/10.1007/978-3-031-44274-2_22
Los DSauerwald TAgrawal KLee I(2022)Brief AnnouncementProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538561(419-421)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538561
Dong RSudo YIzumi TMasuzawa T(2022)Loosely-stabilizing maximal independent set algorithms with unreliable communicationsTheoretical Computer Science10.1016/j.tcs.2022.09.031937(69-84)Online publication date: Nov-2022
https://doi.org/10.1016/j.tcs.2022.09.031
Dobe OWilke LÁbrahám EBartocci EBonakdarpour B(2022)Probabilistic Hyperproperties with RewardsNASA Formal Methods10.1007/978-3-031-06773-0_35(656-673)Online publication date: 24-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-06773-0_35
Heck LSpel JJunges SMoerman JKatoen J(2022)Gradient-Descent for Randomized Controllers Under Partial ObservabilityVerification, Model Checking, and Abstract Interpretation10.1007/978-3-030-94583-1_7(127-150)Online publication date: 14-Jan-2022
https://doi.org/10.1007/978-3-030-94583-1_7
SAKUMOTO YOHSAKI H(2021)Graph Degree Heterogeneity Facilitates Random Walker MeetingsIEICE Transactions on Communications10.1587/transcom.2020EBP3093E104.B:6(604-615)Online publication date: 1-Jun-2021
https://doi.org/10.1587/transcom.2020EBP3093
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Self-Stabilizing Mutual Exclusion in the Presence of Faulty Nodes

Fair group mutual exclusion

Lock-based self-stabilizing distributed mutual exclusion algorithms