Skip to content

CECR ​

Convergent Extremal Coordinate Routing: how a message finds its way across a partly connected mesh, each hop closer to its target.

The specification · cecr/1, version 1.0

The problem ​

In a partial mesh no peer is linked to every other, so a message for one peer has to be passed along. CECR decides, at each hop, which neighbour to pass it to, using only what that peer knows, without loops.

The idea ​

  • Membership by lease. Every peer publishes a signed membership record (alive or left) that expires unless renewed. Each peer keeps its own live view of the room from these records.
  • Coordinates from the extremes. A peer's coordinate is its id's place between the smallest and largest live ids in that view. Each node works the extremes out from its own authenticated view, never from what others claim. Coordinates order ids; they do not measure latency or distance.
  • An XOR backbone. Each node keeps a link in every non-empty XOR bucket, and links to its numeric predecessor and successor.

A hop ​

For a message to target t, a node:

  1. delivers it if it is t; stops (TARGET_NOT_LIVE) if t is not in its live view;
  2. sends it straight to t if t is a neighbour;
  3. otherwise prefers neighbours closer to t by XOR bucket, ranked by a blend of coordinate and XOR distance (coordinate weight 7/20);
  4. falls back to any neighbour that lowers the raw XOR distance;
  5. stops (NO_PROGRESS) rather than pass it to a neighbour that is no closer.

Every hop strictly lowers the XOR distance to the target, so a route cannot loop, even without a list of peers visited. Coordinates are used only once a node's view is stable and agrees with its neighbours'; until then, routing is XOR alone.

What it promises, and what it doesn't ​

With a stable view, a live target and XOR coverage at every hop, a message arrives within 256 hops (the id width), and the next hop is the same on every node with the same view. CECR does not promise O(log N) routing in general, low latency, or reliable delivery, and signatures do not stop Sybil attacks or peers that drop traffic.

In PeerPigeon, getCecrState() and the cecrStateChanged event show a node's view, and getHopDistance(peerId) its distance to a peer.

peer.ooo · peer to peer on PeerPigeon