this page is a dynamically changing index of all our posts, it’s one more place to start reading Decentralized Thoughts
Basics, Foundations, and Classics
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 more about Partial Synchrony and about different relaxations of Broadcast.
One of the classic protocols of distributed computing is the Dolev-Strong Authenticated Broadcast protocol.
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.
We start with a simple SMR for crash failures. We later extend this to omission failures. First via single shot.
Lower Bounds
-
Consensus with Ommsion failures requires $f<n/2$.
-
Byzantine Consensus in Partial Synchrony requires $f<n/3$.
-
Byzantine Consensus with no PKI (or more generally when the adversary can simulate) requires $f<n/3$.
-
Consensus is challenging because some initial state must be uncommitted and this imples executions with at least $f+1$ rounds in Synchrony and non-terminating executions in Asynchrony (the FLP impossibility).
Blockchains
-
The first blockchain (or how to timestamp a digital document).
-
Setup assumptions in Bitcoin and Ethereum and the notion of checkpointing a blockchain.
Cryptography
The basics:
More advanced: