Drawbacks of Multual Exclusion:

1. Asynchronous interrupts: may wait random time
2. Heterogeneous Processors: there may be some relatively slow processor
3. Fault-tolerance: the lock-holder may fail

<aside> 💡 Register: refering to the minimum computing unit, but not the physical register

</aside>

Consensus

Each thread has a private input, and then they communicate to aggre on one thread’s input

<aside> 💡 Theorem

There is no wait-free implementation of n-thread consensus, n>1, from read-write registers

</aside>

Consensus Object

A consensus object provides a single method decide().

Each thread calls the decide() method with its input $v$ at most once.

The object’s decide() method returns a value meeting the following conditions:

• Consistent: all threads decide the same value
• Valid: the common decision value is some thread's input

In other words, a concurrent consensus object is linearizable to a sequential consensus object in which the thread whose value was chosen completes its decide() first.

Definitions

1. A class C solves n-thread consensus if there exists a consensus protocol for n threads using any number of objects of class C and any number of atomic registers.
2. The consensus number of a class C is the largest n for which that class solves n-thread consensus. If no largest n exists, we say the consensus number of the class is infinite.
3. Suppose one can implement an object of class C from one or more objects of class D, together with some number of atomic registers. If class C solves n-consensus, then so does class D.