Computation of cliques and blockclique

[massa-bot]

In GitLab by @qdr

Goal

Given the graph of block that contains the incompatibles blocks, update the set of cliques and the blockclique.

Requires

83

To do

• if the new block has incompatibilities, we recompute the cliques with the maximum clique algorithm here https://gitlab.com/massalabs/massa-network/-/wikis/IK_GPX-algorithm-for-finding-maximal-cliques
• if not, we update the cliques incrementally: we add the block B to all cliques C where B is compatible with all blocks of C
• Then, we compute the blokclique: the clique of maximum fitness.

The fitness of a clique is defined as the sum of the fitness of each block of the clique, and the fitness of a block is defined by f=1+e where e is the number of endorsements in the block. Until we implement endorsements, the fitness of a clique is thus the number of blocks.

A tie breaking mechanism must be implemented: here we will prefer cliques with a minimum sum of priority of blocks, and if still tie, of minimum hash sum. The priority of a block B is defined as the number of missed blocks in the thread of B between B and its parent.

[massa-bot]

In GitLab by @qdr

changed the description

[massa-bot]

In GitLab by @qdr

changed the description