Article

Free access

Self-stabilizing algorithms for synchronous unidirectional rings

Authors:

Alain Mayer,

Rafail Ostrovsky,

Moti YungAuthors Info & Claims

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

Pages 564 - 573

Published: 28 January 1996 Publication History

PDF eReader

References

[1]

Y. AFEK AND G.M.BaowN, Self-stabilizing over unreliable communication media. Distributed Computing, 7:1993, pp. 27-34.

Digital Library

Google Scholar

[2]

Y. AFEK AND E. GAFNI, Distributed Algorithms for Unidixectional Networks, SIAM J. on Computing, 1994 pp. 1152-1178.

Digital Library

Google Scholar

[3]

Y. AFEK, S. KUTTEN, AND M. YUNC, Memoryefficient self stabilizing protocols for general networks. In Proc. of the dth Int. Workshop on Distributed Algorithms, Springer-Verlag LNCS, September 1990.

Digital Library

Google Scholar

[4]

B. ALBERT AND A.P. JAYASUMAN^, FDDI and FDDI-II: Architecture, Protocols, and Performance, Ariech House Telecommunication Library, ed. V. Cerf, Artech House, 1994.

Digital Library

Google Scholar

[5]

E. ANAGNOSTOU, R. EL-YANIV, AND V. HADZI- LACOS, Memory adaptive self-stabilizing protocols. In Proc. of the 6th Int. Workshop on Distributed Algorithms: Springer- Verlag LNCS, November 1992.

Digital Library

Google Scholar

[6]

D. ANGLUIN, Local and global properties in networks of processors, Proc. 12ih A CM Symp. on Theory of Computing (1980), 82-93.

Digital Library

Google Scholar

[7]

B. AWEaBUCH, S. KUTTEN, Y. M^NSOUa, B. PATT-SHAMIR, AND G. VARGHESE, Time optimal self stabilizing synchronization. In Proc. ~5th A CM Syrup. on Theory of Computing, pages 652- 661, May 1993.

Digital Library

Google Scholar

[8]

B. AWERBUCH AND R. OSTROVSKY, Memory efficient and self stabilizing network reset. In Proc. of the ldth A CM Symp. on Principles of Distributed Computing, August 1994.

Digital Library

Google Scholar

[9]

B. AWERBUCH, B. PATT-SHAMIR, AND G. VAgGI~ESE, Self-stabilization by local checking and correction. In Proc. of the 32nd IEEE Ann. Syrup. on Fo~ndaiion of Computer Science, pages 268-277, October 199t.

Digital Library

Google Scholar

[10]

B. AWEaBUCH, AND G. VAaCHESE, Distributed program checking: a paradigm for building self-stabilizing distributed protocols, Proc. 33nd IEEE Syrup. on Foundations of Computer Science (1991), 258-267.

Digital Library

Google Scholar

[11]

R. COLE, ^Nr) U VISUKIN, Deterministic Coin Tossing and Accelerating Cascades, Proc. 18 A CA/{ Syrup. on Theory of Computing, (1986), 206-219.

Digital Library

Google Scholar

[12]

E. W. DIJKSTaA. Self-stabilizing systems in spite of distributed control. Communication of the ACM, 17:643-644, November 1974.

Digital Library

Google Scholar

[13]

S. DOLEV, A. ISRAELI, AND $. MOa^N. Selfstabilization of dynamic systems assuming only read/write atomicity. In Proc. of lhe Ninth A CM Syrup. on Principles of Distributed Computing, pages 103-118, August 1990.

Digital Library

Google Scholar

[14]

S. DOLEV, A. ISRAELI, AND S. MORAN. Uniform dynamic self-stabilizing leader election. In P.G. Spirakis S. Toueg and L. Kirousis, editors, Lecture Notes in Computer Science 579: Proceedings of the fifth Int. Workshop on Distributed Algorithms, pages 163-180. Springer Verlag, October 1991.

Digital Library

Google Scholar

[15]

D. DOLEV, M. KL^wE, AND M. RODEH, An O(n log n) Unidirectional Algorithm for Extrema Finding In a Cycle. J. of Algorithms, 3: 245-260, 1982.

Google Scholar

[16]

S. EVEN, A. LITMAN, AND P. WINKLES. Computing with Snakes in Directed Network of Automata Proc. 31st IEEE Symp. on Foundations of Computer Science (1990), 740--745.

Google Scholar

[17]

G.N. FaEDEaiCKSON AND N. LYNCH, The impact of synchronous communication on the problem of electing a leader. J. of the ACM 34(1) (1987), 98-115.

Digital Library

Google Scholar

[18]

T. HERMAN, Probabilistic self-stabilization, Information Processing Letters 35 (1990), 63-67.

Digital Library

Google Scholar

[19]

N. HONDA AND Y. NISHITANI, The Firing Squad Synchronization Problem for Graphs, Theoretical Computer Science, v. 14, 1981, pp. 39-61.

Google Scholar

[20]

A. ISaAELI AND M. JALrON, Token management schemes and random walks yield self stabilizing mutual exclusion, Proc. 9th A CM Syrup. on Principles of Distributed. Coinputing (1990), 119-130.

Digital Library

Google Scholar

[21]

A. ITAI AND M. I~ODEH, Symmetry breaking in distributive networks, Information and Computation 88 (1990) 60-87.

Digital Library

Google Scholar

[22]

A. ITAI, On the power needed to elect a leader Proc. dth International Workshop on Distributed Algorithms, Lecture Notes in Computer,_qcicncc, Vol 486, Springer-Verlag, New York, (1989), 29- 40.

Digital Library

Google Scholar

[23]

G. iTKIS, AND L LEVIN. Fast and Lean Self- Stabilizing Asynchronous Protocols. In Proc. of the 35th {EEE Ann. Syrup. on Foundation of Computer Science, October 1994.

Google Scholar

[24]

S. KATZ AND K.J. PEARY, Self-stabilizing extensions for message-passing systems, Di.~t. ribuied Computing 7 (1993), 17-26.

Digital Library

Google Scholar

[25]

S. KUTTEN, Stepwise Construction of Efficient Distributed Traversing Algorithm for General Strongly Connected Directed Networks, The 9-lh IUCC, 446-458, 1988.

Google Scholar

[26]

N.LINIAL, Distributive Graph Algorithms- Global Solutions from Local Data. In Proc. of lhe 28th IEEE Ann. Symp. on Foundation of Computer Science, October 1987, 331-335.

Google Scholar

[27]

A. M^~~.a, Y. OFEK, R. OSTaOVSK~, AND M. YUNG, Self-stabilizing symmetry breaking in constant space. In Proc. ~dth ACM 5'ymp. on Theory of Computing, May 1992.

Digital Library

Google Scholar

[28]

R~. OSTROVSKY AND D. WILKERSON Faster Computation On Directed Networks of Automata. In Proc. of Fourteenth Annual ACM Symposium on Principles of Distributed Computing (PODC-95), Ottawa, Ontario, Canada, August 20-23, 1995.

Digital Library

Google Scholar

[29]

R. OSTaOvSKY AND M YUNG, How to withstand mobile virus attacks, Proc. of the 10th ACM Symposium on the Principles in Distributed Computing, 1991, pp. 51-61.

Digital Library

Google Scholar

[30]

(;. PAaLATI AND M YUNG, Non-exploratory self-stabilization for constant-space symmetrybreaking Proc. of the 2d ESA (European Symp. on Algorithms). Springer-Verlag, LNCS 855, 1994, pp. 183-201.

Digital Library

Google Scholar

[31]

G. PETERSON, An O(nlog n) Unidirectional Algorithm for the Circular Extrema Problem. ACM Tran. Prog. Lang. Syst., 4: 758-762, 1982.

Digital Library

Google Scholar

[32]

F.E. RosE, FDDI- A Tutorial, IEEE Communication Magazine, v. 24, pp. 10-15, May 1986.

Google Scholar

[33]

A.S. TANENBAUM, Computer Networks, 2-d ed. Prentice Hall Software Series, Prentice Hall.

Digital Library

Google Scholar

[34]

P. TET^LI AND P. WINKLe:a, On a Random Walk Problem arising in Self-Stabilizing Token Management In Proc. of the l Oth A CM Syrup. on Principles of Distributed Computing, August 1991.

Digital Library

Google Scholar

[35]

G. VARC, HgSE.Self-Stabilizing by Counter- Flushing In Proc. of the l~tth A CM Syrup. on Principles of Distributed Computing, August 1994.

Digital Library

Google Scholar

Cited By

View all

Altisen KCournier ADefalque GDevismes SKuznetsov PGelles ROlivetti D(2024)On Self-stabilizing Leader Election in Directed NetworksProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662778(527-537)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662778
Kowalski DMalinowski A(2008)How to meet in anonymous networkTheoretical Computer Science10.1016/j.tcs.2008.02.010399:1-2(141-156)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1016/j.tcs.2008.02.010
Korman AKutten S(2006)On distributed verificationProceedings of the 8th international conference on Distributed Computing and Networking10.1007/11947950_12(100-114)Online publication date: 27-Dec-2006
https://dl.acm.org/doi/10.1007/11947950_12
Show More Cited By

Index Terms

Self-stabilizing algorithms for synchronous unidirectional rings

Recommendations

Grooming in unidirectional rings: K4-e designs

In wavelength division multiplexing for unidirectional rings, traffic grooming is used to pack low rate signals into higher rate streams to share a wavelength. The grooming chosen determines the number of add-drop multiplexers used for the optical-to-...
Efficient algorithms for wavelength rerouting in WDM multi-fiber unidirectional ring networks

In this article, we consider wavelength rerouting in wavelength-routed Wavelength-Division Multiplexed (WDM) multi-fiber unidirectional ring networks with circuit switching. The wavelength continuity constraint imposed by WDM networks leads to poor ...
Grooming multicast traffic in unidirectional SONET/WDM rings
Part Supplement

In this paper we study the problem of efficient grooming of given non-uniform multicast traffic demands on a unidirectional SONET/WDM ring. The goal is to try to minimize the network cost as given by (i) the number of wavelengths required per fiber and (...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

January 1996

586 pages

ISBN:0898713668

Chairman:
Éva Tardos

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 28 January 1996

Check for updates

Qualifiers

Article

Conference

SODA96

Sponsor:

SIGACT
SIAM

SODA96: Conference on Discrete Algorithms

January 28 - 30, 1996

Georgia, Atlanta, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
441
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)6

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Altisen KCournier ADefalque GDevismes SKuznetsov PGelles ROlivetti D(2024)On Self-stabilizing Leader Election in Directed NetworksProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662778(527-537)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662778
Kowalski DMalinowski A(2008)How to meet in anonymous networkTheoretical Computer Science10.1016/j.tcs.2008.02.010399:1-2(141-156)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1016/j.tcs.2008.02.010
Korman AKutten S(2006)On distributed verificationProceedings of the 8th international conference on Distributed Computing and Networking10.1007/11947950_12(100-114)Online publication date: 27-Dec-2006
https://dl.acm.org/doi/10.1007/11947950_12
Kowalski DMalinowski A(2006)How to meet in anonymous networkProceedings of the 13th international conference on Structural Information and Communication Complexity10.1007/11780823_5(44-58)Online publication date: 2-Jul-2006
https://dl.acm.org/doi/10.1007/11780823_5
Sirakoulis GRaptis VKarafyllidis ITsalides PThanailakis A(2005)A fault-tolerant message passing algorithm and its hardware implementationAdvances in Engineering Software10.1016/j.advengsoft.2004.10.00536:3(159-171)Online publication date: 1-Mar-2005
https://dl.acm.org/doi/10.1016/j.advengsoft.2004.10.005
Rosaz LNeiger G(2000)Self-stabilizing token circulation on asynchronous uniform unidirectional ringsProceedings of the nineteenth annual ACM symposium on Principles of distributed computing10.1145/343477.343626(249-258)Online publication date: 16-Jul-2000
https://dl.acm.org/doi/10.1145/343477.343626
Beauquier JGradinariu MJohnen CCoan BWelch J(1999)Memory space requirements for self-stabilizing leader election protocolsProceedings of the eighteenth annual ACM symposium on Principles of distributed computing10.1145/301308.301358(199-207)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1145/301308.301358
Afek YBremler ASaks M(1997)Self-stabilizing unidirectional network algorithms by power-supplyProceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms10.5555/314161.314193(111-120)Online publication date: 5-Jan-1997
https://dl.acm.org/doi/10.5555/314161.314193

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

Grooming in unidirectional rings: K4-e designs

Efficient algorithms for wavelength rerouting in WDM multi-fiber unidirectional ring networks

Grooming multicast traffic in unidirectional SONET/WDM rings