More Web Proxy on the site http://driver.im/

research-article

Self-Stabilizing Indulgent Zero-degrading Binary Consensus

Authors:

Oskar Lundström,

Elad Michael SchillerAuthors Info & Claims

ICDCN '21: Proceedings of the 22nd International Conference on Distributed Computing and Networking

Pages 106 - 115

https://doi.org/10.1145/3427796.3427836

Published: 05 January 2021 Publication History

Abstract

Guerraoui proposed an indulgent solution for the binary consensus problem. Namely, he showed that an arbitrary behavior of the failure detector never violates safety requirements even if it compromises liveness. Consensus implementations are often used in a repeated manner. Dutta and Guerraoui proposed a zero-degrading solution, i.e., during system runs in which the failure detector behaves perfectly, a node failure during one consensus instance has no impact on the performance of future instances.

Our study, which focuses on indulgent zero-degrading binary consensus, aims at the design of an even more robust communication abstraction. We do so through the lenses of self-stabilization—a very strong notion of fault-tolerance. In addition to node and communication failures, self-stabilizing algorithms can recover after the occurrence of arbitrary transient faults; these faults represent any violation of the assumptions according to which the system was designed to operate (as long as the algorithm code stays intact).

This work proposes the first, to the best of our knowledge, self-stabilizing algorithm for indulgent zero-degrading binary consensus for time-free message-passing systems prone to detectable process failures. The proposed algorithm has an stabilization time (in terms of asynchronous cycles) from arbitrary transient faults. Since the proposed solution uses an Ω failure detector, we also present the first, to the best of our knowledge, self-stabilizing asynchronous Ω failure detector, which is a variation on the one by Mostéfaoui, Mourgaya, and Raynal.

References

[1]

Marcos Kawazoe Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, and Sam Toueg. 2004. Communication-efficient leader election and consensus with limited link synchrony. In Principles of Distributed Computing, PODC. ACM, 328–337.

[2]

Noga Alon, Hagit Attiya, Shlomi Dolev, Swan Dubois, Maria Potop-Butucaru, and Sébastien Tixeuil. 2015. Practically stabilizing SWMR atomic memory in message-passing systems. J. Comput. Syst. Sci. 81, 4 (2015), 692–701.

[3]

Karine Altisen, Stéphane Devismes, Swan Dubois, and Franck Petit. 2019. Introduction to Distributed Self-Stabilizing Algorithms. Morgan & Claypool Publishers.

[4]

Joffroy Beauquier and Synnöve Kekkonen-Moneta. 1997. Fault-tolerance and self-stabilization: impossibility results and solutions using self-stabilizing failure detectors. Int. J. Systems Science 28, 11 (1997), 1177–1187.

[5]

Michael Ben-Or. 1983. Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols (Extended Abstract). In Proceedings of the Second Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Montreal, Quebec, Canada, August 17-19, 1983. ACM, 27–30.

Digital Library

[6]

Martin Biely, Martin Hutle, Lucia Draque Penso, and Josef Widder. 2007. Relating Stabilizing Timing Assumptions to Stabilizing Failure Detectors Regarding Solvability and Efficiency. In Stabilization, Safety, and Security of Distributed Systems, SSS LNCS, Vol. 4838. Springer. 4–20.

[7]

Kenneth P. Birman and Thomas A. Joseph. 1987. Reliable Communication in the Presence of Failures. ACM Trans. Comput. Syst. 5, 1 (1987), 47–76.

Digital Library

[8]

Peva Blanchard, Shlomi Dolev, Joffroy Beauquier, and Sylvie Delaët. 2014. Practically Self-stabilizing Paxos Replicated State-Machine. In NETYS(LNCS), Vol. 8593. Springer, 99–121.

[9]

Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. 1996. The Weakest Failure Detector for Solving Consensus. J. ACM 43, 4 (1996), 685–722.

Digital Library

[10]

Tushar Deepak Chandra and Sam Toueg. 1996. Unreliable Failure Detectors for Reliable Distributed Systems. J. ACM 43, 2 (1996), 225–267.

Digital Library

[11]

Carole Delporte-Gallet, Stéphane Devismes, and Hugues Fauconnier. 2007. Robust Stabilizing Leader Election. In Stabilization, Safety, and Security of Distributed Systems, SSS LNCS, Vol. 4838. Springer. 219–233.

[12]

Edsger W. Dijkstra. 1974. Self-stabilizing Systems in Spite of Distributed Control. Commun. ACM 17, 11 (1974), 643–644.

Digital Library

[13]

Shlomi Dolev. 2000. Self-Stabilization. MIT Press.

[14]

Shlomi Dolev, Chryssis Georgiou, Ioannis Marcoullis, and Elad Michael Schiller. 2018. Practically-self-stabilizing virtual synchrony. J. Comput. Syst. Sci. 96(2018), 50–73.

[15]

Shlomi Dolev, Ronen I. Kat, and Elad Michael Schiller. 2010. When consensus meets self-stabilization. J. Comput. Syst. Sci. 76, 8 (2010), 884–900.

Digital Library

[16]

Shlomi Dolev, Thomas Petig, and Elad Michael Schiller. 2018. Self-Stabilizing and Private Distributed Shared Atomic Memory in Seldomly Fair Message Passing Networks. CoRR abs/1806.03498(2018).

[17]

Shlomi Dolev and Elad Schiller. 2003. Communication Adaptive Self-Stabilizing Group Membership Service. IEEE Trans. Parallel Distributed Syst. 14, 7 (2003), 709–720.

Digital Library

[18]

Shlomi Dolev and Elad Schiller. 2004. Self-stabilizing group communication in directed networks. Acta Informatica 40, 9 (2004), 609–636.

Digital Library

[19]

Shlomi Dolev, Elad Schiller, and Jennifer L. Welch. 2006. Random Walk for Self-Stabilizing Group Communication in Ad Hoc Networks. IEEE Trans. Mob. Comput. 5, 7 (2006), 893–905.

Digital Library

[20]

Partha Dutta and Rachid Guerraoui. 2002. Fast Indulgent Consensus with Zero Degradation. In Dependable Computing EDCC(LNCS), Vol. 2485. Springer, 191–208.

[21]

Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. 1985. Impossibility of Distributed Consensus with One Faulty Process. J. ACM 32, 2 (1985), 374–382.

Digital Library

[22]

Chryssis Georgiou, Robert Gustafsson, Andreas Lindhé, and Elad Michael Schiller. 2019. Self-stabilization Overhead: A Case Study on Coded Atomic Storage. In 7th Networked Systems, NETYS LNCS, Vol. 11704. Springer. 131–147.

[23]

Chryssis Georgiou, Oskar Lundström, and Elad Michael Schiller. 2019. Self-stabilizing Snapshot Objects for Asynchronous Failure-Prone Networked Systems. In 7th Networked Systems NETYS LNCS, Vol. 11704. Springer. 113–130.

[24]

Rachid Guerraoui. 2000. Indulgent algorithms. In Principles of Distributed Computing, PODC. ACM, 289–297.

[25]

Rachid Guerraoui and Nancy A. Lynch. 2006. A General Characterization of Indulgence. In Stabilization, Safety, and Security of Distributed Systems, SSS(LNCS), Vol. 4280. Springer, 16–34.

[26]

Rachid Guerraoui and Michel Raynal. 2004. The Information Structure of Indulgent Consensus. IEEE Trans. Computers 53, 4 (2004), 453–466.

Digital Library

[27]

Rachid Guerraoui and Michel Raynal. 2007. The Alpha of Indulgent Consensus. Comput. J. 50, 1 (2007), 53–67.

Digital Library

[28]

Vassos Hadzilacos and Sam Toueg. 1994. A Modular Approach to Fault-Tolerant Broadcasts and Related Problems. Technical Report. Cornell Univ., Ithaca, NY.

[29]

Michel Hurfin, Achour Mostéfaoui, and Michel Raynal. 2002. A Versatile Family of Consensus Protocols Based on Chandra-Toueg’s Unreliable Failure Detectors. IEEE Trans. Computers 51, 4 (2002), 395–408.

Digital Library

[30]

Martin Hutle and Josef Widder. 2005. On the Possibility and the Impossibility of Message-Driven Self-stabilizing Failure Detection. In Self-Stabilizing Systems, SSS(LNCS), Vol. 3764. Springer, 153–170.

[31]

Martin Hutle and Josef Widder. 2005. Self-Stabilizing Failure Detector Algorithms. In Parallel and Distributed Computing and Networks, IASTED, Thomas Fahringer and M. H. Hamza (Eds.). IASTED/ACTA Press, 485–490.

[32]

Idit Keidar and Sergio Rajsbaum. 2003. A simple proof of the uniform consensus synchronous lower bound. Inf. Process. Lett. 85, 1 (2003), 47–52.

Digital Library

[33]

Leslie Lamport. 1998. The Part-Time Parliament. ACM Trans. Comput. Syst. 16, 2 (1998), 133–169.

Digital Library

[34]

Oskar Lundström, Michel Raynal, and Elad M. Schiller. 2020. Self-stabilizing Indulgent Zero-degrading Binary Consensus. In CoRR abs/2010.05489.

[35]

Oskar Lundström, Michel Raynal, and Elad Michael Schiller. 2020. Self-stabilizing Set-Constraint Delivery Broadcast. In 40th IEEE International Conference on Distributed Computing Systems, (ICDCS). To appear.

[36]

Oskar Lundström, Michel Raynal, and Elad M. Schiller. 2020. Self-stabilizing Uniform Reliable Broadcast. In Networked Systems and CoRR abs/2001.03244.

[37]

Achour Mostéfaoui, Eric Mourgaya, and Michel Raynal. 2003. Asynchronous Implementation of Failure Detectors. In Dependable Systems and Networks DSN. IEEE Computer Society, 351–360.

[38]

Michel Raynal. 2018. Fault-Tolerant Message-Passing Distributed Systems - An Algorithmic Approach. Springer.

[39]

Iosif Salem and Elad Michael Schiller. 2018. Practically-Self-stabilizing Vector Clocks in the Absence of Execution Fairness. In 6th Networked Systems NETYS(LNCS), Vol. 11028. Springer, 318–333.

[40]

Robbert van Renesse and Deniz Altinbuken. 2015. Paxos Made Moderately Complex. ACM Comput. Surv. 47, 3 (2015), 42:1–42:36.

[41]

Weigang Wu, Jiannong Cao, Jin Yang, and Michel Raynal. 2008. Using asynchrony and zero degradation to speed up indulgent consensus protocols. J. Parallel Distributed Comput. 68, 7 (2008), 984–996.

Digital Library

Cited By

Lundström ORaynal MSchiller E(2024)Self-stabilizing Multivalued Consensus in Asynchronous Crash-prone SystemsTheoretical Computer Science10.1016/j.tcs.2024.114886(114886)Online publication date: Sep-2024
https://doi.org/10.1016/j.tcs.2024.114886
Lundström ORaynal MSchiller E(2024)Self-Stabilizing Indulgent Zero-degrading Binary ConsensusTheoretical Computer Science10.1016/j.tcs.2024.114387(114387)Online publication date: Jan-2024
https://doi.org/10.1016/j.tcs.2024.114387
Duvignau RRaynal MSchiller E(2023)Self-stabilizing Byzantine fault-tolerant repeated reliable broadcastTheoretical Computer Science10.1016/j.tcs.2023.114070972(114070)Online publication date: Sep-2023
https://doi.org/10.1016/j.tcs.2023.114070
Show More Cited By

Recommendations

Self-stabilizing indulgent zero-degrading binary consensus
Abstract
Guerraoui proposed an indulgent solution for the binary consensus problem. Namely, he showed that an arbitrary behavior of the failure detector never violates safety requirements even if it compromises liveness. Consensus implementations are ...
Highlights
- We consider asynchronous message-passing systems that are prone to node failures, such as crashes.
- We provide the first self-stabilizing solution for Binary consensus, which can recover after the last occurrence of a transient fault.
Loosely-self-stabilizing Byzantine-Tolerant Binary Consensus for Signature-Free Message-Passing Systems
Networked Systems
Abstract
At PODC 2014, A. Mostéfaoui, H. Moumen, and M. Raynal presented a new and simple randomized signature-free binary consensus algorithm (denoted here as MMR) that copes with the net effect of asynchrony and Byzantine behaviors. Assuming message ... $^{}$
$^{}$
Self-Stabilizing Snapshot Objects for Asynchronous Failure-Prone Networked Systems
PODC '19: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing

A snapshot object simulates the behavior of an array of single-writer/multi-reader shared registers that can be read atomically. Delporte-Gallet et al. proposed two fault-tolerant algorithms for snapshot objects in asynchronous crash-prone message-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICDCN '21: Proceedings of the 22nd International Conference on Distributed Computing and Networking

January 2021

252 pages

ISBN:9781450389334

DOI:10.1145/3427796

Copyright © 2021 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 January 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

ICDCN '21

ICDCN '21: International Conference on Distributed Computing and Networking 2021

January 5 - 8, 2021

Nara, Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
43
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lundström ORaynal MSchiller E(2024)Self-stabilizing Multivalued Consensus in Asynchronous Crash-prone SystemsTheoretical Computer Science10.1016/j.tcs.2024.114886(114886)Online publication date: Sep-2024
https://doi.org/10.1016/j.tcs.2024.114886
Lundström ORaynal MSchiller E(2024)Self-Stabilizing Indulgent Zero-degrading Binary ConsensusTheoretical Computer Science10.1016/j.tcs.2024.114387(114387)Online publication date: Jan-2024
https://doi.org/10.1016/j.tcs.2024.114387
Duvignau RRaynal MSchiller E(2023)Self-stabilizing Byzantine fault-tolerant repeated reliable broadcastTheoretical Computer Science10.1016/j.tcs.2023.114070972(114070)Online publication date: Sep-2023
https://doi.org/10.1016/j.tcs.2023.114070
Georgiou CRaynal MSchiller E(2023)Self-stabilizing Byzantine-Tolerant RecyclingStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-44274-2_39(518-535)Online publication date: 30-Sep-2023
https://doi.org/10.1007/978-3-031-44274-2_39
Raynal M(2023)A Short Visit to Distributed Computing Where Simplicity Is Considered a First Class PropertyThe French School of Programming10.1007/978-3-031-34518-0_3(47-67)Online publication date: 11-Oct-2023
https://doi.org/10.1007/978-3-031-34518-0_3
Lundström ORaynal MSchiller E(2022)Brief Announcement: Self-stabilizing Total-Order BroadcastStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-21017-4_27(358-363)Online publication date: 15-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-21017-4_27
Duvignau RRaynal MSchiller E(2022)Self-stabilizing Byzantine Fault-Tolerant Repeated Reliable BroadcastStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-21017-4_14(206-221)Online publication date: 15-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-21017-4_14
Lundstrom ORaynal MSchiller E(2021)Self-stabilizing Multivalued Consensus in Asynchronous Crash-prone Systems2021 17th European Dependable Computing Conference (EDCC)10.1109/EDCC53658.2021.00023(111-118)Online publication date: Sep-2021
https://doi.org/10.1109/EDCC53658.2021.00023
Georgiou CMarcoullis IRaynal MSchiller E(2021)Loosely-self-stabilizing Byzantine-Tolerant Binary Consensus for Signature-Free Message-Passing SystemsNetworked Systems10.1007/978-3-030-91014-3_3(36-53)Online publication date: 19-May-2021
https://dl.acm.org/doi/10.1007/978-3-030-91014-3_3

View Options

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.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents