Article

Distributed error confinement

Authors:

Boaz Patt-ShamirAuthors Info & Claims

PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing

Pages 33 - 42

https://doi.org/10.1145/872035.872041

Published: 13 July 2003 Publication History

Abstract

We initiate the study of error confinement in distributed applications, where the goal is that only nodes that were directly hit by a fault may deviate from their correct external behavior, and only temporarily. The external behavior of all other nodes must remain impeccable, even though their internal state may be affected. Error confinement is impossible if an adversary is allowed to inflict arbitrary transient faults on the system, since the faults might completely wipe out input values. We introduce a new fault tolerance measure we call agility, which quantifies the strength of an algorithm that disseminate information, against state corrupting faults.We study the basic problem of broadcast, and propose algorithms that guarantee error confinement with optimal agility to within a constant factor, even in asynchronous networks when the topology is unknown. These algorithms can serve as building blocks in more general reactive systems. Previous results in exploring locality in reactive systems were not error confined, and relied on the assumption (not used in current paper) that the errors hitting each node are probabilistic, such that a faulty node itself, or its neighbor, can detect the node faulty.The main algorithm uses the novel core bootstrapping technique, that seems inherent for voting in reactive networks; its analysis leads to an interesting combinatorial problem. The technique and the analysis may be of independent interest

References

[1]

Y. Afek and A. Bremler. Self-stabilizing unidirectional network algorithms by power-supply. In Proc. of the 8th ann. ACM-SIAM Symposium on Discrete Algorithms, pages 111--120, 1997.]]

Digital Library

[2]

Y. Afek and S. Dolev. Local stabilizer. In Proceedings of the 5th Israel Symposium on Theory of Computing and Systems, June 1997.]]

Digital Library

[3]

Y. Afek, S. Kutten, and M. Yung. Memory-efficient self-stabilization on general networks. In Proc. 4th Workshop on Distributed Algorithms, pages 15--28, Italy, Sept. 1990. Springer-Verlag (LNCS 486). To appear in Theoretical Comp. Sci.]]

Digital Library

[4]

B. Awerbuch, S. Kutten, Y. Mansour, B. Patt-Shamir, and G. Varghese. Time optimal self-stabilizing synchronization. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, San Diego, California, pages 652--661, May 1993. Also appeared as IBM Research Report RC-19149(83418).]]

Digital Library

[5]

B. Awerbuch, B. Patt-Shamir, and G. Varghese. Self-stabilization by local checking and correction. In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, pages 268--277, Oct. 1991.]]

Digital Library

[6]

B. Awerbuch, B. Patt-Shamir, G. Varghese, and S. Dolev. Self-stabilization by local checking and global reset. In Proc. 8th International Workshop on Distributed Algorithms, pages 326--339. Springer-Verlag (LNCS 857), 1994.]]

Digital Library

[7]

M. Breitling. Modeling faults of distributed, reactive systems. In 6th International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems, (FTRTFT2000), pages 58--69. Springer (LNCS 1926), 2000.]]

Digital Library

[8]

Imrich Chlamtac, Shlomit S. Pinter Distributed Nodes Organization Algorithm for Channel Access in a Multihop Dynamic Radio Network. IEEE Transactions on Computers 36(6): 728--737 (1987)]]

Digital Library

[9]

A. Bui, A. K. Datta, F. Petit, and V. Villain. State-optimal snap-stabilizing PIF in tree networks. In Proceedings of the Third Workshop on Self-Stabilizing Systems (WSS 3), pages 78--85. IEEE Computer Society, 1999.]]

Digital Library

[10]

E. W. Dijkstra. Self-stabilizing systems in spite of distributed control. Comm. ACM, 17(11):643--644, November 1974.]]

Digital Library

[11]

S. Dolev and T. Herman. Superstabilizing protocols for dynamic distributed systems. In Proc. of the Second Workshop on Self-Stabilizing Systems, pages 3.1--3.15, May 1995.]]

Digital Library

[12]

S. Dolev, A. Israeli, and S. Moran. Self-stabilization of dynamic systems assuming only read/write atomicity. In Proc. 9th Ann. ACM Symp. on Principles of Distributed Computing, Quebec City, Canada, Aug. 1990.]]

Digital Library

[13]

S. Ghosh, A. Gupta, T. Herman, and S. V. Pemmaraju. Fault-containing self-stabilizing algorithms. In Proc. 15th Ann. ACM Symp. on Principles of Distributed Computing, May 1996.]]

Digital Library

[14]

M.-Y. Kao, J. Reif, and S. Tare. Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. In Proc. of the 4th ann. ACM-SIAM Symposium on Discrete Algorithms, 1993.]]

Digital Library

[15]

S. Katz and K. J. Perry. Self-stabilizing extensions for message-passing systems. Distributed Computing, 7(1):17--26, 1993.]]

Digital Library

[16]

S. Kutten and B. Patt-Shamir. Stabilizing time-adaptive protocols. Theoretical Computer Science, 220(3):93--111, 1999.]]

Digital Library

[17]

S. Kutten and D. Peleg. Fault-local distributed mending. In Proc. 14th Ann. ACM Symp. on Principles of Distributed Computing, Aug. 1995.]]

Digital Library

[18]

L. Lamport. Time, clocks, and the ordering of events in a distributed system. Comm. ACM, 21(7):558--565, July 1978.]]

Digital Library

[19]

P. A. Lee and T. Anderson. Fault Tolerance: Principles and Practice. Springer-Verlag, Wien, second revised edition, 1990.]]

Digital Library

[20]

N. Lynch. Distributed Algorithms. Morgan Kaufmann, San Mateo, CA, 1995.]]

Digital Library

[21]

D. Malkhi, Y. Mansour, and M. Reiter. Diffusing without false rumors: On propagating updates in a byzantine environment. Theoretical Comput. Sci., 2002.]]

[22]

C. H. Papadimitriou and M. Yanakakis. Shortest paths without a map. Theoretical Computer Science, 84(1):127--150, 1991.]]

Digital Library

[23]

G. Parlati and M. Yung. Non-exploratory self-stabilization for constant-space symmetry-breaking. In J. van Leeuwen, editor, Proceedings of the 2nd Annual European Symposium on Algorithms, pages 26--28, Sept. 1994. LNCS 855, Springer Verlag.]]

Digital Library

[24]

D. J. Taylor. Practical techniques for damage confinement in software. In Proceedings of the 1998 Computer Security Dependability and Assurance (CSDA '98). IEEE, 1998.]]

Digital Library

[25]

G. Varghese. Self-stabilization by counter flushing. SIAM J. Comput., 30(2):486--510, 2000.]]

Digital Library

[26]

I-Ling Yen: A Highly Safe Self-Stabilizing Mutual Exclusion Algorithm. Information Processing Letters 57(6): 301--305 (1996).]]

Digital Library

Cited By

Patel RAwasthi LGovil MRachita (2023)n-Layer Platform for Hi-Tech WorldRole of Data-Intensive Distributed Computing Systems in Designing Data Solutions10.1007/978-3-031-15542-0_5(83-96)Online publication date: 26-Jan-2023
https://doi.org/10.1007/978-3-031-15542-0_5
Oliveira FTjang ABianchini RMartin RNguyen TMorin CMuller G(2010)BarricadeProceedings of the 5th European conference on Computer systems10.1145/1755913.1755924(83-96)Online publication date: 13-Apr-2010
https://dl.acm.org/doi/10.1145/1755913.1755924
YAMAUCHI YKAMEI SOOSHITA FKATAYAMA YKAKUGAWA HMASUZAWA T(2009)Hierarchical Composition of Self-Stabilizing Protocols Preserving the Fault-Containment PropertyIEICE Transactions on Information and Systems10.1587/transinf.E92.D.451E92-D:3(451-459)Online publication date: 2009
https://doi.org/10.1587/transinf.E92.D.451
Show More Cited By

Index Terms

Distributed error confinement

Recommendations

Distributed error confinement

We study error confinement in distributed applications, which can be viewed as an extreme case of various fault locality notions studied in the past. Error confinement means that to the external observer, only nodes that were directly hit by a fault may ...
The customizable fault/error model for dependable distributed systems
Dependable computing

Dependability is a qualitative term referring to a system's ability to meet its service requirements in the presence of faults. The types and number of faults covered by a system play a primary role in determining the level of dependability which that ...
Systematic t-Error Correcting/All Unidirectional Error Detecting Codes

In this paper we give methods for the construction of systematic t-random error correcting and all unidirectional error detecting codes. Also we give the encoding/decoding algorithms and discuss their implementation.

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing

July 2003

380 pages

ISBN:1581137087

DOI:10.1145/872035

General Chair:
Elizabeth Borowsky
Boston Coll.
,
Program Chair:
Sergio Rajsbaum
UNAM

Copyright © 2003 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODC03

Sponsor:

PODC03: Twenty-Second Annual ACM Symposium on Principles of Distributed Computing

July 13 - 16, 2003

Massachusetts, Boston

Acceptance Rates

PODC '03 Paper Acceptance Rate 51 of 226 submissions, 23%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
403
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Patel RAwasthi LGovil MRachita (2023)n-Layer Platform for Hi-Tech WorldRole of Data-Intensive Distributed Computing Systems in Designing Data Solutions10.1007/978-3-031-15542-0_5(83-96)Online publication date: 26-Jan-2023
https://doi.org/10.1007/978-3-031-15542-0_5
Oliveira FTjang ABianchini RMartin RNguyen TMorin CMuller G(2010)BarricadeProceedings of the 5th European conference on Computer systems10.1145/1755913.1755924(83-96)Online publication date: 13-Apr-2010
https://dl.acm.org/doi/10.1145/1755913.1755924
YAMAUCHI YKAMEI SOOSHITA FKATAYAMA YKAKUGAWA HMASUZAWA T(2009)Hierarchical Composition of Self-Stabilizing Protocols Preserving the Fault-Containment PropertyIEICE Transactions on Information and Systems10.1587/transinf.E92.D.451E92-D:3(451-459)Online publication date: 2009
https://doi.org/10.1587/transinf.E92.D.451
Kutten SMasuzawa T(2007)Output Stability Versus Time Till OutputDistributed Computing10.1007/978-3-540-75142-7_27(343-357)Online publication date: 2007
https://doi.org/10.1007/978-3-540-75142-7_27
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
Yamauchi YKamei SOoshita FKatayama YKakugawa HMasuzawa T(2006)Composition of fault-containing protocols based on recovery waiting fault-containing composition frameworkProceedings of the 8th international conference on Stabilization, safety, and security of distributed systems10.5555/1759076.1759114(516-532)Online publication date: 17-Nov-2006
https://dl.acm.org/doi/10.5555/1759076.1759114
Beauquier JDelaët, SHaddad S(2006)A 1-strong self-stabilizing transformerProceedings of the 8th international conference on Stabilization, safety, and security of distributed systems10.5555/1759076.1759085(95-109)Online publication date: 17-Nov-2006
https://dl.acm.org/doi/10.5555/1759076.1759085
Keidar ISchuster A(2006)Want scalable computing?ACM SIGACT News10.1145/1165555.116556937:3(59-66)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1145/1165555.1165569
Birk YKeidar ILiss LSchuster AWolff RRuppert EMalkhi D(2006)Veracity radiusProceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing10.1145/1146381.1146399(102-111)Online publication date: 23-Jul-2006
https://dl.acm.org/doi/10.1145/1146381.1146399
Arora AZhang H(2006)LSRPIEEE/ACM Transactions on Networking10.1109/TNET.2006.87617914:3(520-531)Online publication date: 1-Jun-2006
https://dl.acm.org/doi/10.1109/TNET.2006.876179
Show More Cited By

View Options

Get Access

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents