Consensus (computer Science) - Equivalency of Agreement Problems

Equivalency of Agreement Problems

Three agreement problems of interest are as follows.

Terminating Reliable Broadcast

(Also known as The General's Problem) A collection of n processes, numbered from 0 to n - 1, communicate by sending messages to one another. Process 0 must transmit a value v to all processes such that

1. If Process 0 is correct then every correct process receives v
2. For any two correct processes, each process receives the same value

Consensus

Formal requirements for a consensus protocol may include

Agreement - All correct processes must agree on the same value.

Weak Validity - If all correct processes receive the same input value, then they must all output that value.

Strong Validity - For each correct process, its output must be the input of some correct process.

Termination - All processes must eventually decide on an output value

Weak Interactive Consistency

For n processes in a partially synchronous system (the system alternates between good and bad periods of synchrony), each process chooses a private value. The processes communicate with each other by rounds to determine a public value and generate a consensus vector with the following requirements

1. If a correct process sends v, then all correct processes receive either v or nothing (integrity property)
2. All messages sent in a round by a correct process are received in the same round by all correct processes (consistency property).

It can be shown that variations of these problems are equivalent in that the solution for a problem in one type of model may be the solution for another problem in another type of model. For example, a solution to the Weak Byzantine General problem in a synchronous authenticated message passing model leads to a solution for Weak Interactive Consistency. An interactive consistency algorithm can solve the consensus problem by having each process choose the majority value in its consensus vector as its consensus value.