Blockchains are decentralized and immutable ledgers that ensure secure transaction recording. In these systems, the atomic broadcast is pivotal, ensuring consistent transaction delivery to all participants. It ensures either all nodes receive a transaction or none, preserving ledger integrity. This paper addresses the atomic broadcast problem in asynchronous systems. The existing atomic broadcast protocols sufer from relying on strong temporal assumptions and generating a significant number of messages. In response, we propose a novel protocol based on the rotating coordinator principle for message ordering and the ♢ failure detector for fault tolerance. It has been demonstrated that ♢ is the minimal and suficient class of failure detectors to solve the atomic broadcast in asynchronous systems. Simulation results, conducted using the Neko simulator, demonstrate significant enhancements in latency and message throughput compared to two existing protocols, implemented within the same simulator. The robustness and eficiency of the proposed solution are convincingly demonstrated through extensive simulations. This research contributes valuable insights into enhancing the reliability and performance of atomic broadcast protocols, crucial for the development of resilient and scalable distributed systems in blockchain technology and beyond.
CEUR ceur-ws.org
systems, combined with the dificulty of providing global system control and the presence of
failures (crashes or byzantine). This dificulty is significantly reduced by relying on group
communication primitives that ofer better guarantees than standard point-to-point communication.
In these systems, the atomic broadcast (with reduction to consensus) is pivotal, ensuring
consistent transaction delivery to all participants. It ensures either all nodes receive a transaction or
none, preserving the systems integrity [
Several algorithms solving the atomic broadcast problem in a distributed systems have been
proposed in the literature. These algorithms can be classified according to two main criteria: The
message ordering approach and the fault tolerance mechanism implemented [
This paper presents a new atomic broadcast protocol for all types of asynchronous distributed
systems. The protocol is based on the utilization of unreliable failure detectors ♢ for fault
tolerance [
The paper is structured as follows. Section 2 surveys some related work. Section 3 introduces the system model and, formally, defines the concepts. Then, Section 4 presents the proposed atomic broadcast protocol and Section 5 proves its correctness. Section 6 evaluates the performances of the proposed protocol. Finally, Section 7 concludes the paper.
In [
Two classes of atomic broadcast protocols have been identified according to the ordering of messages and the fault tolerance mechanism used. Token-based solutions rely on the ring structure of processes to transmit the order information handled by a token. They have been divided into two classes according to the fault tolerance mechanism used: [10], [11], [12] are based on group membership service while [13], [14] are failure detector based protocols.
In [
In blockchain systems, the atomic broadcast protocols tolerate Byzantine failures when the processes are distributed across a decentralized network of nodes. These protocols ensure fault tolerance, allowing the system to maintain the consistency and integrity of data even in the presence of malicious processes or Byzantine faults [16], [17], [18], [19], [20].
In this section, we present the system model and some definitions related to our study.
We consider an asynchronous distributed system composed of a set Π = { 0, …, −1 } of processes, connected by reliable communication channels forming a fully connected network. Processes can only tolerate failures by permanent crashes. We assume a majority of correct processes ( < /2 ; where represents the maximum number of faulty processes). The system is augmented with the unreliable failure detector ♢ .
Informally, a failure detector consists of a set of modules, each attached to a process: The
module attached to a process maintains a set of suspected faulty processes. A failure detector
is considered unreliable because it may suspect a correct process as well as fail to suspect a
genuinely faulty process. Chandra and Toueg [
Chandra et al. [9] showed that ♢ is the weakest class of failure detectors and is the minimal and necessary class to solve the atomic broadcast problem in an asynchronous distributed system (by reduction to the consensus problem).
This problem ensures an atomic delivery of messages to the processes of the system (a message
sent by a process is received by all processes) [
The atomic broadcast is an extension of the reliable broadcast. In addition to ensuring that
all processes receive the same number of messages (reliable broadcast), it also ensures the
same delivery order of these messages [
Each correct process, participating in the atomic broadcast protocol, emits and receives messages of various types: 4.
tasks. 1. : To elect the new coordinator for the current round; 2. : When the process wants to cancel the processing done during the current round; 3. : As soon as the coordinator receives a suficient number of votes, it broadcasts this message to inform the other processes of its decision regarding the order of the message list to be atomically delivered.
: A simple message broadcast by a correct process to participate in the application The first three messages are control messages, while the last message leads to a system evolution (its execution). To achieve this, a process manipulates the following data structures: • _ : A list containing the messages identifiers ( ) and it does not allow duplication of elements. • : A data structure composed of two integers, the first representing the message sender number and the second is the timestamp of this message. The use of this structure guarantees the uniqueness of broadcast messages. • • • • • • identifiers ( ∀ ∈ Π : _
[] = ? ).
_ : The list of broadcast messages that have not been yet ordered.
: An integer representing the current round, initially set to zero. _
: An array of integers containing the votes of the processes according to their : An integer containing the number of positive votes (vote=1) present in : An integer containing the number of negative votes (vote=2) present in _ _ .
.
: A list containing all messages belonging to rounds succeeding the current round.
The section is devoted to the description and the algorithm of the proposed solution.
The principle of the protocol is quite straightforward. It operates in a series of asynchronous rounds. During each round, a process is elected (rotating coordinator) to enforce the list of messages to be delivered by all correct processes. The algorithm relies on the use of the failure detector ♢ to provide the list of faulty processes in the system. To achieve this, the use of communication primitives, reliable broadcast, is paramount to ensure messages sending and receiving. The algorithm unfolds in two tasks: 1. Task1: It consists of two phases: a) Phase1: Each process broadcasts its messages by invoking the − primitive (which is the indirect implementation of − ). b) Phase2: During this phase, each process must vote for one of two values: (1) If it does not suspect the coordinator process ; (2) If it suspects it to be faulty based on the list of faulty processes provided by the failure detector ♢ attached to this process. The process can only cast one vote during a round. 2. Task2: Upon receiving a message , the process must perform one of the following treatments depending on the type of the received message: a) is a simple message: adds to its _ and places the message identifier _ and its local variables and . in _
. b) is a vote message: updates
Two cases can be considered: • • its
_ . ≥ ( − ) : broadcasts a
message to start a new round.
≥ ( − ) and is the coordinator: In this case, decides and broadcasts c) ∈
_ : If the round number of ( delivers its recorded messages in the imposed order and initiates a new round. However, if ) is equal to the current round, _ according to the coordinator is greater than the current round, the process adds the message to the temporary list . d) is a
message: If round. However, if message to the temporary list
.
is equal to the current round, initiates a new is greater than the current round, the process adds the
Lemma 1. If a process delivers a message , then has been broadcast by at least one process (validity property).
Proof. The use of reliable broadcast primitives ensures this lemma.
Lemma 2. If a correct process delivers a message , then inevitably all correct processes deliver (agreement property).
Proof. The use of the reliable broadcast primitives ensures that inevitably all processes deliver the same set of messages or none of them. By using the coordinator principle, we ensure that any message sent by a correct process will be delivered by all correct processes as soon as the coordinator broadcasts its final ordered list of messages.
Lemma 3. For any message , each correct process delivers the message at most once, and only if has previously been broadcast by a certain correct process (integrity property). Proof. This property is guaranteed by the use of the reliable broadcast primitives.
Lemma 4. If two correct processes and deliver two messages and ′, then delivers before ′ if, and only if, delivers before ′ (total order property).
Proof. This property is guaranteed by broadcasting the coordinator list of messages. Once a process is elected as the coordinator of the current round, it will impose its list of messages to be atomically delivered by all the correct processes. This list will be broadcast to the processes through the reliable broadcast primitive − . Therefore, all correct processes will deliver their messages according to the order imposed by the coordinator, which will be the same for every process.
Theorem.The algorithm in Algorithm 1 implements the primitives of the atomic broadcast.
In this section, we evaluate the performance of the proposed protocol. To do so, we utilize a well-known simulator in distributed systems, Neko [21].
In our work, we employ the same simulation model as [22] Fig. 1.
The parameter ( ≥ 0 ) indicates the relative speed of processing a message on a process compared to its transmission on the network. Diferent values for modeling the network environment were chosen ( = 0.1, = 1, = 10). The values of are selected based on the approach followed in [23]: • = 1: Indicates that the processor processing and network transmission have the same cost; • = 10: Indicates that the processor processing is higher compared to network transmis• = 0.1: Indicates that network transmission is higher compared to processor processing.
In this section, we present the simulation results obtained by comparing the proposed protocol
with two other protocols existing in the literature [
=1 =
(∑ ) − Where:
). • ∈ 0, 1, ..., − 1 : Represents the number of processes in the system; • : Represents the time of broadcasting − () • : Represents the time of consumption − () ; (message validation by the process 6.2.2. Execution without process crashes In this section, we present the simulation results in terms of latency/ throughput. We consider a number of processes = 5 for our proposal and that of 96 , and = 7 for 11 , 1, while varying the values of (0.1, 1, 10), in a scenario without process failures.
Through the obtained results in Fig. 2, Fig. 3, and Fig. 4, we notice that our proposal outperforms in terms of latency compared to 96 and 11 . In the case where = 0.1 , our proposal practically overlaps with that of 11 . As soon as the throughput exceeds 800 msgs/s (Fig. 4), the protocol 11 reaches its limits, unlike our protocol which experiences a considerable increase but remains operational. 6.2.3. Execution with process crashes In this section, we present the simulation results in terms of latency and throughput. We consider = 5 as the total number of processes for our proposal, = 7 for 11 , and = 2 as the maximum number of crashed processes for both protocols. We also vary the values of (0.1, 1, 10) in an environment with process failures.
Through the obtained results in Fig. 5, Fig. 6, and Fig. 7, we observe that 11 outperforms
our proposal in the case of low throughput. However, once this throughput exceeds a certain
threshold, the latency of our protocol improves significantly, while the protocol of 11
becomes non-operational.
1Since the number of processes required to support two failures is = 7 in [13], and = 5 in our proposal and [
This paper proposed a distributed protocol addressing the atomic broadcast problem in an asynchronous system. This protocol combines two approaches for message ordering and fault tolerance, including the rotating coordinator principle and the unreliable failure detector ♢ . Through simulation results obtained using the distributed systems simulator Neko, we observed that our proposal exhibits a remarkable improvement in terms of protocol latency and the number of messages generated compared to two other reference protocols implemented in the same simulator.
[9] T. Chandra, V. Hadzilacos, S. Toueg, The weakest failure detector for solving consensus,
Journal of the ACM (JACM) 43 (1996) 685–722. [10] J. Chang, N. Maxemchuk, Reliable broadcast protocols, ACM Transactions on Computer
Systems (TOCS) 2 (1984) 251–273. [11] Y. Amir, L. Moser, P. Melliar-Smith, D. Agarwal, P. Ciarfella, The totem single-ring ordering and membership protocol, ACM Transactions on Computer Systems (TOCS) 13 (1995) 311–342. [12] P. Jalili-Marandi, M. Primi, N. Schiper, F. Pedone, Ring paxos: High-throughput atomic broadcast, The Computer Journal 60 (2017) 866–882. [13] R. Ekwall, A. Schiper, A fault-tolerant token-based atomic broadcast algorithm, IEEE
Transactions on Dependable and Secure Computing 8 (2011) 625–639. [14] N. Rebouh, A. Ifeticene, N. Aidoun, L. Bouallouche-Medjkoune, Failure detector-ring paxos-based atomic broadcast algorithm, International Journal of Critical Computer-Based Systems 7 (2017) 78–90. [15] A. Mostefaoui, M. Raynal, Low cost consensus-based atomic broadcast, in: Proceedings. 2000 Pacific Rim International Symposium on Dependable Computing, IEEE, 2000, pp. 45–52. [16] M. Yin, D. Malkhi, M. K. Reiter, G. Gueta, I. Abraham, Hotstuf: Bft consensus with linearity and responsiveness, in: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019, pp. 347–356. [17] R. Kotla, L. Alvisi, M. Dahlin, A. Clement, E. Wong, Zyzzyva: speculative byzantine fault tolerance, in: Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, 2007, pp. 45–58. [18] S. Liu, P. Viotti, C. Cachin, V. Quema, M. Vukolic, {XFT}: Practical fault tolerance beyond crashes, in: 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), 2016, pp. 485–500. [19] Y. Gilad, R. Hemo, S. Micali, G. Vlachos, N. Zeldovich, Algorand: Scaling byzantine agreements for cryptocurrencies, in: Proceedings of the 26th symposium on operating systems principles, 2017, pp. 51–68. [20] M. Castro, B. Liskov, et al., Practical byzantine fault tolerance, in: OsDI, volume 99, 1999, pp. 173–186. [21] P. Urban, X. Defago, A. Schiper, Neko: A single environment to simulate and prototype distributed algorithms, in: Proceedings 15th International Conference on Information Networking, IEEE, 2001, pp. 503–511. [22] P. Urban, X. Defago, A. Schiper, Contention-aware metrics for distributed algorithms: Comparison of atomic broadcast algorithms, in: Proceedings Ninth International Conference on Computer Communications and Networks (Cat. No. 00EX440), IEEE, 2000, pp. 582–589. [23] P. Urban, I. Shnayderman, A. Schiper, Comparison of failure detectors and group membership: Performance study of two atomic broadcast algorithms, in: 2003 International Conference on Dependable Systems and Networks, 2003. Proceedings., IEEE Computer Society, 2003, pp. 645–645.