# Consensus is Harder Than It Looks

DevFeed: [Consensus is Harder Than It Looks](<https://devfeed.tech/articles/consensus-is-harder-than-it-looks-12500.md>)

Original publisher: [Read original article](<http://brooker.co.za/blog/2020/10/05/consensus.html>)

Author: Marc Brooker

Published: 2020-10-05T00:00:00Z

Content type: article

Language: en

Sources: [Marc Brooker's Blog](<https://devfeed.tech/sources/marc-brooker-s-blog.md>), [Marc Brooker's Blog](<https://devfeed.tech/sources/marc-brooker-s-blog-2.md>)

Topics: [distributed-systems](<https://devfeed.tech/topics/distributed-systems.md>), [Concurrent Programming](<https://devfeed.tech/topics/concurrent-programming.md>), [Processes](<https://devfeed.tech/topics/processes.md>), [systems](<https://devfeed.tech/topics/systems.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>)

Tags: [complexity](<https://devfeed.tech/tags/complexity.md>), [concurrency](<https://devfeed.tech/tags/concurrency.md>), [locks](<https://devfeed.tech/tags/locks.md>), [processes](<https://devfeed.tech/tags/processes.md>), [systems](<https://devfeed.tech/tags/systems.md>)

## AI overview

The article argues that building consensus-based, highly available systems is harder than the Paxos algorithm alone suggests. It discusses deterministic replicas, concurrency, host failures, leases, monitoring, and the practical challenges of implementing fault-tolerant services.

## Source excerpt

Consensus is Harder Than It Looks And it looks pretty hard. In his classic paper How to Build a Highly Available System Using Consensus Butler Lampson laid out a pattern that's become very popular in the design of large-scale highly-available systems. Consensus is used to deal with unusual situations like host failures (Lampson says reserved for emergencies), and leases (time-limited locks) provide efficient normal operation. The paper lays out a roadmap for implementing systems of this kind, leaving just the implementation details to the reader. The core algorithm behind this paper, Paxos, is famous for its complexity and subtlety. Lampson, like many who came after him1, try to build a framework of specific implementation details around it to make it more approachable. It's effective, but incomplete. The challenge is that Paxos's subtlety is only one of the hard parts of building a consensus system. There are three categories of challenges that I see people completely overlook. Determinism "How can we arrange for each replica to do the same thing? Adopting a scheme first proposed by Lamport, we build each replica as a deterministic state machine; this means that the transition relation is a function from (state, input) to (new state, output). It is customary to call one of these replicas a 'process'. Several processes that start in the same state and see the same sequence of inputs will do the same thing, that is, end up in the same state and produce the same outputs" - Butler Lampson (from How to Build a Highly Available System Using Consensus). Conceptually, that's really easy. We start with a couple of replicas with state, feed them input, and they all end up with new state. Same inputs in, same state out. Realistically, it's hard. Here are just some of the challenges: Concurrency. Typical runtimes and operating systems use more than just your program's state to schedule threads, which means that code that uses multiple threads, multiple processes, remote calls,