Characterizing Distributed Adversaries via Disagreement Power

17 concepts5 papers1 proposal

In distributed computing, we traditionally evaluate system robustness using the classic $t$-crash model: we assume an adversary can choose any subset of up to $t$ nodes and cause them to fail. While mathematically clean, this uniform model fails to capture the reality of modern distributed networks. Real-world failures are rarely uniform or completely random. A network partition might isolate a specific cluster, a power failure might take down a specific rack, or an intelligent adversary might strategically delay specific "straggler" nodes to maximize disruption, as noted by Margalit Glasgow et al. in Approximate Gradient Coding with Optimal Decoding.

Furthermore, traditional models treat all adversaries that can crash $t$ nodes as identical. However, an adversary that can adaptively choose which nodes to crash mid-protocol based on network messages is fundamentally more destructive than one that must choose its targets in advance. As shown by Harry Buhrman et al. in On the importance of having an identity or, is consensus really universal? and Dariusz R. Kowalski et al. in Gossiping to reach consensus, this gap between weak (static) and strong (adaptive) adversaries dictates whether fundamental tasks like consensus or node naming are even possible.

To build a unified framework that can compare any arbitrary adversarial strategy—whether it involves random crashes, coordinated network partitions, or adaptive stragglers—we need a metric that measures an adversary's impact rather than its actions. Instead of asking "how many nodes did the adversary destroy?", we should ask "how much disagreement can the adversary cause?"

Shifting Focus from Faults to Disruption

This insight motivates the concept of disagreement power, introduced by Carole Delporte-Gallet et al. in The Disagreement Power of an Adversary. Disagreement power quantifies an adversary's strength by the maximum number of distinct values it can force a distributed system to output during a $k$-set agreement task.

In a standard consensus task, all healthy nodes must agree on a single value ($k=1$). In $k$-set agreement, the nodes are allowed to choose up to $k$ different values. If an adversary can manipulate message timings or node failures such that the remaining correct nodes split into $k$ different opinions, that adversary has a disagreement power of at least $k$. By framing adversary strength this way, we shift the focus from fault injection to task disruption.

The Mechanics of the Structure Predicate

Why does this framing work? It works because it allows us to abstract away the specific, exotic failure patterns of an adversary and focus entirely on the topological boundaries it creates.

The authors formalize this by defining a structure predicate on the sets of processes that the adversary is permitted to crash, a technique detailed in both The Disagreement Power of an Adversary and La puissance de désaccord d'un adversaire by Carole Delporte-Gallet et al. Instead of assuming an adversary can crash any $t$ processes, the predicate explicitly maps out the permitted combinations of failures.

Traditional t-fault Model:
[Adversary] ---> Can crash ANY 2 nodes ---> [Nodes: A, B, C, D]
(Treats all combinations uniformly)

Disagreement Power Model:
[Adversary] ---> Allowed failure sets (Structure Predicate) ---> Evaluates information flow
(Measures how effectively failures fragment the network into independent consensus groups)

By analyzing this predicate, we can compute the exact maximum number of disconnected components or "surviving cliques" the adversary can engineer. If the adversary's allowed failure sets prevent information from flowing between $k$ distinct groups of processes, it can prevent them from ever reconciling their states, thereby forcing a $k$-set disagreement.

Equivalence Classes of Adversarial Strength

The ultimate utility of this framework lies in its ability to partition the infinite space of possible adversaries into a small, discrete set of equivalence classes based on their disagreement power.

As demonstrated by Carole Delporte-Gallet et al. in La puissance de désaccord d'un adversaire, two adversaries that operate completely differently—for instance, one that can crash any 2 nodes in a network versus one that can only crash specific combinations of 4 nodes—are completely indistinguishable if they share the same disagreement power. Within the same equivalence class, they can disrupt the exact same set of distributed tasks.

This equivalence simplifies distributed system design. Instead of inventing a new consensus protocol or failure detector for every unique network topology or threat model, engineers and theorists can determine the disagreement power of their specific environment and apply a known, optimal protocol tailored to that exact class of disruption.

Key Foundational Work

On the Importance of Having an Identity or is Consensus Really Universal? (2006) — contributed 1 concept elements to this direction.
Gossiping to reach consensus (2002) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_disagreement_power_f20d3bf1,
  title = {disagreement power},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/disagreement-power/rdr_f20d3bf14bb74828955f929b79ec1a65},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_disagreement_power_f20d3bf1_v1,
  title = {disagreement power},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/disagreement-power/rdr_f20d3bf14bb74828955f929b79ec1a65/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake