Complexity and optimization

In the general protocol, the number of reference pairwise comparisons scales with how many neighbors each node has—but who is adjacent to whom is left to the implementer.

If each node only has O(1) neighbors, work stays O(n) in n nodes. If the graph is fully connected—every node neighbors every other—the count of edges (hence comparisons) is quadratic, O(n²).

Complete graphs $K_2$ and $K_3$

For |V| = 2 or 3, even a complete graph is tiny: 1 or 3 reference pairwise comparisons respectively, so complexity is not a practical concern yet.

Complete graphs with $|V| > 3$

Beyond $K_3$, the edge count of a clique keeps growing quadratically.

For a complete graph on n vertices, the number of edges is

With more than three nodes, fully connected CRPC graphs become expensive fast—each edge also implies two reciprocal attestations, so stored comparison data is 2 × |E|.

Note: Multiply reference comparisons (edges) by two to get the number of published pairwise attestations.

Ring topology

The usual sparse choice is a ring: each node has at most two neighbors. Reference comparisons then scale linearly with n while still yielding useful per-node attestations.

In a $C_6$ example, five nodes may pass local checks while one fails—illustrating how more participants make disputes easier to surface.

We suggest a minimum of three nodes in practice so that, if one node disputes, two others still contribute independent signal.

Complete graphs: comparisons grow as Θ(n²); simple cycles: Θ(n) edges, times two for reciprocity—so dense topologies blow up much faster.

Solving the drift problem

For rings with |V| ≥ 4, local thresholds can hide global inconsistency: each edge may look fine while a non-edge pair (e.g. opposite on the ring) would violate ε if measured directly. Call that accumulated gap drift.

Example on $C_4$

Take nodes $N_1 \ldots N_4$ with scalar results:

• $N_1 = 1.0$
• $N_2 = 1.1$
• $N_3 = 1.2$
• $N_4 = 1.1$
• $\epsilon = 0.15$

Every measured adjacent difference is ≤ 0.1 < 0.15, so all $\delta_{ij} < \epsilon$ on edges. Yet $\lvert N_1 - N_3 \rvert = 0.2 > 0.15$—unmeasured drift the naive ring never sees.

Fully connecting the graph would catch that but reintroduces O(n²) edges.

Local vs global ε

Split the budget: let $\epsilon_{\text{glob}}$ be the true tolerance you care about, and set a stricter per-edge tolerance $\epsilon_{\text{loc}}$ derived from n.

Use

On a cycle, the worst-case hop distance between two nodes is about ⌊n/2⌋; if each edge obeys an L-Lipschitz-style bound with $L = \epsilon_{\text{loc}}$, then diametrically opposite values are bounded by roughly $L \cdot \lfloor n/2 \rfloor \leq \epsilon_{\text{glob}}$. (The write-up ties this to choosing $\epsilon_{\text{loc}}$ so unmeasured pairs stay below $\epsilon_{\text{glob}}$ without a clique.)

That lets you keep linear edge count while implicitly controlling non-edges, at the cost of tighter per-edge thresholds as n grows.

Demonstration: catching unacceptable drift

Reuse the $C_4$ example with $\epsilon_{\text{glob}} = 0.15$:

Now $\delta_{12} = \lvert N_1 - N_2 \rvert = 0.1 > 0.075$—the first edge fails the stricter local rule, so we reject the configuration before trusting unmeasured pairs such as $(N_1, N_3)$.

Even without explicitly computing $\delta_{13} = 0.2$, we already know $0.2 > \epsilon_{\text{glob}}$ would have been a problem; $\epsilon_{\text{loc}}$ gives a linear-time certificate that would have been invisible under a single naive $\epsilon$ on the ring alone.

In practice, tightening $\epsilon_{\text{loc}}$ buys much of the safety of a dense graph while keeping sparse topology.