Synchronisation and Agreement

general problem that defines the need for a set of entities in a DS to reach a common decision over something

typically follow one of three theoretical models:

1. Consensus

2. Interactive Consistency

3. The Byzantine General’s Problem

Assuming a set of 𝑛 processes of a DS that do not fail and communicate over a reliable communication system, a consensus problem as a special case of an agreement problem, can be defined as follows:

• each process 𝑝𝑖 possesses the following components:

  • a decision state 𝑠𝑖

  • a proposed value 𝑣𝑖, from a set of possible values 𝑉

  • a consensus value 𝑐𝑖, set from the same set of values 𝑉 plus an additional special value ⊥

• initially, the decision state 𝑠𝑖 of each process is set to "UNDECIDED" and 𝑐𝑖 is set to ⊥

• in order to reach agreement, the processes communicate with one another by exchanging an arbitrary number of messages over an arbitrary number of rounds

  • each message contains one or more proposed values 𝑣 of itself or other processes

• each process, at some time point, sets the consensus value 𝑐𝑖 by executing a decision function (such as majority voting) on the set of exchanged proposed values and changes its state to "DECIDED“

  • when this happens, no more changes to the consensus value are allowed (i. e. it is write-once)

• when all processes entered the DECIDED state, the consensus value of each process should be the same, i. e. 𝑐𝑖 = 𝑐𝑗, for every 𝑖, 𝑗 = 1 … 𝑛

used to solve a consensus problem in a distributed way under realistic conditions

An important requirement for such protocols is that they must be able to tolerate failures of processes, where the following two failure modes are distinguished:

Crash failures, where a process fails in such a way, that it can no longer participate in the protocol any more, i. e. the process stops working entirely and can not send or receive messages

Arbitrary or byzantine failures, where a process crashes or acts otherwise arbitrarily towards the other processes - in particular, a process could propose arbitrary values to other processes which might not even be reasonable for the respective use case, or could withhold values received from other processes indefinitely

In practice, it is assumed that there is an upper bound on the number 𝑑 of failed processes in either failure mode, for which a given protocol must be tolerant: such a protocol is then designated as "𝑑 crash-resilient" or "𝑑 byzantine-resilient", respectively

In addition to fault tolerance, a consensus protocol must also provide adequate performance

Typical metrics in this context are the number of rounds and the amount of exchanged messages necessary for one run of the protocol

• Termination

• Agreement

• Validity/Integrity

Each process enters the DECIDED state after a finite amount of time, i. e. an agreement is eventually made

After execution of the protocol, all correct (i. e. non-failed) processes possess the same consensus value, i. e. they all agree on the value for their 𝑐𝑖

After execution of the protocol, the consensus value of a correct process must be equal to the proposed value of some process

In general, the process whose value was chosen could be correct or could be failed

This property can be made stronger, if necessary, for example, by requiring that the process whose value was chosen is also correct

Instead of a single consensus value, each process 𝑝𝑖 sets an interactive consistency vector 𝐼𝐶𝑉𝑖[𝑗], with 𝑗 = 1 … 𝑛, where each entry represents the proposed value of the 𝑗-th process

Termination: Each process sets the value of each entry of its consensus vector after a finite amount of time, i. e. an agreement is eventually made

Agreement: After execution of the protocol, all correct (i. e. non-failed)

processes possess the same consistency vector, i. e. they all agree on the values of all entries of their 𝐼𝐶𝑉𝑖. Note, that when a failed process proposes different values to other processes, all correct processes must still agree on the same (!) value for the entry of the failed process, even when this value was never proposed by the failed process!

Validity: After execution of the protocol, the value 𝐶𝑉𝑖[𝑗] corresponding to a correct process 𝑝𝑗 must be equal to this process’ proposed value at each correct process 𝑝𝑖

agreement is always possible under the assumption that processes can only experience crash failures

processes can detect the crash of some process via timeout of messages and exclude this process in the remaining rounds of an agreement protocol

Assuming a maximum number 𝑑 of crashed processes, any agreement protocol is guaranteed to reach agreement in a maximum of 𝑑 + 1 rounds, i. e. when in each round another process crashes

solve the consensus problem in a synchronous system under the assumption of a maximum of 𝑑 crash failures is the following:

• Assume a group of 𝑛 processes, where each process 𝑝𝑖 tracks the proposed values that were sent and received in each round 𝑟 of the algorithm via sets 𝑉𝑖,𝑟

  • A round is bounded in time to the maximum one-way transmission delay of a message

• Initially, each process 𝑝𝑖 sets 𝑉𝑖,0 = {} and 𝑉𝑖,1 = {𝑣𝑖}, where 𝑣𝑖 is the process’ proposed value

• For each round 𝑟, with 𝑟 = 1 … (𝑓 + 1), each process 𝑝𝑖 performs the following actions:

  • Send the set of values 𝑉𝑠𝑒𝑛𝑑,𝑖 = 𝑉𝑖,𝑟 − 𝑉𝑖,𝑟−1 containing all proposed values that were not sent in the prior round via (unreliable) multicast to all other processes

  • Set 𝑉𝑖,𝑟+1 to 𝑉𝑖,𝑟 as preparation for the next round

  • If a message with a set of proposed values 𝑉𝑗,𝑟𝑒𝑐 is received from some process 𝑝𝑗, add all received values to the set for the next round, i. e. set 𝑉𝑖,𝑟+1 to 𝑉𝑖,𝑟+1 ∪ 𝑉𝑗,𝑟𝑒𝑐

• After the 𝑑 + 1-th round, each process 𝑝𝑖 sets its consensus value 𝑐𝑖 to the value 𝑑𝑒𝑐(𝑉𝑖,𝑟+1), where 𝑑𝑒𝑐() is some decision function, such as the minimum or majority function

  • For certain decision functions, like majority, a default value must be defined in case of no majority etc.

An agreement protocol that guarantees agreement under the assumption of byzantine failures is said to achieve byzantine agreement

This is only possible under the following condition:

𝑛 ≥ 3𝑑 + 1

i. e. when more than two-thirds of the processes are correct so they can “outnumber” the possibly wrong proposals made by byzantine processes

process acts irrationally or maliciously, frequently in violation of the protocols or rules that are intended to govern the system