This page is a dynamically changing index of all posts on Decentralized Thoughts (you can read chronologically here).

We would love to get your feedback and thoughts on Twitter.

Basics, Foundations, and Classics

You can start with the definition of Consensus and Agreement. Then learn about the network model, the threshold adversary model, and the power of the adversary. Finally, many protocols need a trusted setup phase. You can learn about different relaxations of Broadcast.

Checkout out our consensus cheat sheet for a quick overview of what is possible and impossible.

Synchronous Protocols

Under synchrony, a classic protocol is the Dolev-Strong Authenticated Broadcast protocol. You can read about more recent protocols such as Sync HotStuff, an optimal optimistically responsive synchronous protocol, and simple streamlined synchronous protocol Streamlet. A survey of authenticated protocols under the synchrony assumption.

Partially Synchronous Protocols

Partial synchrony is one of the most used models in real work systems today.

Modern variants of the classic protocols of Paxos and Raft are covered in Benign Hotstuff and Simplifing Raft with Chaining. Log Paxos is a modern take on multi-Paxos. It’s both surprisingly simple and concretely efficient.

For Byzantine adversaries, checkout Information Theoretic HotStuff.

Asynchronous Protocols

One of the core challenges in a fault-tolerant distributed computing is tolerating an asynchronous network. The classic FLP lower bound is a fundamental result showing the impossibility of consensus underf aults.

A fundamental building block in asynchrony is the Reliable Broadcast protocol.

How do you measure round complexity in asynchrony (and can you improve the round complexity of reliable broadcast)?

The multi-leader generalization of reliable broadcast is called Reliable Gather.

State Machine Replication

We begin by defining state machine replication (SMR) and talk about different degrees of SMR fault tolerance. The scalability and performance of a State Machine Replication system is not just about consensus, but also about data and execution.

Start with a simple SMR for crash failures. Extend SMR to omission failures. First via single shot and then via the lock-commit paradigm to multi-shot consensus.

In partial synchrony, Log Paxos shows how to extend Paxos to multi-Paxos in a straightforward and efficient manner.

Lower Bounds

Lower bounds give us powerful tools to understand the fundamental limitations and model assumptions.

Blockchains

What was the first blockchain (or how to timestamp a digital document)? Do proof-of-work blockchains need any setup assumptions? What does checkpointing a blockchain mean? What is Nakamoto Consensus? How do you prove it is secure. What is the problem of selfish mining?

The simplest L2 solution is a payment channel.

Cryptography

Some basics:

More advanced:

Research oriented posts