Consensus Algorithm

Blog Dag is a graph G = < B, g, P, E > where B is blocks/vertices within the graph, g is the genesis block, P is the function that maps a block b to its parent block (ie. P(b) is the "parent" of block b), and E is the set of edges between blocks/vertices.

e in E is e = <b, b'> pointing from block b to ancestor block b', denoting that b' happens before b.

Chain(G,b) =  g if b = g,  otherwise its the set of { Chain(G, P(b)) .. b }

Child(G,b) = { b' where P(b') = b}

Sibling(G,b) = Child(G,P(b)) - {b}    ie. all children of the parent of b, P(b), minus b itself

Subtree(G,b) = ( union of all Subtree(G, i) for i in Child(G,b) ) unioned with b itself  [NOTE: Recursive!]

Before(G,b) = {all b' where b' is in B, and <b, b'> is in E}

Past(G, b) = ( union of all Past(G,i) where i is in Before(G,b) and union with b itself ) [NOTE: Recursive!]

Definition of Pivot(G, b):

INPUT: The local block dag <B, g, P, E> and a starting block b in B OUTPUT: The last block in the pivot chain for the subtree of b in blockdag G

if (Child(G,b) == EMPTYSET) { 
    return b;
}
else {
   block s = nullblock;
   hash w = MINHASH;
   for b' in Child(G, b) {
       w' = Count(Subtree(G,b'));
       if (w' > w || (w' == w && Hash(b') < Hash(s))) {
            w = w';
            s = b';
       }
   }

   return Pivot(G,s);
}