Global Consensus

Global consensus is the need for all processes/nodes in a concurrent/distributed system to have agreement about some aspect of the state of the system. For example, a distributed GarbageCollector would need to know that all processes in a system contain no live references to an object before freeing that object--asking each process this question serially might fail (as a sole reference to such an object might be migrated from one process A to another B, after it is determined that B contains no such references and before A is queried).

Also a tricky problem in real-life--where we live with the fact that global consensus is impossible in many situations.

For a practical example, consider taking the (physical) inventory of a factory as part of a year-end closing of the books (this is standard accounting practice). A physical inventory is necessary, using computer records won't suffice. All the raw materials, work-in-progress, finished goods, and tools and equipment must be accounted for.

Now, consider that the factory is producing a very successful product and is running 24/7 in production--doing the inventory at night is not an answer. You might be able to take parts of the factory offline to do a count; but you cannot take the whole factory off-line. And material may flow between areas counted and areas not counted (and thus might get counted twice, or not at all).

Another real-life example: BankMoneyTransfer.

"One can solve obstruction-free consensus using only read/write registers" -- but we would prefer to gain consensus not merely obstruction-free, but at least lock-free (LockFreeSynchronization), and preferably wait-free (WaitFreeSynchronization). See SynchronizationStrategies.

"Wait Free Synchronization" Lecture 2 CS380D Distributed Computing I http://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/F03/notes/12-4.pdf is a good summary of "Wait-Free Synchronization" by Maurice Herlihy (1993) http://citeseer.ist.psu.edu/herlihy93waitfree.html

Maurice Herlihy mathematically proves that that "It is impossible to construct a wait-free implementation of any object with a consensus number greater than 1 using atomic read/write registers." (or point-to-point FIFO message channels).

Maurice Herlihy also proves that test&set and fetch&add [and unconditional swap between register and memory], can synchronize 2 threads, but no more.

"Nevertheless ... there do exist simple universal objects from which one can construct a wait-free implementation of any sequential object."

Any one of these "universal objects" are sufficient to synchronize any number of processes:

an atomic compare&swap instruction.
sticky byte
The augmented queue: with "enqueue", "dequeue", and "peek at first item in queue" instructions.
"fetch&cons": atomically thread an item onto the front of a linked list.
memory-to-memory move
memory-to-memory swap

One universal object Herlihy implies but does not list:

augmented stack with "peek at bottom of stack"

Any of these "universal objects" can be used to implement any other "universal object". None of these "universal objects" can be implemented by "weaker" synchronization primitives.

Those are nice if your processors share a common, global memory -- but what if you're on a network, like in the BankMoneyTransfer example ?

CategoryConcurrency