What is a ticket and what properties does it have?
A ticket is a weaker form of a lock with the following properties:
What does the Paxos Protocol look like?
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:
Define configuration and critical configuration.
Define univalent and bivalent.
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