Leaderless Consensus: Logical Clocks, Dependency Graphs, and Avalanche Sampling

Abstract: Leaderless Consensus Moves Ordering Cost Into the Conflict Graph

Leaderless consensus addresses the central bottleneck of leader-based protocols. In Raft, a leader replicates the log. In PBFT, a primary proposes sequence numbers. In a shared sequencer, a core ordering role can become both a throughput ceiling and a target for denial-of-service. Leaderless designs remove that fixed ordering point, but they do not remove ordering. They move ordering work into dependency graphs, conflict sets, randomized sampling, recovery protocols, and clock discipline.

EPaxos lets any replica become the command leader for an operation. If replicas observe the same dependency set, the command can commit on a fast path. If dependencies disagree, the protocol falls back to a slow path and merges conflicts. Avalanche and the Snow protocol family take a different route: validators repeatedly sample peers and update their preferences until a metastable preference becomes locally acceptable with parameterized probability. Both approaches scale well when conflicts are low. Both degrade when concurrent transactions hit the same state, liquidity inventory, bridge channel, or refund credential.

This article analyzes monotonic clocks, logical clocks, vector clocks, and hybrid logical clocks as tools for reasoning about causality in leaderless systems. For AllSwap, the relevant question is not whether a chain advertises high throughput. The question is whether concurrent cross-chain payments, solver quotes, market-maker inventory changes, and refunds can retain a verifiable order when there is no single sequencer that everyone treats as the source of truth.

Boundary: Consensus Time Is Not Wall-Clock Time

The system model includes replicas, clients, validators, cross-chain routers, solvers, market makers, bridge verifiers, and users. The adversary can create high-conflict transactions, delay messages in selected regions, bias peer sampling, exploit clock drift, and induce dependency cycles. The adversary is not assumed to forge signatures, control every random sample, modify honest client code, or rewrite committed state. The discussion is defensive protocol analysis, not a playbook for attacking live systems.

Leader-based protocols centralize ordering. Raft separates leader election, log replication, and safety. PBFT uses a primary and view changes to make Byzantine fault tolerance practical in asynchronous environments. The benefit is a simple replicated log. The cost is that the leader or primary can become a latency hub. Leaderless protocols open proposal rights to all replicas so a nearby node can start agreement without routing everything through a fixed coordinator.

The trade-off is subtle. A leader log gives every command a position. A leaderless protocol must infer enough ordering from causality, conflicts, and votes. When commands are independent, this is a win. When commands conflict, the protocol must reconstruct the same ordering evidence that a leader would have produced, but through a more distributed path.

EPaxos and Avalanche should not be treated as the same protocol. EPaxos is deterministic state-machine replication with dependency tracking and fast/slow paths. Avalanche is probabilistic Byzantine consensus built around random sampling and metastable convergence. They are discussed together because they share one design ambition: avoid a fixed leader while still reaching a safe order over concurrent events.

Clock Model: Physical Order Is Not Causal Order

Lamport's happened-before relation is the starting point. In a distributed system, there is no free global time. If event `a` occurs before event `b` in the same process, or a message sent by `a` is received by `b`, then `a` may causally influence `b`. A logical clock maps this causal relation into monotonically increasing values. It does not prove that smaller timestamps always happened earlier in physical time.

Vector clocks add one counter per process and can detect concurrency: two events may be incomparable if neither causally precedes the other. Hybrid logical clocks combine physical time and logical counters. They are useful for logs, snapshots, and cross-partition debugging because they stay close to wall-clock time while preserving one-way causal ordering. Spanner's TrueTime takes a different engineering route by exposing bounded clock uncertainty and using it to provide external consistency in a controlled infrastructure environment.

Leaderless consensus needs these distinctions. Two commands that touch disjoint state can commit in different physical orders at different replicas and still be safe. Two commands that touch the same pool, account, nonce, refund credential, or bridge release must be ordered. Wall-clock order is only an observation. Causal order is a property of messages and state dependencies.

A compact model is:

```text tx_i = (read_set_i, write_set_i, clock_i, origin_i) conflict(i, j) = write_set_i intersects read_set_j or write_set_j intersects read_set_i causal(i, j) = clock_i happened-before clock_j through messages order_needed(i, j) = conflict(i, j) or causal(i, j) ```

If `order_needed` is false, a protocol can exploit parallelism. If it is true, the protocol must produce a stable order. Cross-chain systems often have deceptively high conflict. Many orders look independent at the address level, but they may draw from the same USDT inventory, use the same market-maker credit line, compete for the same bridge lane, or depend on the same source-chain payment proof.

EPaxos: Replacing a Leader Log With a Dependency Graph

In EPaxos, any replica can become the command leader for a client operation. The command leader proposes the command together with dependencies and a sequence number. Dependencies are other commands that conflict with this command and must precede it. If a fast quorum returns matching dependencies and sequence numbers, the command can commit quickly. If replicas disagree, the protocol takes a slow path and merges dependency information through a Paxos-like accept phase.

The execution layer sees a graph, not a single log. Vertices are commands. Directed edges are ordering constraints. Once commands are committed, replicas add them to the dependency graph. The executor identifies strongly connected components and uses a deterministic tie-breaker inside each component so all replicas execute the same order even when dependency cycles appear.

A simplified proposal path is:

```text propose(cmd): deps = conflicts_seen_locally(cmd) seq = 1 + max(sequence(dep) for dep in deps) replies = preaccept(cmd, deps, seq) if all fast_quorum replies agree on deps and seq: commit(cmd, deps, seq) else: merged = union(replies.deps) accept_and_commit(cmd, merged, adjusted_seq) ```

The important line is `union(replies.deps)`. Under low conflict, replicas see the same small dependency set. Under high conflict, different replicas observe different edges. The merged dependency set becomes wider, strongly connected components grow, and commands that could have looked parallel at one replica become serialized by recovery. EPaxos Revisited emphasizes that after dependencies are finalized, the graph still has to be traversed to determine execution order. Execution latency can erase the fast-path win.

When Fast Path Degrades

Let `p` be the probability that a command conflicts with a concurrent command, and let `m` be the number of concurrent proposals in the same window. A rough independence model gives:

```text P_fast approximately equals (1 - p) raised to (m - 1) ```

The exact probability depends on workload structure, replica placement, and quorum observation, but the direction is useful. When `p` is small, the fast path dominates. When a hot pool, hot inventory account, or hot bridge lane pushes `p` upward, fast-path probability falls quickly. The tail matters more than the average: a system can process many independent orders quickly while a few high-value routes suffer dependency blowups.

The graph cost is also workload-sensitive. If the graph is a sparse DAG, topological execution is cheap. If conflicts create large strongly connected components, every command in the component must wait for a deterministic internal order. Tarjan or Kosaraju-style SCC detection is linear in vertices plus edges, but in a consensus hot path the edge count is the danger. Each edge represents observed conflict, recovery merge, or application-level dependency.

A production EPaxos-like system needs several structures:

- `conflict_index`: maps state keys to recent command instances. - `dependency_graph`: stores command vertices and dependency edges. - `recovery_log`: tracks uncommitted, partially committed, or slow-path commands. - `scc_scheduler`: deterministically executes strongly connected components. - `clock_hint`: records logical or HLC metadata for replay and debugging, without using it as proof of order.

If the application cannot declare read/write sets accurately, the protocol has to be conservative. Conservative conflict detection reduces safety risk, but it also lowers fast-path hit rate.

Avalanche: Metastable Sampling Is Not Free Randomness

Avalanche and the Snow family avoid global quorums by repeated random sampling. A node queries `k` peers. If at least `alpha` peers prefer the same value, the node adopts or reinforces that preference. If the same preference wins enough consecutive rounds, controlled by `beta`, the node accepts it locally. Small preference advantages can become self-reinforcing, pushing the network toward a metastable decision.

A simplified Snow-style loop is:

```text preference = initial_value confidence = 0 while confidence < beta: sample = query_random_validators(k) majority = count_preferences(sample) if majority[preference] >= alpha: confidence += 1 elif exists value v with majority[v] >= alpha: preference = v confidence = 1 else: confidence = 0 accept(preference) ```

The safety claim is probabilistic and parameterized. Larger `k`, stricter `alpha`, and larger `beta` lower the probability of inconsistent decisions, but they increase latency and message work. Avalanche's official Snowman documentation presents alpha and beta as configurable consensus parameters. Later academic analyses of Avalanche and Snow protocols show that the interaction among randomization, adversarial influence, and liveness is more delicate than the intuitive positive-feedback story suggests.

For transaction graphs, the advantage is that no node has to process linear global messages for every decision. The weakness is that conflict sets and sample bias matter. If two conflicting transactions gain local preference in different regions, sampling needs enough rounds to break symmetry. If the peer-sampling process repeatedly returns biased neighborhoods, convergence slows or favors the wrong preference. For high-value cross-chain releases, an application should not blindly use the same confidence threshold as a small transfer.

Monotonic Clock Drift Still Matters

Many leaderless protocols do not rely on synchronized physical clocks for safety. That does not mean implementation time is irrelevant. Local monotonic clocks drive request timeouts, retry intervals, cache expiry, sample windows, duplicate suppression, metrics, and log segmentation. A monotonic clock does not go backward, but rates can differ across hosts. Virtual-machine pauses, scheduler stalls, NTP behavior, sleep states, and container migration can make local deadlines diverge.

In EPaxos, an aggressive timeout can push a command that might have committed on the fast path into recovery. A conservative timeout can leave a real fault blocking the dependency graph. In Avalanche, query timeouts and sample intervals affect the set of preferences a node observes. A faster retry loop in one region can make that region overrepresented in local samples.

The safe engineering rule is to separate clock roles. Logical clocks express causality and replay. HLCs support audit logs, snapshots, and cross-node debugging. Monotonic clocks support local deadlines. None of these clocks should by itself become the final ordering proof for conflicting transactions. Final order must still come from signed messages, dependency edges, quorum evidence, or sampling certificates.

Failure Modes

The first failure mode is hot-key conflict amplification. Many transactions compete for the same pool, account, inventory bucket, bridge channel, or refund credential. In an EPaxos-like protocol, the dependency graph grows dense and the fast path degrades. Defenses include application-level read/write declarations, hotspot queueing, amount-based route splitting, and conflict-edge metrics.

The second failure mode is dependency recovery storms. After a replica crash or partition, unresolved commands require dependency recovery. If each recovery step discovers more conflicts, slow path keeps merging dependencies and the executor cannot cut a stable component. Defenses include fanout limits, abort semantics for expired commands, idempotent order states, and bounded retry windows.

The third failure mode is biased random sampling. Avalanche-like systems assume samples are representative enough for the parameters used. Network topology, peer selection, cloud concentration, or adversarial delay can make samples less independent than expected. Defenses include stronger peer sampling, sample-diversity telemetry, operator-distribution limits, and higher thresholds for larger value at risk.

The fourth failure mode is wall-clock misuse. If an application treats local wall-clock arrival time as economic order, cross-region trades can be misordered under drift or asymmetric latency. Defenses keep wall-clock time as a hint and require consensus evidence for conflicts.

The fifth failure mode is premature cross-chain release. A local accepted value may not yet be visible to the bridge, light client, or target-chain verifier. Defenses separate `local_accepted`, `network_finalized`, `bridge_observed`, and `target_released` rather than collapsing them into one confirmation flag.

AllSwap Relevance: Routing Needs Explainable Conflict Domains

AllSwap routes do not run on abstract throughput numbers. They run on real conflict domains. Two swaps can both be "USDT cross-chain" and still differ in conflict behavior depending on source-chain payment proof, target-chain inventory, market-maker quota, bridge lane, refund address, and destination execution queue. If the underlying chain or bridge uses leaderless consensus, the router needs to know which evidence supports acceptance.

A practical route score can track:

- `conflict_domain`: pool, inventory account, bridge lane, or refund credential. - `consensus_mode`: leader log, dependency-graph fast path, slow path, or probabilistic sampling. - `clock_source`: logical clock, HLC, bridge observation time, or local wall clock. - `sample_confidence`: sampling parameters and consecutive successful observations. - `refund_ordering`: whether the refund credential has entered a stable order.

These fields do not need to be exposed to ordinary users, but they determine quotation, release, and refund behavior. A small order may tolerate probabilistic acceptance or a fast path. A high-value order should wait for stronger evidence or require a solver to post more risk capital. Leaderless consensus is valuable when it removes a central bottleneck under low conflict. It is dangerous when a product hides the path by which it degraded under high conflict.

Implementation Layer: Make Conflict Domains First-Class

A usable leaderless routing system should not wait for the underlying consensus protocol to return a slow-path signal before it discovers a conflict. The route engine can construct a `conflict_domain_id` when the order enters the system. It can be derived from source chain, source transaction proof, target asset, target chain, market-maker inventory account, bridge lane, and refund credential. The exact hash does not need to be meaningful to users. It needs to be stable enough for routers, solvers, and auditors to reason about conflict.

A cross-chain order can then move through five queues:

```text quote_queue -> reserve_queue -> source_observed_queue -> release_queue -> refund_queue ```

`quote_queue` handles price and path selection. `reserve_queue` locks inventory or credit. `source_observed_queue` waits for source-chain payment evidence and consensus evidence. `release_queue` handles target-chain execution. `refund_queue` handles failure recovery. Every queue entry should carry the same `conflict_domain_id` and a `causal_token`. If two orders share a conflict domain, the router can serialize them intentionally rather than pushing both into a leaderless substrate and letting recovery discover the conflict after the fact.

This is not a rejection of concurrency. It is a way to spend concurrency on orders that are actually independent. Small stablecoin swaps, different destination chains, and different inventory buckets can proceed in parallel. The same high-value inventory slot, the same bridge lane, or the same refund credential should be queued early. If the underlying protocol is EPaxos-like, this reduces strongly connected components. If it is Avalanche-like, this reduces conflict-set size and sampling ambiguity.

The same design improves audits. When an order fails, logs should identify whether the cause was expired pricing, missing source-chain evidence, EPaxos-style slow-path recovery, insufficient sampling confidence, bridge-observation lag, or unstable refund order. Collapsing all of those into "network delay" destroys the distinction between market risk, consensus risk, and implementation risk.

There is a direct solver implication as well. A solver can price risk more tightly when the conflict domain is small and known. If the router cannot explain the conflict domain, the solver has to assume a wider tail-risk distribution, which raises spreads or reduces willingness to quote. Better consensus metadata can therefore improve user pricing without turning the article into an advertisement for any single protocol. It also gives operations teams a sharper rollback boundary: a refund can be delayed because a dependency is unresolved, not because the entire route is unsafe. That distinction matters during incidents.

Open Problems

First, application-level read/write declaration remains weak. If contracts and routers cannot expose precise conflict domains, leaderless consensus must serialize more than necessary.

Second, probabilistic finality does not have a uniform product vocabulary. Chains, bridges, RPC providers, and routers use words like accepted, finalized, and confirmed differently.

Third, dependency graphs and MEV interact in unresolved ways. Whoever can influence conflict edges or tie-breakers can influence arbitrage and liquidation order.

Fourth, HLC and physical-clock uncertainty are hard to standardize in open peer-to-peer networks. Datacenter systems can rely on stronger clock infrastructure than public blockchain validators.

Fifth, the independence assumptions behind randomized sampling need continual validation in real topologies. Cloud concentration, geographic latency, and peer-discovery rules change what protocol parameters actually mean.

References

[1] Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System, https://lamport.azurewebsites.net/pubs/time-clocks.pdf

[2] Friedemann Mattern, Virtual Time and Global States of Distributed Systems, https://homes.cs.washington.edu/~arvind/cs425/doc/mattern89virtual.pdf

[3] Kulkarni et al., Logical Physical Clocks and Consistent Snapshots, https://cse.buffalo.edu/tech-reports/2014-04.pdf

[4] Corbett et al., Spanner: Google's Globally-Distributed Database, https://research.google.com/archive/spanner-osdi2012.pdf

[5] Ongaro and Ousterhout, In Search of an Understandable Consensus Algorithm, https://raft.github.io/raft.pdf

[6] Castro and Liskov, Practical Byzantine Fault Tolerance, https://css.csail.mit.edu/6.824/2014/papers/castro-practicalbft.pdf

[7] Moraru, Andersen, Kaminsky, There Is More Consensus in Egalitarian Parliaments, https://www.cs.princeton.edu/courses/archive/fall19/cos418/papers/epaxos.pdf

[8] Tollman, Park, Ousterhout, EPaxos Revisited, https://www.usenix.org/conference/nsdi21/presentation/tollman

[9] Yin et al., Scalable and Probabilistic Leaderless BFT Consensus through Metastability, https://arxiv.org/abs/1906.08936

[10] Avalanche Builder Hub, Snowman Consensus, https://build.avax.network/docs/primary-network/avalanche-consensus

[11] Amores-Sesar, Cachin, Schneider, An Analysis of Avalanche Consensus, https://arxiv.org/abs/2401.02811

[12] Amores-Sesar, Cachin, Tedeschi, When Is Spring Coming? A Security Analysis of Avalanche Consensus, https://arxiv.org/abs/2210.03423