Byzantine Resilience at Swarm Scale: A Decentralized Blocklist Protocol from Inter-robot Accusations

3 min read

The Decentralized Blocklist Protocol (DBP) lets cooperative robots accuse a peer whenever a local observation contradicts what the peer reported. Accusations are signed, flooded through the network, and fed by every robot into the same deterministic maximum-matching algorithm (Edmonds’), so all cooperative robots compute the same blocklist. Because an accusation from a cooperative robot is assumed true, any accusation means at least one of the pair is Byzantine. Blocking both ends of each matched pair therefore removes every Byzantine robot when the accusations satisfy Hall’s marriage condition, at the cost of also blocking some honest accusers.

Findings

  • On linear-consensus tasks, DBP lowers the worst-case connectivity needed from (2F+1)-connected for W-MSR to (F+1)-connected, and needs one cooperative observer to spread new information instead of F+1.
  • A theorem gives eventual agreement on the blocklist when at most F robots are Byzantine and the time-varying network stays “floodable” despite F robots refusing to forward.
  • Target tracking with 200 cooperative and 100 Byzantine robots: W-MSR with F = 100 could not propagate the target at all, and with F = 15 part of the swarm tracked it but the Byzantine influence was never removed.
  • Time synchronisation with 100 cooperative robots (50 anchors) against 45 Byzantine robots adding +1000 time steps: once all Byzantine robots were blocked, error returned to nominal.
  • Cooperative localisation with 120 cooperative robots (80 anchors) against 50 Byzantine robots adding offsets of up to 20 m: W-MSR does not apply, and DBP accused and blocked the attackers quickly.

Limits

  • Accusations must be sound: a cooperative robot never accuses another cooperative one. A cooperative robot with a broken sensor breaks this, and the authors list unsound accusations as future work.
  • Identities come from a trusted authority at deployment, messages are signed, the team is closed, and Sybil attacks are ruled out by assumption.
  • Byzantine robots keep their influence until enough accusations accumulate, and honest accusers get blocked along with them (in the paper’s seven-robot example, two of the four blocked robots are cooperative).
  • Accusation rules are hand-written per application (for example a bound on how fast a target can move). All results are simulations.

Relevance

A clear alternative to the trimming in the W-MSR note: it spends identity infrastructure and application knowledge to buy lower connectivity requirements. Like most work on Byzantine faults, it never asks whether the accused robot is lying or broken; both get blocked.