Consensus

Consensus algorithms are used to agree on a decision inside a distributed system.

Regular consensus #

• Validity: any value decided is a value proposed
• Termination: every correct process eventually decides
• Integrity: no process decides twice
• Agreement: no two correct processes decide differently

Uses best-effort broadcast and perfect failure detector.

Uniform consensus #

Uniform Agreement: no two correct processes decide differently

All processes add their proposal value to proposalset and then use the same deterministic function to decide.

Total order broadcast #

Can be used to build consensus.

Total order property: let $m_1$ and $m_2$ be any two messages. Let $p_i$ and $p_j$ be any correct processes that deliver $m_1$ and $m_2$. If $p_i$ delivers $m_1$ before $m_2$ then and $p_j$ also delivers $m_1$ before $m_2$.