Distributed consensus

When is it achieved?

Formal requirements for consensus:

• Processes produce the same value.

• All results are valid.

• All processes have to, eventually, provide a result.

Consistency, availability, and partitioning

CAP theorem

• Any distributed system that shares information can only have two of the three following properties:

  • Consistency, any shared and replicated information appears as a single updated value.

  • Availability ensures that an update will always, eventually, be executed

  • Partition of the set will always be tolerated.

Corolarium

In a network with communication failures an atomic read/write operation in shared memory that ensures a response to all requests is impossible.