1
$\begingroup$

The FLP paper provides proof in section "4. Initially Dead Processes" that consensus is possible if majority of processes live and no process dies during the consensus protocol. The proof has 4 main steps:

  1. Build G graph in way that each process broadcast it's process number and waits for the message from L other processes (L=[(N+1)/2])
  2. Calculate transitive closure of G: G+
  3. Determine clique of G+. The paper says that clique has cardinality at least L. (Node k is in the clique iff k is itself an ancestor of every node j that is an ancestor of k)
  4. Make a decision based on the initial values of the processes in the clique

I would have the following question about step 3:

  • What guarantees that clique described in step 3 exist?
$\endgroup$

2 Answers 2

0
$\begingroup$

Firstly, we need to prove that G is a single connected component. If n is a node in a connected component of G, then there are L-1 other nodes that are also in that component (the ones from which n received their messages). So this component has the size of at least (L-1)+1 = L nodes. So each connected component has at least L number of nodes and L is bigger than the half of the number of the nodes, so can be a single connected component only.

By the definition of the transitive closure, G+ will also have a single connected component. This means that it has only a single initial click. An initial click is a set of nodes that does not have incoming edges. Let's assume that n is a member of the initial click of G+. Let m be another node such that there is an edge from m to n in G. By definition, there is an edge in G+ from m to n as well. Because of the definition of initial click, there cannot be an incoming edge to n from outside of the initial click, so m must be in the initial click as well. By the construction rules of G, there is L-1 number of such m nodes that has an edge to n in G, so they are also part of the initial click along with n. So the initial click has the size of at least L nodes.

$\endgroup$
0
$\begingroup$

It can be proven with the following two steps that clique with cardinality at least L exist:

  1. There is at least one node which is in the clique of G+
  2. If a node is in the clique of G+ than all of its predecessors are in the clique

For #1 we use proof by contradiction. So we will assume that no such node exist which is ancestor of all its ancestor:

  1. If no such node exist than for each node X there is at least one node Y that X is not ancestor of Y in G+
  2. If X is not ancestor of Y in G+ than it can not be predecessor of Y predecessors in G either
  3. So X can not be the predecessor of the L -1 predecessors of Y and Y itself in G
  4. There are L-1 nodes left in G. It includes X so X can have maximum L-2 nodes predecessor
  5. If each X has maximum L-2 predecessors in G it means that each node has maximum L-2 outgoing edges. It is contradiction because each node has L-1 incoming edges in G

For #2 the proof is the following with node X which is in the clique of G+:

  1. For each Y node in G+ where X is the ancestor of Y than each Z ancestor of X is also ancestor of Y
  2. For each Z it is true that its ancestors are subset of X ancestors
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.