a message propose(t,c) is chosen if it is stored by a majority of servers
if a command c is executed by some servers, all servers eventually execute c
Define consensus and name its properties.
There are n nodes of which at most f might crash (n-f correct). Node i starts with an input value v_i. The nodes must decide for one of those values satisfying the following properties:
agreement: all correct nodes decide for the same value
termination: all correct nodes terminate in finite time
validity: the decision must be an input value of a node
Define configuration and critical configuration.
We say that a system is fully defined (at any point during the execution) by its configuration C. The configuration includes the state of every node, and all messages that are in transit (sent but not yet received).
C is critical if C is bivalent but all configurations that are direct children of C are univalent
Define univalent and bivalent.
A configuration C is univalent if the decision value is determined independently of what happens afterwards (only one decision is possible). (univalent for value v -> v-valent) Nodes need not be aware of this!
C is bivalent if the nodes might decide for 0 or 1
Define configuration tree.
The configuration tree is a directed tree of configurations. Its root is C0 (fully characterised by the input values), The edges are transitions (characterised by event (u,m), node u receiving message m), every configuration has all applicable transitions as outgoing edges.
Is there a deterministic algorithm which always achieves consensus in the asynchronous model with f>0?
If a system is in a bivalent configuration it must reach a critical configuration within finite time or it does not always solve consensus.
If a config tree contains a critical configuration crashing a single node can create a bivalent leaf
What does the randomized Consensus Protocol look like?