[First appeared in KoreConX on November 20, 2018]
We saw in Part 1 that linked lists provide the conceptual foundation for blockchain, where a ‘block’ is a package of data and blocks are strung together by some type of linking mechanism such as pointers, references, addresses, etc. In this Part 2, we will see how this simple concept gives rise to powerful ideas that lay the foundation for distributed systems.
What happens when one of the links in the linked list or one of the computers (aka, ‘nodes’) in a distributed system falls sick (and responds slowly), gets taken down (‘hacked’), or dies? How does the full list (or chain) recover from such tragic events? This brings us to the notion of fault tolerance in distributed systems. Once changes are made to the data in one of the nodes (blocks), how do we ensure that the same information is consistent with other nodes? That introduces the requirement for consensus.
Pushing the analogy of the linked list a bit further, algorithms that manage linked lists are carefully designed not to break the list. Appending links to the end or the front, for that matter, is an easy operation (we just need to make sure that the markers that indicate the start and end of the list are updated correctly). However, removing a link (or member of the chain) or adding one is a bit trickier. When it is necessary to remove or insert into the middle of the list, it’s a bit more complicated, but a well-understood problem with known solutions. We won’t go into the specifics in this article because the intent is not to describe these operations but to convey a high-level historical perspective.
In distributed systems, fault tolerance becomes a very important topic. In one sense, it is a logical extension to managing a linked list on a single computer. Obviously, in real-world applications, each of the nodes in a distributed system are economic entities that depend on other economic entities to achieve their goals. Faults within the system must be minimized as much as possible. When faults are inevitable, recovery must be as quick and complete as possible. Computer scientists began studying the methods of fault tolerance in the mid-1950s, resulting in the first fault-tolerant computer, SAPO, in Czechoslovakia.
Besides fault tolerance, when information needs to be added to the distributed system (a bit like adding, deleting, or updating the elements of a linked list), the different parties must agree. The reason for agreement is that the data that goes into the ‘linked list’ is data that arises out of transactions between these parties. Without agreement, imagine the chaos! My node would record that I sent you $90 while your node would record only $19! Or, if I send you payment for a product, I expect to receive the product. There should be agreement, settlement, and reconciliation between the transacting parties. A stronger requirement in distributed systems is that once the parties agree to something, the data that is agreed upon cannot be changed by one of the parties without the concurrence of the other party or parties. The strongest version of this requirement is ‘immutability’, where it is technically impossible to make any changes to data that is agreed to and committed to the chain.
Fault-Tolerance and Consensus
Distributed systems, therefore, require fault-tolerance, consensus, and immutability in varying degrees, depending on the needs of the business. Mechanisms for fault-tolerance and consensus evolved since the early days. Notable developments are:
- Byzantine Fault Tolerance (BFT) by Lamport, Shostak, and Pease in 1982, to deal with situations where one or more of the nodes in the distributed system become faulty or malicious.
- Proof-of-Work (POW), first described in 1993 and the term coined in 1999, which is a technique for providing economic disincentives for malicious attacks. A precursor idea of POW was proposed in 1992 by Cynthia Dwork and Moni Naor, as a means to combatting junk mail—a problem that was already a significant nuisance way back in 1992!* Their solution was to require a sender to solve a computational problem that was easy enough for sending emails normally but becomes computationally expensive for sending massive amounts of junk emails.
- Hashcash, a POW algorithm, was proposed by Adam Back in 1997. This was used as the basis of POW in bitcoin by Satoshi Nakamoto in 2008, which brought awareness of POW to a much wider audience.
- A high-performance version of BFT, called Practical Byzantine Fault Tolerance (PBFT), by Miguel Castro and Barbara Liskov, in 1999; and so on.
- Paxos**, a family of consensus algorithms, has its roots in a 1988 work by Dwork, Lynch, and Stockmeyer, and first published in 1998 (even though conceived several years earlier) by Leslie Lamport.
- Raft consensus algorithm was developed by Diego Ongaro and John Ousterhout. Published in 2014, it was designed to be a more understandable alternative to Paxos.
State machine replication (SMR) is a framework for fault-tolerance and consensus is a way to resolve conflicts or achieve agreement on the state values. SMR’s beginnings are in the early 1980s, with an influential paper by Leslie Lamport, “Using Time Instead of Timeout for Fault-Tolerant Distributed Systems” in 1984.
In Part 3, we will do a high-level review of mechanisms designed to keep distributed systems secure, consistent, and able to handle large volumes of transactions.
*Their paper, “Pricing via Processing or Combatting Junk Mail”, begins with a charming expression of exasperation: “Some time ago one of us returned from a brief vacation, only to find 241 messages in our reader.”
**No known relation to the blockchain company, Paxos.com