Home | | Distributed Systems | Consensus and related problems

# Consensus and related problems

The byzantine generals problem: a decision whether multiple armies should attack or retreat, assuming that united action will be more successful than some attacking and some retreating

Consensus and related problems

§  Problems of agreement

o   For processes to agree on a value (consensus) after one or more of the processes has proposed what that value should be

o   Covered topics: byzantine generals, interactive consistency, totally ordered multicast

·        The byzantine generals problem: a decision whether multiple armies should attack or retreat, assuming that united action will be more successful than some attacking and some retreating

·        Another example might be space ship controllers deciding whether to proceed or abort. Failure handling during consensus is a key concern

§  Assumptions

o   communication (by message passing) is reliable

o   processes may fail

§  Sometimes up to f of the N processes are faulty

·        Consensus Process

·        Each process pi begins in an undecided state and proposes a single value vi, drawn from a set D (i=1…N)

·        Processes communicate with each other, exchanging values

·        Each process then sets the value of a decision variable di and enters the decided state

·        Requirements for Consensus

§  Three requirements of a consensus algorithm

o   Termination: Eventually every correct process sets its decision variable

o   Agreement: The decision value of all correct processes is the same: if pi and pj are correct and have entered the decided state, then di=dj

·        (i,j=1,2, …, N)

o   Integrity: If the correct processes all proposed the same value, then any correct process in the decided state has chosen that value

·        The byzantine generals problem

§  Problem description

o   Three or more generals must agree to attack or to retreat

o   One general, the commander, issues the order

o   Other generals, the lieutenants, must decide to attack or retreat

o   One or more generals may be treacherous

·        A treacherous general tells one general to attack and another to retreat

·        Difference from consensus is that a single process supplies the value to agree on

·        Requirements

o   Termination: eventually each correct process sets its decision variable

o   Agreement: the decision variable of all correct processes is the same

o   Integrity: if the commander is correct, then all correct processes agree on the value that the commander has proposed (but the commander need not be correct)

·        The interactive consistency problem

§  Interactive consistency: all correct processes agree on a vector of values, one for each process. This is called the decision vector

o   Another variant of consensus

§  Requirements

o   Termination: eventually each correct process sets its decision variable

o   Agreement: the decision vector of all correct processes is the same

o   Integrity: if any process is correct, then all correct processes decide the correct value for that process

·        Relating consensus to other problems

§  Consensus (C), Byzantine Generals (BG), and Interactive Consensus (IC) are all problems concerned with making decisions in the context of arbitrary or crash failures

§  We can sometimes generate solutions for one problem in terms of another. For example

o   We can derive IC from BG by running BG N times, once for each process with that process acting as commander

o   We can derive C from IC by running IC to produce a vector of values at each process, then applying a function to the vector‘s values to derive a single value.

o   We can derive BG from C by

§  Commander sends proposed value to itself and each remaining process

§  All processes run C with received values

§  They derive BG from the vector of C values

·        Consensus in a Synchronous System

§  Up to f processes may have crash failures, all failures occurring during f+1 rounds. During each round, each of the correct processes multicasts the values among themselves

·        The algorithm guarantees all surviving correct processes are in a position to agree

·        Note: any process with f failures will require at least f+1 rounds to agree

·        Limits for solutions to Byzantine Generals

§  Some cases of the Byzantine Generals problems have no solutions

o   Lamport et al found that if there are only 3 processes, there is no solution

o   Pease et al found that if the total number of processes is less than three times the number of failures plus one, there is no solution

§  Thus there is a solution with 4 processes and 1 failure, if there are two rounds

o   In the first, the commander sends the values

o   while in the second, each lieutenant sends the values it received

·        Asynchronous Systems

·        All solutions to consistency and Byzantine generals problems are limited to synchronous systems

o   Fischer et al found that there are no solutions in an asynchronous system with even one failure

o   This impossibility is circumvented by masking faults or using failure detection

·        There is also a partial solution, assuming an adversary process, based on introducing random values in the process to prevent an effective thwarting strategy. This does not always reach consensus

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Distributed Systems : Synchronization and Replication : Consensus and related problems |