Article

Free access

Self-stabilizing unidirectional network algorithms by power-supply

Authors:

Yehuda Afek,

Anat BremlerAuthors Info & Claims

SODA '97: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms

Pages 111 - 120

Published: 05 January 1997 Publication History

PDF eReader

References

[1]

Y. Afek, B. Awerbuch, and E. Gafni. Applying static network protocols to dynamic networks. In Proc. o,f the ~8th IEEE Ann. Syrup. on Foundation of Computer Science, pages 358-370, October 1987.

Google Scholar

[2]

Y. Afek and G. M. Brown. SeW-stabilization over unreliable communication media. Distributed Computing Journal, 7:27-34, 1993. Abstract in Proc. o} the 8th IEEE Syrup. on Reliable Distributed Systems, 10- 12 1989.

Digital Library

Google Scholar

[3]

Y. Afek and E. Gafni. Distributed algorithms for unidirectional networks. Siam J. on Computing, 23(6), December 1994.

Digital Library

Google Scholar

[4]

Y. Afek, S. Kutten, and M. Yung. Memory-efficient self stabilizing protocols for general networks. In Proc. of the gth Int. Workshop on Distributed Algorithms, September 1990.

Digital Library

Google Scholar

[5]

Y. Afek and T. Lev. Distributed synchronization protocols for SDH networks. Submitted for publication, November 1995.

Google Scholar

[6]

E. Anagnostou, R. E1-Yaniv, and V. Hadzilacos. Memory adaptive serf-stabilizing protocols. In Proc. of the 6th Int. Workshop on Distributed Algorithms: Springer-Verlag LNCS, November 1992.

Digital Library

Google Scholar

[7]

A Arora and MG Gouda. Distributed reset. 43:1026- 1038, 1994.

Digital Library

Google Scholar

[8]

B. A werbuch, and G. Varghese. Distributed program checking' a paradigm for building self-stabilizing distributed protocols. In Proc. o} the ¿nd IEEE Ann. Syrup. on Foundation of Computer Science, pages 258- 267, October 1991.

Digital Library

Google Scholar

[9]

B. Awerbuch, S. Kutten, Y. Mansour, B. Patt-Shamir, and G. Varghese. Time optimal self stabilizing synchronization. In Proc. $Sth A CM Syrnp. on Theory of Computing, pages 652-661, May 1993.

Digital Library

Google Scholar

[10]

B. Awerbuch, B. Patt-Shamir, and G. Varghese. Selfstabilization by local checking and correction. In Proc. of the S~nd IEEE Ann. Syrup. on Foundation of Computer Science, pages 268-277, October 1991.

Digital Library

Google Scholar

[11]

B Awerbuch, B Patt-Shamir, G Varghese, and S Dolev. Self-stabilizing by local checking and global reset. In International Workshop on Distributed Algorithms, Springer- Verlag, pages 326-339, 1994.

Digital Library

Google Scholar

[12]

G. M. Brown, M. G. Gouda, and (3-1 Wu. Token systems that self-stabilize. IEEE Transactions on Computers, c38(6):845-852, 1989.

Digital Library

Google Scholar

[13]

J. Burns and J. Pachl. Uniform seW-stabilizing tings. A CM Transactions on _Programming Languages and Systems, 11(2):330-344, 1989.

Digital Library

Google Scholar

[14]

J. E. Burns, M. G. Gouda, and R. E. Miller. Stabilizatlon and pseudo stabilization. Tech_n}cM Report TR- 90-13, The University of Texas at Austin, May 1990.

Digital Library

Google Scholar

[15]

Z. CoUin and S. Dolev. SeE-stabilizing depth first search.Information Processing Letters, 49:297-301, 1994.

Digital Library

Google Scholar

[16]

E. W. Dijkstra. $elf-stabillzing systems in spite of distributed control. Communications of the ACM, 17(11):643-644, 1973.

Digital Library

Google Scholar

[17]

E. W. Dijkstra. Self-stabillzing systems in spite of distributed control. Communication o} the A CM, 17:643- 644, November 1974.

Digital Library

Google Scholar

[18]

D. Dolev, M. Klawe, and M. Rodeh. An O(n log n) unidirectional algorithm for extrcma finding in a circle. Journal of Algorithm, 3:245-260, 1982.

Google Scholar

[19]

S. Dolev, A. Israeli, and S. Moran. Resource bounds for self stabilizing message driven protocols. In Proc. l Oth A CM Syrup. on Principles of Distributed Computing, pages 281-294. ACM, august 1991.

Digital Library

Google Scholar

[20]

S. Dolev, A. Israeli, and S. Moran. Self-stabilization of dynamic systems assuming only read/write atomlclty. Distributed Computing Journal, 7, 1994. also In Proc. 9th A CM Syrup. on Principles of Distributed Computing, August 1990.

Digital Library

Google Scholar

[21]

S. Even, A. Litman, and P. Winkler. Computing with snakes in directed networks of automata. In Proc. of the 31st {EEE Ann. Syrup. on Foundation of Computer Science, pages 740-745, October 1990.

Google Scholar

[22]

El. Gafni and Y. Afek. Election and traversal in unidirectional networks. In Proc. of the 3rd Ann. A CM Syrup. on Principles o} Distributed Computing, August 1984.

Digital Library

Google Scholar

[23]

E. Gafni and W. Korfb. age. Distributed election in unidirectional eulerlan networks. In Proc. Twenty- Second Ann. Allerton Conference on Communication, Control, and Computing, October 1984.

Google Scholar

[24]

M. Gerla, L. Kleinrock, and Y. Afek. A distributed routing algorithm for unidirectional networks. In Proc. G~OBCOM 83, 1983.

Google Scholar

[25]

T. Herman. Probabilistic self-stabilization, ln}orma-,ion Processing Letters, 35:63-67, 1990.

Digital Library

Google Scholar

[26]

A Israeli and M Jalfon. Uniform self-stabilizing ring orientation.Information and Computatlon, 104:175- 196, 1993.

Digital Library

Google Scholar

[27]

S. Katz and K. J. Perry. Self-stabilizing extensions for message-passing systems. In M. Evangelist and S. Katz, editors, MCC Technical Report Number STP- 379-89, Pvoc. of the MCC Workshop on Self-Stabilizing Systems, 1989.

Google Scholar

[28]

S. Kutten. Stepwiae construction of an efficient distributed traversing algorithm for general strongly connected directed networks. In J. Early, editor, Proc. of the Ninth Int. Conference on Computer Communication, pages 446-452, October 1988.

Google Scholar

[29]

A. Mayer, Y. Ofek, R. Ostrovsky, and M. Yung. Selfstabilizing symmetry breaking in constant space. In Proc. ~dth A CM Syrup. on Theory of Computing, May 1992.

Digital Library

Google Scholar

[30]

A. Mayer, R. Ostrovsky, and M. Yung. General distributed self-stabilizlng algorithms for unidirectional rings. In Proe. of 8th Ann. A CM-S{AM Syrup. on Discrete Algorithms, January 1996.

Digital Library

Google Scholar

[31]

N. Multari. Self-Stabilizing Protocols. PhD thesis, Department of Computer Sciences, University of Texas, 1988. Ph.D. Thesis.

Google Scholar

[32]

Rafail Ostrovsky and Daniel Wilkerson. Faster computation on directed networks of automata. In Proceedings of the 14(th Annual A CM Symposium on Principles of Distributed Computing, pages 38-46. ACM, August 1995.

Digital Library

Google Scholar

[33]

G.L. Peterson. An O(n log n) unidirectional algorithm for the circular extrema problem. A CM Trans. Program. Lang. Syst., 4(4):758-762, October 1982.

Digital Library

Google Scholar

[34]

W. P. Tajibnapis. A correctness proof of a topology information maintenance protocol for a distributed computer network. CA CM, 20-7:477-485, 1977.

Digital Library

Google Scholar

Cited By

View all

Datta ALarmore L(2018)Self-Stabilizing Leader Election in Dynamic NetworksTheory of Computing Systems10.1007/s00224-017-9758-962:5(977-1047)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s00224-017-9758-9
Datta ALarmore LVemula P(2011)An O(n)-time self-stabilizing leader election algorithmJournal of Parallel and Distributed Computing10.1016/j.jpdc.2011.05.00871:11(1532-1544)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1016/j.jpdc.2011.05.008
Datta ALarmore LPiniganti H(2010)Slf-stabiliezing leader election in dynamic networksProceedings of the 12th international conference on Stabilization, safety, and security of distributed systems10.5555/1926829.1926837(35-49)Online publication date: 20-Sep-2010
https://dl.acm.org/doi/10.5555/1926829.1926837
Show More Cited By

Index Terms

Self-stabilizing unidirectional network algorithms by power-supply
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows
  2. Randomness, geometry and discrete structures

Recommendations

Fault-containment in self-stabilizing distributed systems
Fault-containing self-stabilizing distributed protocols

Self-stabilization is an elegant approach for designing a class of fault-tolerant distributed protocols. A self-stabilizing protocol is guaranteed to eventually converge to a legitimate state after a transient fault. However, even a minor transient ...
Self-Stabilizing Byzantine Broadcast
SRDS '14: Proceedings of the 2014 IEEE 33rd International Symposium on Reliable Distributed Systems

We consider the problem of reliably broadcasting messages in a multi-hop network where nodes can fail in some unforeseen manner. We consider the most general failure model: the Byzantine model, where failing nodes may exhibit arbitrary behavior, and ...

Comments

Information & Contributors

Information

Published In

SODA '97: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms

January 1997

788 pages

ISBN:0898713900

Chairman:
Michael Saks

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 05 January 1997

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
275
Total Downloads

Downloads (Last 12 months)53
Downloads (Last 6 weeks)9

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Datta ALarmore L(2018)Self-Stabilizing Leader Election in Dynamic NetworksTheory of Computing Systems10.1007/s00224-017-9758-962:5(977-1047)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s00224-017-9758-9
Datta ALarmore LVemula P(2011)An O(n)-time self-stabilizing leader election algorithmJournal of Parallel and Distributed Computing10.1016/j.jpdc.2011.05.00871:11(1532-1544)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1016/j.jpdc.2011.05.008
Datta ALarmore LPiniganti H(2010)Slf-stabiliezing leader election in dynamic networksProceedings of the 12th international conference on Stabilization, safety, and security of distributed systems10.5555/1926829.1926837(35-49)Online publication date: 20-Sep-2010
https://dl.acm.org/doi/10.5555/1926829.1926837
Wu MKim CJung J(2010)Leader election based on centrality and connectivity measurements in ad hoc networksProceedings of the 4th KES international conference on Agent and multi-agent systems: technologies and applications, Part I10.5555/1883838.1883887(401-410)Online publication date: 23-Jun-2010
https://dl.acm.org/doi/10.5555/1883838.1883887
Peres O(2009)Brief AnnouncementProceedings of the 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems10.1007/978-3-642-05118-0_65(795-796)Online publication date: 5-Nov-2009
https://dl.acm.org/doi/10.1007/978-3-642-05118-0_65
Datta ALarmore LVemula P(2008)Self-Stabilizing Leader Election in Optimal SpaceProceedings of the 10th International Symposium on Stabilization, Safety, and Security of Distributed Systems10.5555/1484018.1484033(109-123)Online publication date: 21-Nov-2008
https://dl.acm.org/doi/10.5555/1484018.1484033
Beauquier JDelaët SHaddad S(2006)Necessary and sufficient conditions for 1-adaptivityProceedings of the 20th international conference on Parallel and distributed processing10.5555/1898953.1899026(96-96)Online publication date: 25-Apr-2006
https://dl.acm.org/doi/10.5555/1898953.1899026
Burman JHerman TKutten SPatt-Shamir B(2005)Asynchronous and fully self-stabilizing time-adaptive majority consensusProceedings of the 9th international conference on Principles of Distributed Systems10.1007/11795490_13(146-160)Online publication date: 12-Dec-2005
https://dl.acm.org/doi/10.1007/11795490_13
Azar YKutten SPatt-Shamir BBorowsky ERajsbaum S(2003)Distributed error confinementProceedings of the twenty-second annual symposium on Principles of distributed computing10.1145/872035.872041(33-42)Online publication date: 13-Jul-2003
https://dl.acm.org/doi/10.1145/872035.872041
Beauquier JGenolini CKutten SCoan BWelch J(1999)Optimal reactive k-stabilizationProceedings of the eighteenth annual ACM symposium on Principles of distributed computing10.1145/301308.301359(209-218)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1145/301308.301359
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

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

Fault-containment in self-stabilizing distributed systems

Fault-containing self-stabilizing distributed protocols

Self-Stabilizing Byzantine Broadcast

Comments

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Acceptance Rates

Other Metrics

Article Metrics

Other Metrics

Cited By

PDF

eReader

Login options

Full Access

References

Cited By

Index Terms

Recommendations

Fault-containment in self-stabilizing distributed systems

Fault-containing self-stabilizing distributed protocols

Self-Stabilizing Byzantine Broadcast

Comments

Information

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations