Article

Free access

Self-stabilization by counter flushing

Author:

George VargheseAuthors Info & Claims

PODC '94: Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing

Pages 244 - 253

https://doi.org/10.1145/197917.198102

Published: 14 August 1994 Publication History

PDF eReader

References

[1]

Yehuda Afek and Geoffrey Brown. Selfstabilization of the alternating bit protocol. In Proc. 8th IEEE Syrup. on Reliable Distributed Systems, 1989.

Crossref

Google Scholar

[2]

Anish Arora and Mohamed G. Gouda. Distributed reset. In Proc. l Oth Uonf. on Foundations of Software Technology and Theoretical Computer Science, 1990.

Crossref

Google Scholar

[3]

Anish Arora, Mohamed G. Gouda, and George Varghese. Distributed constraint satisfaction. {n Proceedings I dth IEEE D US, Poland, June 1994.

Google Scholar

[4]

Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-Shamir, and George Varghese. Time optimal self-stabilizing synchronization. In Proc. 25th A UM STOC, Oct 1993.

Digital Library

Google Scholar

[5]

Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. Self-stabilization by local checking and correction. In Proc. 32nd IEEE FO CS, Oct 1991.

Digital Library

Google Scholar

[6]

M. Schneider. Self-stabilization A CM Computing Surveys, 25(1), 1993.

Digital Library

Google Scholar

[7]

K. Mani Chandy and Leslie Lamport. Distributed snapshots: Determining global states of distributed systems. A UM Trans. on Comput. Syst., 3(1):63-75, February 1985.

Digital Library

Google Scholar

[8]

Edsger W. Dijkstra. Self stabilization in spite of distributed control. Comm. of the A CA/{, 17:643-644, 1974.

Digital Library

Google Scholar

[9]

Shlomo Dolev, Amos Israeli, and Shlomo Moran. Self-stabilization of dynamic systems assuming only read/write atomicity. In Proc. l Oth A CM PODC Syrup, Quebec City, Aug 1990.

Digital Library

Google Scholar

[10]

Shlomo Dolev, Amos Israeli, and Shlomo Moran. Resource bounds for self-stabilizing message driven protocols. In Proc. 11th A CM PODC Syrup., Montreal, Canada, August 1991.

Digital Library

Google Scholar

[11]

Mohamed G. Gouda and Nicholas J. Multaxi. Stabilizing communication protocols. IEEE Trans. Comp, 40(4), April 1991.

Digital Library

Google Scholar

[12]

Shmuel Katz and Kenneth Perry. Self:. stabilizing extensions for message-passing systems. In Proc. l Oth A CM PODC Syrup., Quebec City, Aug 1990.

Digital Library

Google Scholar

[13]

Nancy A. Lynch and Mark R. Turtle. An introduction to input/output automata. CWI Quarterly, 2(3):219-246, 1989.

Google Scholar

[14]

Jayadev Misra. Detecting termination of distributed computations using markers. In Proc. 2nd A CM PODC Syrup., Montreal~ Aug 1983.

Digital Library

Google Scholar

[15]

Craig Partridge. Gigabit Networking. Addison-Wesley, Reading,MAT 1993.

Digital Library

Google Scholar

[16]

Adrian Segall. Distributed network protocols. IEEE Trans. Info. Theory, IT-29(1):23-35, Jan 1983.

Crossref

Google Scholar

[17]

Andrew S. Tanenbaum. Computer Networks. Prentice-Hall, Englewood Cliffs, N. J., 1981.

Digital Library

Google Scholar

[18]

Gerhard Tel. The Structure of Distributed Al. gorithms. PhD thesis, University of Utrecht.

Google Scholar

[19]

George Varghese. Self-stabilization by local checking and correction. Ph.D. Thesis MIT/LCS/TR-583, MIT, Oct 1992.

Digital Library

Google Scholar

[20]

George Varghese. Serf-stabilization by counter flushing. Washington University Technical Report, WUCS-94-14, 1994.

Google Scholar

Cited By

View all

Ebnenasir AKlinkhamer A(2021)Topology-Specific Synthesis of Self-Stabilizing Parameterized Systems with Constant-Space ProcessesIEEE Transactions on Software Engineering10.1109/TSE.2019.290148547:3(614-629)Online publication date: 1-Mar-2021
https://doi.org/10.1109/TSE.2019.2901485
Klinkhamer AEbnenasir A(2017)Synthesizing Parameterized Self-stabilizing Rings with Constant-Space ProcessesFundamentals of Software Engineering10.1007/978-3-319-68972-2_7(100-115)Online publication date: 11-Oct-2017
https://doi.org/10.1007/978-3-319-68972-2_7
Klinkhamer AEbnenasir A(2016)Shadow/Puppet SynthesisIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2016.253602327:11(3338-3350)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1109/TPDS.2016.2536023
Show More Cited By

Index Terms

Self-stabilization by counter flushing

Recommendations

Self-Stabilization by Counter Flushing

A useful way to design simple and robust protocols is to make them self-stabilizing. A protocol is said to be self-stabilizing if it begins to exhibit correct behavior even after starting in an arbitrary state. We describe a simple technique for self-...
Counter-Based Cache Replacement and Bypassing Algorithms

Recent studies have shown that in highly associative caches, the performance gap between the Least Recently Used (LRU) and the theoretical optimal replacement algorithms is large, motivating the design of alternative replacement algorithms to improve ...
Kill the Program Counter: Reconstructing Program Behavior in the Processor Cache Hierarchy
ASPLOS '17

Data prefetching and cache replacement algorithms have been intensively studied in the design of high performance microprocessors. Typically, the data prefetcher operates in the private caches and does not interact with the replacement policy in the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '94: Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing

August 1994

406 pages

ISBN:0897916549

DOI:10.1145/197917

Chairmen:
James Anderson
Univ. of North Carolina at Chapel Hill
,
David Peleg
Weizmann Institute & IBM T.J. Watson
,
Elizabeth Borowsky
Univ. of California at Los Angeles

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: 14 August 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODC94

Sponsor:

PODC94: 13th Annual ACM Symposium on Principles of Distributed Computing

August 14 - 17, 1994

California, Los Angeles, USA

Acceptance Rates

PODC '94 Paper Acceptance Rate 67 of 133 submissions, 50%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

43
Total Citations
View Citations
188
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)4

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ebnenasir AKlinkhamer A(2021)Topology-Specific Synthesis of Self-Stabilizing Parameterized Systems with Constant-Space ProcessesIEEE Transactions on Software Engineering10.1109/TSE.2019.290148547:3(614-629)Online publication date: 1-Mar-2021
https://doi.org/10.1109/TSE.2019.2901485
Klinkhamer AEbnenasir A(2017)Synthesizing Parameterized Self-stabilizing Rings with Constant-Space ProcessesFundamentals of Software Engineering10.1007/978-3-319-68972-2_7(100-115)Online publication date: 11-Oct-2017
https://doi.org/10.1007/978-3-319-68972-2_7
Klinkhamer AEbnenasir A(2016)Shadow/Puppet SynthesisIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2016.253602327:11(3338-3350)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1109/TPDS.2016.2536023
Ebnenasir AMayo J(2015)Fault-Tolerant Parallel and Distributed Computing for Software Engineering UndergraduatesProceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium Workshop10.1109/IPDPSW.2015.80(788-794)Online publication date: 25-May-2015
https://dl.acm.org/doi/10.1109/IPDPSW.2015.80
Jacob RRicha AScheideler CSchmid STäubig H(2014)SKIP+Journal of the ACM10.1145/262969561:6(1-26)Online publication date: 17-Dec-2014
https://dl.acm.org/doi/10.1145/2629695
Jubran OTheel O(2014)Exploiting Synchronicity for Immediate Feedback in Self-Stabilizing PIF AlgorithmsProceedings of the 2014 IEEE 20th Pacific Rim International Symposium on Dependable Computing10.1109/PRDC.2014.21(106-115)Online publication date: 18-Nov-2014
https://dl.acm.org/doi/10.1109/PRDC.2014.21
Stehr MKim MTalcott C(2014)Partially Ordered Knowledge Sharing and Fractionated Systems in the Context of other Models for Distributed ComputingSpecification, Algebra, and Software10.1007/978-3-642-54624-2_20(402-433)Online publication date: 2014
https://doi.org/10.1007/978-3-642-54624-2_20
Klinkhamer AEbnenasir A(2014)Synthesizing Self-stabilization through Superposition and BacktrackingStabilization, Safety, and Security of Distributed Systems10.1007/978-3-319-11764-5_18(252-267)Online publication date: 2014
https://doi.org/10.1007/978-3-319-11764-5_18
Farahat AEbnenasir A(2012)A Lightweight Method for Automated Design of Convergence in Network ProtocolsACM Transactions on Autonomous and Adaptive Systems10.1145/2382570.23825747:4(1-36)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1145/2382570.2382574
Clouser TNesterenko MScheideler C(2012)TiaraTheoretical Computer Science10.1016/j.tcs.2011.12.079428(18-35)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.1016/j.tcs.2011.12.079
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

Self-Stabilization by Counter Flushing

Counter-Based Cache Replacement and Bypassing Algorithms

Kill the Program Counter: Reconstructing Program Behavior in the Processor Cache Hierarchy