Synchronous consensus protocols offer a significant advantage over their asynchronous and partially synchronous counterparts by providing higher fault tolerance—an essential benefit in distributed systems, like blockchains, where participants may have incentives to act maliciously. However, despite this advantage, synchronous protocols are often met with skepticism due to concerns about their performance, as the latency of synchronous protocols is tightly linked to a conservative time bound for message delivery.

Gossip-based consensus protocols have been recently proposed to confront the challenges faced by state machine replication in large geographically distributed systems. It is unclear, however, to which extent consensus and gossip communication fit together. On the one hand, gossip communication has been shown to scale to large settings and efficiently handle participant failures and message losses. On the other hand, gossip may slow down consensus. Moreover, gossip's inherent redundancy may be unnecessary since consensus naturally accounts for participant failures and message losses. This paper investigates the suitability of gossip as a communication building block for consensus. We answer three questions: How much overhead does classic gossip introduce in consensus? Can we design consensus-friendly gossip protocols? Would more efficient gossip protocols still maintain the same reliability properties of classic gossip?

Tendermint is the replication engine at the core of Cosmos, a network of proof-of-stake blockchains. In the lifespan of blockchains, Cosmos and Tendermint are mature technologies, currently used by more than a hundred businesses and deployed by hundreds of nodes. The system was designed to provide flexible deployment despite heterogeneous environments, scale performance with the number of nodes, and tolerate misbehaving participants. In this practical experience report, we overview Tendermint's main design goals and architecture, and present a detailed performance evaluation of the system in a realistic environment. We report results from a geographically distributed environment with up to 128 nodes, including failure-free executions and fail-prone scenarios, with both crash and Byzantine failures.

It has been shown that the highest throughput for broadcasting messages in a point-to-point network is achieved with a ring topology. Although several ring-based group communication protocols have benefited from this observation, broadcasting messages along a ring overlay may lead to high latencies: In a system with n processes, at least n-1 communication steps are necessary for all processes to deliver a message. In this work, we argue that it is possible to reach optimal throughput without resorting to a ring topology (or to ip-multicast, typically unavailable in wide-area networks). This can be done by routing messages through different paths, while carefully using the available bandwidth at each process, resulting in a significantly lower latency for every message (potentially a single communication step). Based on this idea, we propose Ridge, a Paxos-based atomic multicast protocol where each message is initially forwarded to a single destination, the distributor, whose responsibility is to propagate the message to all other destinations. To utilize all bandwidth available in the system, processes alternate in the role of distributor. By doing this, the maximum system throughput matches that of ring-based protocols, with a latency that is not significantly dependent on the size of the system. Finally, we show that Ridge can also deliver messages optimistically, with even lower latency.

Many applications today rely on multiple services, whose results are combined to form the application's response. In such contexts, the most unreliable service and the slowest service determine the application's reliability and response time, respectively. State-machine replication and atomic broadcast are fundamental abstractions to build highly available services. In this paper, we consider the latency variability of atomic broadcast protocols. This is important because atomic broadcast has a direct impact on the response time of services. We study four high performance atomic broadcast protocols representative of different classes of protocol design and characterize their latency tail distribution under different workloads. Next, we assess how key design features of each protocol can possibly be related to the observed latency tail distributions. Our observations hint at request batching as a simple yet effective way to shorten the latency tails of some of the studied protocols, an improvement within the reach of application implementers. Indeed, our observation is not only verified experimentally, it allows us to assess which of the protocol's key design principles favor the construction of latency predictable protocols.