History of consensus protocols, a short thread.
In the 1970s, computer scientists such as Leslie Lamport and Barbara Liskov began thinking about the following question: “how do we achieve agreement between a set of machines?”
This simple question gave rise to the long and complex problem known as “consensus”, which is integral to the study of distributed systems.
For many decades, only one family of consensus protocols was known, namely “classical consensus protocols”. Protocols belonging to this family can be easily recognized due to one property: all-to-all voting.
Such protocols achieve agreement through a procedure similar to that of a voting for a new bill in a parliament: when a transaction (bill) is issued, every validator (senator) votes on whether they would like to “accept” or “reject” that transaction.
All votes are collected by all validators, leading to complex and cumbersome message interactions. In particular, these protocols necessarily require a lower bound of O(n^2) messages, where ’n’ is the number of validators.
While classical consensus protocols can confirm transactions very quickly, in a matter of just a few seconds, they can only do so when the network is small, typically less than a few hundred validators.
Furthermore, these protocols necessarily require knowledge of all participants, making them difficult to deploy in large environments, such as those needed for a global, open, digital currency.
These protocols were the de-facto standard until 2008, when Satoshi introduced the second family of protocols, known as Nakamoto, or longest-chain, consensus protocols.
This family has a revolutionary property that entirely upends that of classical protocols: they operate at the same speed regardless of the number of participants.
This also implies that they are suitable for open environments, where keeping track of incoming and outgoing participants (i.e. dynamic participation) is difficult.
Unfortunately, these protocols also have a fatal downside: they are inherently slow, operating at only a few transactions per second, and confirming transactions in a matter of minutes. Furthermore they also have high energy usage.
Variants of both classical and Nakamoto consensus protocols, which featured a multitude of optimizations, kept appearing for many years, without making much of a dent in their downsides.
However, in 2018, another family of consensus protocols was introduced, called the Snow family, by Team Rocket in collaboration with a group of distributed systems researchers. The Avalanche protocol was the first member of this family.
These algorithms use a novel mechanism for reaching agreement: instead of all-to-all voting, these protocols randomly select a handful of participants and ask about the state of the world. What makes these protocols groundbreaking-ly awesome?
They merge the best of both classical and Nakamoto: they confirm transactions in a few seconds and operate at thousands of tps, while also enabling thousands to millions of participants, thus making them suitable for open, permission-less settings where validators come and go.
About AVA Labs:
AVA Labs makes it simple to launch finance applications using blockchain technology–with highly scalable and efficient networks, customizable public and private blockchains, the capability to create any digital asset, and more. We are empowering people to build an open, simple, and democratic internet of finance.