We introduced definitions for consensus, Byzantine Broadcast (BB) and Byzantine Agreement (BA), in an earlier post. In this post, we discuss how consensus protocols are used in State Machine Replication (SMR), a fundamental approach in distributed computing for building fault-tolerant systems. We 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...
[Read More]
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 flavors: GST and Unknown Latency. In this post we discuss:
[Read More]
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]
The Dolev and Reischuk Lower Bound: Does Agreement need Quadratic Messages?
How scalable is Byzantine agreement? Does solving agreement require non-faulty parties to send a quadratic number of messages in the number of potential faults? In this post, we highlight the Dolev and Reischuk lower bound from 1982 that addresses this fundamental question.
[Read More]
Byzantine Agreement is Impossible for $n \leq 3 f$ if the Adversary can Simulate
The Fischer, Lynch, and Merritt, 1985 lower bound states that Byzantine agreement is impossible if the adversary controls $f>n/3$ parties. It is well known that this lower bound does not hold if there is a PKI setup.
[Read More]
The Trusted Setup Phase
co-authored with Avishay Yanai
[Read More]
Do Bitcoin and Ethereum have any trusted setup assumptions?
What is Consensus?
Consensus broadly means different parties reaching agreement. In distributed computing, Consensus is a core functionality. In this post, we define the consensus problem and its variants.
[Read More]
Byzantine Agreement is impossible for $n \leq 3 f$ under partial synchrony
Lower bounds in distributed computing are very helpful. They prevent us from wasting time on impossible tasks :-). More importantly, they help us focus on what is optimally possible or how to circumvent them by altering assumptions or problem formulation.
[Read More]
What is the difference between PBFT, Tendermint, SBFT and HotStuff ?
In this post I will try to compare four of my favorite protocols for Byzantine Fault Tolerant (BFT) State Machine Replication (SMR):
[Read More]
The threshold adversary
In addition to limiting the adversary via a communication model synchrony, asynchrony, or partial synchrony, we need a way to limit the adversary’s power to corrupt parties.
[Read More]
The power of the adversary
After we fix the communication model, synchrony, asynchrony, or partial synchrony, and a threshold adversary there are still five important modeling decisions regarding the adversary’s power:
[Read More]
Synchrony, Asynchrony and Partial synchrony
In the standard distributed computing model, communication uncertainty is modeled by an adversary that controls message delays. The communication model defines the limits to the power of the adversary to delay messages.
[Read More]
Where do I even start?
I have been wanting to start a blog for a long time. Here we go!