Consensus is one of the most fundamental problems in distributed computing. It is important because of it’s role in State Machine Replication (SMR), a generic approach for replicating services that can be modeled as a deterministic state machine. Traditionally, deployments of SMR based systems are in data-center settings (local area network), have a small number of replicas (three to seven) and are typically part of a single administration domain.

More recently, SMR based systems are used in the context of blockchain systems (e.g., Tendermint), which pose a whole new set of challenges on the design and deployment of SMR based systems: reaching agreement over wide area network, among large number of nodes (hundreds or thousands) that are not part of the same administration domain, and where a subset of nodes can behave maliciously (Byzantine faults). Furthermore, contrary to the previous data-center deployments where nodes are fully connected to each other, in blockchain systems, a node is only connected to a subset of other nodes, so communication is achieved by gossip-based peer-to-peer protocols.

Practical consensus algorithms normally consider the partially synchronous system model, where system alternates between asynchronous and synchronous periods. Consensus algorithms are designed to be always safe (even in the presence of asynchrony), and to ensure termination during synchronous periods. Ensuring safety and termination together is very challenging, and consensus algorithms (especially those considering Byzantine faults) are considered very subtle to understand and implement correctly, even by seasoned researchers. One of the reason is a lack of adequate abstractions.

In this talk we will present the Weak Interactive Consistency (WIC), an abstraction that simplifies reasoning about termination of consensus algorithms for Byzantine faults. We will then explain additional safety-related mechanisms of known consensus algorithms in the context of Generic consensus algorithm. Finally, we will explain a novel termination mechanism used in Tendermint that benefits from the gossip based communication on which modern blockchain systems are being built.

**********************

This talk is part of a public seminar series organised within the Master in Financial Technology & Computing

Zarko Milosevic obtained a Doctor of Science (PhD) degree in Distributed Systems from EPFL in 2013. Before PhD, he finished Master in Computer Science at EPFL in 2008 and obtained a dipl.ing. degree in Electrical Engineering (Computer Science) from School of Electrical Engineering, University of Belgrade, in 2006. He worked as a software engineer for several companies in Switzerland. Currently, he works as an Assistant Professor at Singidunum University and as a Research Scientist at Tendermint (https://tendermint.com/). His research interests lies in the broad area of fault-tolerant distributed systems.