Kevalin - Gossip Protocol

The gossip protocol allows collections of documents to be synchronized in logarithmic time without central coordination of nodes.

Each Collection identifies a signing key which each valid document must be signed with to verify membership (the rules for collection membership should be extended in future to any valid claim about the document, e.g. a document identifying itself as a reply to another document).

Nodes subscribe to collections. For each subscription, nodes exchange sets of message IDs (first checking an overall hash of the sets). If they discover new IDs (with valid membership proofs) they will fetch the new documents from the source node (pull model).

Gossip allows eventual consistency of the subscription contents without requiring active connections to the source of the collection.

Gossip node selection

Gossip is performed on a regular interval with a set of participating nodes chosen by maintaining a Kademlia routing table for each subscription. This ensures that the graph of subscribed nodes is fully connected and gossip will eventually reach the entire network.

The ‘small-world’ nature of the Kademlia routing table ensures that remote parts of the ID space will be contacted at approximately the same rate as nearby nodes, ensuring efficient diffusion through the entire graph (i.e. log(N) rounds of gossip).

Nodes participating in the subscription can signal to other participating nodes by publishing their ID to a special ‘subscription’ value under the id of the collection subscribed to.

Broadcast messages

For ‘real-time’ communication updates are broadcast between actively subscribing nodes. Incoming broadcast messages will immediately be forwarded to neighbouring nodes (push model) according to a broadcast protocol.

This allows updates to a collection to be distributed in a logarithmic number of hops proportional to the size of the subscription network.

Valid messages for broadcast distribution must meet the collection inclusion requirements and have a creation timestamp within a reasonable bound to prevent replay attacks.

Gossip is still performed in the background to reconcile the state of the collection and catch any updates missed (e.g. by new nodes joining the system).