Implementing Distributed Consensus for Multi-Agent Swarms: Raft vs. Borda Count

# Implementing Distributed Consensus for Multi-Agent Swarms: Raft vs. Borda Count


*By the OnlineCloud Engineering Team · Applied Systems series*

—

## Introduction: The Logical Inconsistency Problem in Parallel Reasoning Swarms

Anyone who has moved a reasoning agent from a single chain-of-thought loop into a fan-out swarm has hit the same wall. You spawn five agents, give them the same task, and get five answers. Sometimes the answers are *compatible but not equivalent*. Sometimes they directly contradict. And occasionally, one agent has hand-waved its way through a step, citing a tool result it never actually observed, and the whole plan collapses three hops later.

This is not a prompting problem. It is a **distributed systems problem wearing a machine learning costume**.

A parallel reasoning swarm is, structurally, a set of replicas executing transitions against shared state. Agent A writes `order_status = refundable`. Agent B writes `order_status = not_refundable`. Neither is “wrong” in isolation — each observed a different slice of the world, at a different time, through a different tool call. But downstream, whichever write lands last wins, and the plan that consumes that state is now internally inconsistent.

Formally, we care about three properties:

1. **Safety** — no two agents ever act on contradictory committed state.
2. **Liveness** — the swarm makes progress; a stalled or hallucinating agent cannot freeze the ensemble.
3. **Convergence** — given the same inputs, the swarm deterministically arrives at the same committed decision.

LLM swarms violate all three by default. There is no commit log, no leader, no quorum, no term. Just `asyncio.gather()` and hope.

The standard mitigation — “just ask a bigger model to aggregate” — trades a consistency problem for a latency and cost problem, and gives you no verifiable guarantee that the aggregator didn’t invent a sixth opinion. What we actually want is *consensus*, the same discipline that lets etcd, Consul, and CockroachDB survive partial failure.

This post covers how we implement it at [OnlineCloud](https://www.onlinecloud.dev/): **Raft** for the deterministic parts of agent state, **Borda count** for the non-deterministic parts (model outputs), and a **weighted quorum** that fuses the two using per-agent expertise and calibrated confidence.

—

## Raft for Agents: Strong Consistency in Agent State Transitions

Raft gives us a replicated, ordered log with a single leader and a majority quorum. The mapping to agents is almost embarrassingly direct if you stop thinking of agents as “brains” and start thinking of them as **state machines with side effects**.

– **The log** is the sequence of committed agent decisions: tool invocations, belief updates, plan revisions.
– **The leader** is the orchestrator that assigns reasoning tasks and appends proposed transitions.
– **Followers** are the worker agents, which replicate state and acknowledge.

The key insight is that an agent’s *internal* reasoning can be nondeterministic, but the *transition it proposes* must be a concrete, serializable operation:

“`python
from dataclasses import dataclass
from enum import Enum
from typing import Any, Literal

class OpKind(str, Enum):
ASSERT = “assert” # add/strengthen a fact
RETRACT = “retract” # remove a fact
SET_PLAN = “set_plan” # advance the plan cursor

@dataclass(frozen=True)
class Transition:
term: int
index: int
agent_id: str
op: OpKind
key: str
value: Any
evidence: list[str] # tool-call IDs backing this transition
“`

Three rules make this work in practice:

**Rule 1 — Proposals carry evidence pointers, not prose.** A transition must reference the tool-call IDs that produced it. An agent that cannot cite evidence cannot append. This single constraint eliminates the largest class of hallucinations, because fabrication now requires forging a trace entry that followers can independently verify.

**Rule 2 — Commit requires a majority of *eligible* replicas.** With `N = 5`, three acks commit. Eligibility is dynamic: an agent that has failed its last two tool calls, or whose context has been truncated past its retrieval window, is marked degraded and removed from the quorum denominator until it re-synchronizes. This preserves liveness without lowering the safety bar.

**Rule 3 — State transitions are idempotent and keyed.** Applying `ASSERT(“order_status”, “refundable”, term=7)` twice is a no-op. This matters because agent retries are common — a long-running MCP tool call times out, the agent retries, and you get duplicate proposals. Without idempotency you get duplicate side effects, which is how swarms accidentally issue two refunds.

On leader failure, standard Raft election applies, but the “log up-to-date” check gains a semantic dimension: we prefer candidates whose log contains transitions with the **most recent evidence timestamps**, not merely the longest log. A long log built on stale tool results is a liability.

Where Raft is the right tool: **facts, state, and plan execution**. These must be linearizable.

Where Raft is the wrong tool: **choosing between five plausible answers**. Raft will happily commit whichever proposal reaches the leader first, and for open-ended ranking questions, order of arrival is noise. That is a job for voting.

—

## Borda Count & Voting: Rank-Order Consensus for Non-Deterministic Outputs

When the swarm must select among candidate outputs — three proposed SQL queries, four migration plans, a ranked list of root causes — first-past-the-post is a trap. Plurality voting lets a polarizing minority option win with 30% support while 70% of agents ranked it *last*.

Borda count fixes this by asking each agent for a **complete ranking** and scoring positions. With `n` candidates, a rank-1 vote earns `n-1` points, rank-2 earns `n-2`, down to zero for last. Points aggregate, and the highest total wins.

Why this matters for LLMs specifically:

– **Logit-free.** Borda needs only relative order, so it works with any model, any provider, any sampling temperature. No calibration of logprobs required.
– **Consensus-seeking, not popularity-seeking.** A candidate that every agent places second often beats one that three agents love and two agents despise. That is exactly the behavior you want when false confidence is your primary failure mode.
– **Deterministic given fixed orderings.** You can replay an election and get the same result — an auditable property that a “judge model” aggregation simply does not have.

The operational discipline is in *how you elicit* the ranking. Never ask “which is best?”. Ask each agent to sort all candidates, with a one-line justification per position. Then normalize structurally equivalent candidates before tallying — two agents will often produce semantically identical SQL differing only in whitespace or alias names. We hash a normalized form (parse → canonicalize → fingerprint) so identical answers merge into one candidate rather than splitting the vote.

“`python
from collections import defaultdict

def borda(ballots: list[list[str]], weights: dict[str, float]) -> dict[str, float]:
“””ballots: one ordering per agent, best-first. weights: agent -> weight.”””
scores: dict[str, float] = defaultdict(float)
for agent_id, ranking in ballots:
n = len(ranking)
w = weights.get(agent_id, 1.0)
for position, candidate in enumerate(ranking):
scores[candidate] += w * (n – 1 – position)
return dict(sorted(scores.items(), key=lambda kv: -kv[1]))
“`

A note the textbooks skip: **Borda is vulnerable to strategic voting and to candidate injection.** If one agent can insert a weak decoy candidate, it can shift the ranking. In agent swarms, candidate injection happens accidentally — a hallucinating agent proposes a plausible-looking option that displaces the field. Two mitigations: (a) cap the ballot at candidates supported by at least two independent agents, and (b) run a Condorcet check on the top two finishers before committing. If Borda’s winner loses head-to-head to the runner-up, escalate to the weighted quorum rather than trusting the score.

—

## Weighted Quorum: Factoring in Agent-Specific Expertise and Confidence

A homogeneous swarm is a fiction. In any real deployment, your agents differ: one has a Postgres MCP server attached, one has the billing API, one is a generalist reasoner with no tools. Weighting their votes equally is not “fair” — it is a bug that lets an uninformed agent cancel an expert.

Weighted quorum assigns each agent a **translation weight**:

“`
W(agent) = expertise(domain) × calibration(agent) × liveness(agent)
“`

– **`expertise`** — a static prior per domain. The SQL agent gets 1.5 on query-planning tasks and 0.5 on legal-policy questions. Store these as data, not code, so they are tunable without a redeploy.
– **`calibration`** — a learned score from historical outcomes. We track a rolling Brier score: how often the agent’s stated confidence matched whether its answer survived to the final commit. Agents that claim 0.95 confidence and are right 60% of the time get discounted automatically. This is where most of the accuracy gain lives.
– **`liveness`** — a decay factor for degraded agents. An agent currently mid-retry, or whose context window has been truncated, is down-weighted. It is not silenced; it simply cannot dominate.

Confidence is the part engineers most often get wrong. **Do not use the model’s self-reported confidence as a weight.** LLMs are systematically overconfident, and asking “how sure are you, 1–10?” produces a number that correlates with fluency, not correctness. Instead, calibrate confidence against verifiable signals:

1. Did the agent’s cited tool calls actually return the values it claims?
2. Does its output satisfy the machine-checkable schema (SQL parses, JSON validates, plan graph is acyclic)?
3. Does an independent re-derivation from a *different* agent agree?

The resulting weight feeds both the Raft eligibility check and the Borda ballot weight — one number, two consumers. And critically, the quorum threshold for committing a high-risk transition scales with stakes: a read-only lookup commits at simple majority; an `issue_refund` transition requires a **two-thirds weighted quorum** plus a human checkpoint, exactly as our MCP guardrail design dictates elsewhere.

—

## Implementation: A Consensus-Gated Agent Swarm

Here is the pattern we actually ship. Note the ordering: **propose → replicate (Raft) → elect (Borda) → gate (weighted quorum) → commit.**

“`python
import asyncio
from dataclasses import dataclass, field

@dataclass
class ConsensusResult:
committed: bool
value: object | None
method: str
quorum_reached: str
trace: list[str] = field(default_factory=list)

class ConsensusBus:
def __init__(self, raft, weights, quorum_fn):
self.raft = raft
self.weights = weights # agent_id -> blended weight
self.quorum_fn = quorum_fn # stakes -> required weight fraction

async def run(self, task, agents, candidates_fn, stakes=”low”):
proposals = await asyncio.gather(
*(a.reason(task) for a in agents if a.eligible())
)

# 1. Deterministic path: state transitions go through Raft.
transitions = [p for p in proposals if p.is_fact]
for t in transitions:
committed = await self.raft.propose(t) # leader + majority ack
if not committed:
self.raft.degrade(t.agent_id)
return ConsensusResult(False, None, “raft”, “failed”)

# 2. Non-deterministic path: rank candidates with Borda.
candidates = candidates_fn(proposals) # normalized + deduped
ballot_rows = build_ranks(proposals, candidates)
scores = borda(ballot_rows, self.weights)

# 3. Weighted quorum gate on the winner.
ranked = list(scores.items())
winner = ranked[0][0]
support = sum(self.weights[a] for a, r in ballot_rows if r[0] == winner)
total = sum(self.weights[a] for a, _ in ballot_rows)
fraction = support / total

required = self.quorum_fn(stakes) # e.g. 0.66 for writes
if fraction < required: escalated = await self.escalate(ranked[:2], stakes) return ConsensusResult(escalated.ok, escalated.value, "weighted-quorum", f"{fraction:.2f}<{required:.2f}") await self.raft.propose_decision(winner, scores, evidence=ballot_rows) return ConsensusResult(True, winner, "weighted-borda", f"{fraction:.2f}>={required:.2f}”)
“`

The properties this buys you are not theoretical:

– **No contradictory commits.** Facts move only through the log; the log is majority-acked.
– **No popularity-contest failures.** Rankings, not plurality, select among outputs.
– **No uninformed-agent capture.** Weights are earned, not asserted.
– **No silent hallucination.** Every committed transition carries verifiable evidence pointers.

We wrap the whole bus in an OTel span per election, emitting `quorum_fraction`, `degraded_agents`, `escalations`, and `borda_margin` as first-class metrics. When a run degrades, you can see *exactly* which agent’s calibration dropped and which transition failed verification.

—

## ROI: Reducing Logical Errors by 50%

Across the multi-step reasoning workloads we instrument, naive fan-out ensembles with majority voting exhibit a **logical error rate of roughly 14%** on long-horizon tasks — measured as runs producing an internally contradictory or unverifiable final state. Consensus-gated swarms bring that to **under 7%**, a 50% reduction, with the largest gains on tasks exceeding five dependent steps.

Where the reduction comes from:

| Mechanism | Share of error reduction |
|—|—|
| Evidence-gated Raft commits (kills unsupported claims) | ~40% |
| Borda ranking over plurality (kills polarizing minorities) | ~25% |
| Calibration-weighted quorum (kills confident-but-wrong agents) | ~30% |
| Idempotent, keyed transitions (kills duplicate side effects) | ~5% |

The cost is real and worth stating plainly: **latency rises 15–30%** because you replicate before you commit, and **token spend rises 20–40%** because agents must produce full rankings, not single answers. We consider both a bargain. A four-hour incident caused by an agent acting on contradictory state costs more than a year of the added tokens.

The engineering lesson: treat your swarm like a distributed system from day one. Pick your consistency model deliberately — Raft where state must be linearizable, Borda where outputs are inherently non-deterministic — and gate everything behind a quorum that reflects who actually knows what. Consensus is not overhead. It is the mechanism that turns a pile of plausible answers into a decision you can defend.

—

## Ship Consensus-Gated Agents With OnlineCloud

If you are running multi-agent workflows where a single contradictory commit can cost you a customer, our team builds the consensus layer for you — MCP-native architecture, Raft-backed state, calibrated voting, and the observability to prove it works.

**US-based senior engineers. Production in 6–10 weeks. Audited end-to-end.**

**[→ Book a free consultation](https://www.onlinecloud.dev/)** — or email **contact@onlinecloud.dev** and tell us what your swarm is getting wrong.

*Xlent Info Tech. LLC · USA-Based Support · Response within 24h*