Consensus for State Machine Replication

We introduced definitions for consensus, Byzantine Broadcast (BB) and Byzantine Agreement (BA), in an earlier post. In this post, we will discuss how consensus protocols are used in State Machine Replication (SMR). We will compare and contrast this setting to that of traditional BB and BA. A follow up post discusses the reductions from one abstraction to the other in the omission failure model. [Read More]
Tags: dist101

Flavours of Partial Synchrony

This is a follow up post to the post on Synchrony, Asynchrony and Partial synchrony. The partial synchrony model of DLS88 comes in two flavours: GST and Unknown Latency. In this post we discuss: [Read More]
Tags: dist101

Dont Trust. Verify. and Checkpoint?

Imagine that that Aliens land on earth with a new superfast SHA256 machine. Imagine this machine always gives them more than 51% of the current world Bitcoin hash power (but not enough hash power to completely break SHA256). Suppose they decide to build a chain from the Bitcoin Genesis block that is longer than any other chain on earth and put only empty blocks on it. Could they erase all... [Read More]

What is Consensus?

We all broadly understand “consensus” as the notion of different parties agreeing with each other. In distributed computing, Consensus is one of the core functionalities. In this post, we define the consensus problem and discuss some variants and their differences. [Read More]
Tags: dist101

Byzantine Agreement is impossible for $n \leq 3 f$ under partial synchrony

Lower bounds in distributed computing are very helpful. Obviously, they prevent you from wasting time trying to do impossible things :-). Even more importantly, understanding them well often helps in finding ways to focus on what is optimally possible or ways to circumvent them by altering the assumptions or the problem formulation. [Read More]

The threshold adversary

Once we fix the communication model (synchrony, asynchrony, or partial synchrony see here), we then need some way to limit the power of the adversary. [Read More]
Tags: dist101 models

The power of the adversary

Once we fix the communication model (synchrony, asynchrony, or partial synchrony see here), and we fix a threshold adversary we still need to make important modeling decisions about the adversary power. [Read More]
Tags: dist101 models

Synchrony, Asynchrony and Partial synchrony

In the standard distributed computing model, the communication uncertainty is captured by an adversary that can control the message delays. The communication model defines the limits to the power of the adversary to delay messages. [Read More]
Tags: dist101 models

Where do I even start?

I have been wanting to start a blog for a long time. Here we go!