| 1. |
- Duvignau, Romaric, 1989, et al.
(författare)
-
Self-stabilizing Byzantine Fault-Tolerant Repeated Reliable Broadcast
- 2022
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Cham : Springer International Publishing. - 1611-3349 .- 0302-9743. ; 13751 LNCS, s. 206-221
-
Konferensbidrag (refereegranskat)abstract
- We study a well-known communication abstraction called Byzantine Reliable Broadcast (BRB). This abstraction is central in the design and implementation of fault-tolerant distributed systems, as many fault-tolerant distributed applications require communication with provable guarantees on message deliveries. Our study focuses on fault-tolerant implementations for message-passing systems that are prone to process-failures, such as crashes and malicious behaviors. At PODC 1983, Bracha and Toueg, in short, BT, solved the BRB problem. BT has optimal resilience since it can deal with up to t< n/ 3 Byzantine processes, where n is the number of processes. The present work aims at the design of an even more robust solution than BT by expanding its fault-model with self-stabilization, a vigorous notion of fault-tolerance. In addition to tolerating Byzantine and communication failures, self-stabilizing systems 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 remains intact). We propose, to the best of our knowledge, the first self-stabilizing Byzantine fault-tolerant (SSBFT) solution for repeated BRB (that follows BT’s specifications) in signature-free message-passing systems. Our contribution includes a self-stabilizing variation on a BT that solves asynchronous single-instance BRB. We also consider the problem of recycling instances of single-instance BRB. Our SSBFT recycling for time-free systems facilitates the concurrent handling of a predefined number of BRB invocations and, by this way, can serve as the basis for SSBFT consensus.
|
|
| 2. |
- Duvignau, Romaric, 1989, et al.
(författare)
-
Self-stabilizing Byzantine fault-tolerant repeated reliable broadcast
- 2023
-
Ingår i: Theoretical Computer Science. - 0304-3975. ; 972
-
Tidskriftsartikel (refereegranskat)abstract
- We study a well-known communication abstraction called Byzantine Reliable Broadcast (BRB). This abstraction is central in the design and implementation of fault-tolerant distributed systems, as many fault-tolerant distributed applications require communication with provable guarantees on message deliveries. Our study focuses on fault-tolerant implementations for message-passing systems that are prone to process-failures, such as crashes and malicious behavior. At PODC 1983, Bracha and Toueg, in short, BT, solved the BRB problem. BT has optimal resilience since it can deal with t
|
|
| 3. |
- Duvignau, Romaric, 1989, et al.
(författare)
-
Self-stabilizing Byzantine Multivalued Consensus: (extended abstract)
- 2024
-
Ingår i: ACM International Conference Proceeding Series. - 9798400716737 ; , s. 12-21
-
Konferensbidrag (refereegranskat)abstract
- Consensus, abstracting a myriad of problems in which processes have to agree on a single value, is one of the most celebrated problems of fault-tolerant distributed computing. Consensus applications include fundamental services for the environments of the Cloud and Blockchain, and in such challenging environments, malicious behaviors are often modeled as adversarial Byzantine faults. At OPODIS 2010, Mostéfaoui and Raynal (in short MR) presented a Byzantine-tolerant solution to consensus in which the decided value cannot be a value proposed only by Byzantine processes. MR has optimal resilience coping with up to t < n/3 Byzantine nodes over n processes. MR provides this multivalued consensus object (which accepts proposals taken from a finite set of values) assuming the availability of a single Binary consensus object (which accepts proposals taken from the set {0, 1}). This work, which focuses on multivalued consensus, aims at the design of an even more robust solution than MR. Our proposal expands MR's fault-model with self-stabilization, a vigorous notion of fault-tolerance. In addition to tolerating Byzantine, self-stabilizing systems can automatically 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 (provided that the algorithm code remains intact). To the best of our knowledge, we propose the first self-stabilizing solution for intrusion-tolerant multivalued consensus for asynchronous message-passing systems prone to Byzantine failures. Our solution has a Math 1 stabilization time from arbitrary transient faults.
|
|
| 4. |
- Georgiou, C., et al.
(författare)
-
Loosely-self-stabilizing Byzantine-Tolerant Binary Consensus for Signature-Free Message-Passing Systems
- 2021
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Cham : Springer International Publishing. - 1611-3349 .- 0302-9743. ; 12754 LNCS, s. 36-53
-
Konferensbidrag (refereegranskat)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 scheduling is fair and independent from random numbers, MMR is optimal in several respects: it deals with up to t Byzantine processes, where t< n/ 3, n being the number of processes, O(n2) messages, and O(1 ) expected time. The present article presents a non-trivial extension of MMR to an even more fault-prone context, namely, in addition to Byzantine processes, it considers also that the system can experience transient failures. To this end it considers self-stabilization techniques to cope with communication failures and arbitrary transient faults, i.e., any violation of the assumptions according to which the system was designed to operate. The proposed algorithm is the first loosely-self-stabilizing Byzantine fault-tolerant binary consensus algorithm suited to asynchronous message-passing systems. This is achieved via an instructive transformation of MMR to a loosely-self-stabilizing solution that can violate safety requirements with probability Pr = O(1 / (2 M) ), where M is a predefined constant that can be set to any positive integer at the cost of 3 Mn+ log M bits of local memory. In addition to making MMR resilient to transient faults, the obtained loosely-self-stabilizing algorithm preserves its properties of optimal resilience and termination, i.e., t< n/ 3 and O(1 ) expected time. Furthermore, it only requires a bounded amount of memory.
|
|
| 5. |
- Georgiou, C., et al.
(författare)
-
Self-stabilizing Byzantine-Tolerant Recycling
- 2023
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - 1611-3349 .- 0302-9743. ; 14310 LNCS, s. 518-535
-
Konferensbidrag (refereegranskat)abstract
- Numerous distributed applications, such as cloud computing and distributed ledgers, necessitate the system to invoke asynchronous consensus objects for an unbounded number of times, where the completion of one consensus instance is followed by the invocation of another. With only a constant number of objects available, object reuse becomes vital. We investigate the challenge of object recycling in the presence of Byzantine processes, which can deviate from the algorithm code in any manner. Our solution must also be self-stabilizing, as it is a powerful notion of fault tolerance. Self-stabilizing systems can recover automatically after the occurrence of arbitrary transient-faults, in addition to tolerating communication and (Byzantine or crash) process failures, provided the algorithm code remains intact. We provide a recycling mechanism for asynchronous objects that enables their reuse once their task has ended, and all non-faulty processes have retrieved the decided values. This mechanism relies on synchrony assumptions and builds on a new self-stabilizing Byzantine-tolerant synchronous multivalued consensus algorithm, along with a novel composition of existing techniques.
|
|
| 6. |
- Lundström, Oskar, et al.
(författare)
-
Brief Announcement: Self-stabilizing Total-Order Broadcast
- 2022
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Cham : Springer International Publishing. - 1611-3349 .- 0302-9743. ; 13751 LNCS, s. 358-363
-
Konferensbidrag (refereegranskat)abstract
- Our study aims at the design of an even more reliable solution. 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 total-order (uniform reliable) broadcast for asynchronous message-passing systems prone to process failures and transient faults. As we show, the proposed solution facilitates the elegant construction of self-stabilizing state-machine replication using bounded memory.
|
|
| 7. |
- Lundström, Oskar, et al.
(författare)
-
Self-Stabilizing Indulgent Zero-degrading Binary Consensus
- 2021
-
Ingår i: ACM International Conference Proceeding Series. - New York, NY, USA : ACM. ; , s. 106-115
-
Konferensbidrag (refereegranskat)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.
|
|
| 8. |
- Lundström, Oskar, et al.
(författare)
-
Self-stabilizing indulgent zero-degrading binary consensus
- 2024
-
Ingår i: Theoretical Computer Science. - 0304-3975. ; 989
-
Tidskriftsartikel (refereegranskat)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 recovers within a finite time after the occurrence of the last arbitrary transient fault. 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.
|
|
| 9. |
- Lundström, Oskar, et al.
(författare)
-
Self-stabilizing Multivalued Consensus in Asynchronous Crash-prone Systems
- 2021
-
Ingår i: Proceedings - 2021 17th European Dependable Computing Conference, EDCC 2021. ; , s. 111-118
-
Konferensbidrag (refereegranskat)abstract
- The problem of multivalued consensus is fundamental in the area of fault-tolerant distributed computing since it abstracts a very broad set of agreement problems in which processes have to uniformly decide on a specific value v\in V, where V ≥ 2. Existing solutions (that tolerate process failures) reduce the multivalued consensus problem to the one of binary consensus, e.g., Mostéfaoui-Raynal-Tronel and Zhang-Chen. Our study aims at the design of an even more reliable solution. 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 (a finite number 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 multivalued consensus for asynchronous message-passing systems prone to process failures and arbitrary transient-faults. Our solution is also the first (to the best of our knowledge) to support wait-freedom. Moreover, using piggybacking techniques, our solution can invoke n binary consensus objects concurrently. Thus, the proposed self-stabilizing wait-free solution can terminate using fewer binary consensus objects than earlier non-self-stabilizing solutions by Mostéfaoui, Raynal, and Tronel, which uses an unbounded number of binary consensus objects, or Zhang and Chen, which is not wait-free.
|
|
| 10. |
- Lundström, Oskar, et al.
(författare)
-
Self-stabilizing SET-constrained delivery broadcast
- 2020
-
Ingår i: Proceedings - International Conference on Distributed Computing Systems. ; 2020-November, s. 617-627
-
Konferensbidrag (refereegranskat)abstract
- Fault-tolerant distributed applications require communication abstractions with provable guarantees on message deliveries. For example, Set-Constrained Delivery Broadcast (SCD-broadcast) is a communication abstraction for broadcasting messages in a manner that, if a process delivers a set of messages that includes m and later delivers a set of messages that includes m, no process delivers first a set of messages that includes m and later a set of messages that includes m. Imbs et al. proposed this communication abstraction and its first implementation. They have demonstrated that SCD-broadcast has the computational power of read/write registers and allows for an easy building of distributed objects such as snapshot objects and consistent counters. Imbs et al. focused on fault-tolerant implementations for asynchronous message-passing systems that are prone to process crashes. This paper aims to design an even more robust SCD-broadcast communication abstraction, namely a self-stabilizing SCD-broadcast. In addition to process 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 self-stabilizing SCD-broadcast algorithm for asynchronous message-passing systems that are prone to process crash failures. The proposed self-stabilizing SCD-broadcast algorithm has an O(1) stabilization time (in terms of asynchronous cycles). The communication costs of our algorithm are similar to the ones of the non-self-stabilizing state-of-the-art. The main differences are that our proposal considers repeated gossiping of O(1) bits messages and deals with bounded space (which is a prerequisite for self-stabilization). We advance the state-of-the-art also by two new self-stabilizing applications: an atomic construction of snapshot objects and sequentially consistent counters.
|
|
