Lernkarten
What is a ticket and what properties does it have?
A ticket is a weaker form of a lock with the following properties:
- reissuable: server can issue more tickets even if previous ones not yet returned
- expiration: server only accepts most recently issued ticket
What does the Paxos Protocol look like?
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?
No.
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
--> NO
What does the randomized Consensus Protocol look like?
It achieves binary consensus with expected runtime O(2^n) if up to f < n/2 nodes crash.
(there is no consensus algorithm for the asynchronous model that tolerates f >= n/2 failures)
