| Full text | |
| Author(s): |
Ruchel, Lucas, V
;
de Camargo, Edson Tavares
;
Rodrigues, Luiz Antonio
;
Turchetti, Rogerio C.
;
Arantes, Luciana
;
Duarte Jr., Elias Procopio
Total Authors: 6
|
| Document type: | Journal article |
| Source: | JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING; v. 184, p. 11-pg., 2023-10-27. |
| Abstract | |
Atomic Broadcast is an essential broadcast primitive as it ensures the consistency of distributed replicas. However, it is notoriously non-scalable. In this work, we introduce the Leaderless Hierarchical Atomic Broadcast (LHABcast) algorithm, which has two properties to improve scalability. First, it is a fully decentralized algorithm that does not rely on a sequencer/leader, which is often a significant bottleneck. Processes running LHABcast send messages with local sequence numbers and order messages received from other processes using timestamps inspired on Lamport's logical clocks. A process that receives the required set of timestamps can make a decision about the overall sequence of message delivery. Second, the algorithm is hierarchical: processes are organized on a vCube logical overlay network, which has several logarithmic properties and allows the construction of autonomous spanning trees. vCube also works as a failure detector, assuming crash faults and an asynchronous system model. In this paper, LHABcast is described, specified, and proven to be correct. Both simulation and experimental results are presented. A comparison with an all-to-all strategy shows that the number of messages sent by LHABcast is significantly lower in both fault-free and faulty scenarios. An implementation of LHABcast in Akka.io achieved up to 3.9 times higher throughput in fault-free scenarios than an implementation of the Raft-based Apache Ratis. (AU) | |
| FAPESP's process: | 21/06923-0 - CINEMA: Intelligent, Scalable, Mobile and Highly-Available Computing in the Internet |
| Grantee: | Elias Procópio Duarte Júnior |
| Support Opportunities: | Regular Research Grants |