Consensus_heuristic (mavkit-shell-libs.Mavryk_shell.Consensus

Consensus heuristic

A consensus heuristic is a mechanism by which a node attempts to find a data that its network of peers generally agrees upon. Typically, the node attempts to find out what the p2p network as a whole agrees is the head of the chain.

Note that, by nature, this problem does not necessarily have one exact solution. This is a heuristic, it makes a "best guess" based on information available locally.

The consensus heuristic is given candidates: tuples of the form p,d where d is the data and p is a peer id indicating the provenance of the data. Typically, a candidate indicates what a peer considers to be the head of the chain.

The consensus heuristic is parametrized by two values:

expected is the number of candidates that the heuristic keeps internally,
threshold is the number of candidates that need to agree on their data for a consensus to be reached.

A precondition for the heuristic is that 0 <= threshold <= expected < 2 * threshold to ensure a unique consensus value.

type 'a t

'a t is the abstract internal state for the consensus heuristic mechanism. 'a is the type of the data that needs to be agreed upon.

Note that these values are intended to be short-lived, one shot. Specifically, these values are not meant to be used over a long period of time during which there is churn in the set of p2p neighbors.

type 'a state =

| Consensus of 'a
| No_consensus of ('a * int) list
| Need_more_candidates

The three different states that the heuristic can be in.

If the heuristic received less than expected candidates and no candidates' data has threshold occurrences, then its state is Need_more_candidates.

If the heuristic received expected (or more) candidates but no candidates' data has threshold occurrences, its state is No_consensus. The payload for the constructor lists all the candidates' data with the number of their occurrences.

Otherwise there is some candidates' data that has threshold occurrences or more and the state is Consensus.

val create : 
  ?compare:('a -> 'a -> int) ->
  expected:int ->
  threshold:int ->
  unit ->
  'a t

create ~compare ~expected ~threshold () is a fresh heuristic state.

compare is used internally to instantiate a map of candidates. It must be a total order over the type of data, but the specific of the order has no effect on the consensus.

raises Invalid_argument
if not 0 <= threshold <= expected < 2 * threshold

val get_state : 'a t -> 'a state

get_state heuristic returns the current state of the heuristic according to the semantics given above.

val update : 'a t -> (Mavryk_base.P2p_peer.Id.t * 'a) -> unit

update heuristic (peer, data) updates the heuristic with the candidate (peer, data). If a data was already registered for peer, then it is replaced by the update. It is the responsibility of the caller given a peer to update better and better data (for the caller's notion of "better").

Consensus heuristic worker

module Worker : sig ... end

This worker implements a memoisation mechanism for the consensus heuristic with an expiry date mechanism. The worker also handles a hook mechanism to be executed on values found by the consensus heuristic.