Seeding Chaos: Property-Based Testing for Agent Consensus Under Network Partitions

Distributed agent systems fail in the gaps between happy-path tests. You can verify that two agents agree when the network is perfect, but the real world drops packets, partitions nodes, and reorders messages. Property-based testing, combined with a chaos-injection layer that randomly partitions the network, gives you a way to explore that failure space systematically. This is not about throwing random inputs at a pure function; it's about generating random network topologies and partition schedules, then checking that your consensus protocol still satisfies its invariants.

In this article, I'll walk through a concrete methodology for applying property-based testing to agent consensus under random network partitions. We'll use a simple consensus protocol as a running example, and I'll show you how to structure the test harness, define the properties, and interpret the failures. The approach is language-agnostic, but I'll use Python with the hypothesis library because it's widely known and has good support for stateful testing.

Why Property-Based Testing for Distributed Systems?

Traditional unit tests pin down specific scenarios: "if agent A sends message X to agent B, then B responds with Y." These are necessary but insufficient. The space of possible interleavings, delays, and failures is astronomically large, and you can't enumerate it by hand. Property-based testing flips the approach: you define invariants that must always hold, and the test framework generates random inputs (or, in our case, random partition schedules) to try to break them.

The key insight is that for consensus protocols, the invariants are well-known: agreement (all non-faulty agents decide on the same value), validity (if all agents propose the same value, they decide on that value), and termination (all non-faulty agents eventually decide). Property-based testing lets you check these invariants under a wide range of network conditions, including partitions that heal, split the network into multiple components, and drop messages.

The Consensus Protocol Under Test

To make this concrete, let's use a simplified version of the Raft consensus algorithm. Raft is a good candidate because it's designed to handle network partitions, but subtle bugs can still slip through. Our implementation will have the following components:

• A Node class that maintains state: current term, voted-for, log, commit index.
• A Network class that simulates message delivery with delays and drops.
• A PartitionManager that can partition the network into groups.

The full Raft implementation is beyond the scope of this article, but the testing methodology applies to any consensus protocol. In fact, the more complex the protocol, the more value you get from property-based testing.

The Property-Based Test Harness

We'll use hypothesis to generate random sequences of operations: propose a value, send a message, drop a message, partition the network, heal a partition, etc. The test will run the network for a fixed number of steps, then check that the invariants hold.

Here's a skeleton of the test harness:

from hypothesis import given, settings, strategies as st
from hypothesis.stateful import RuleBasedStateMachine, rule, precondition, invariant

class ConsensusMachine(RuleBasedStateMachine):
    def __init__(self):
        super().__init__()
        self.nodes = [Node(i) for i in range(5)]
        self.network = Network(self.nodes)
        self.partitions = []

    @rule(proposer=st.integers(min_value=0, max_value=4), value=st.integers(min_value=0, max_value=100))
    def propose(self, proposer, value):
        self.nodes[proposer].propose(value)

    @rule(sender=st.integers(min_value=0, max_value=4), receiver=st.integers(min_value=0, max_value=4))
    def send_message(self, sender, receiver):
        if sender != receiver:
            self.network.send(sender, receiver)

    @rule()
    def deliver_messages(self):
        self.network.deliver_all()

    @rule()
    def partition_network(self):
        # Randomly partition the network into two groups
        group1 = st.sampled_from([0, 1, 2, 3, 4]).example()
        group2 = [i for i in range(5) if i not in group1]
        self.network.partition(group1, group2)
        self.partitions.append((group1, group2))

    @rule()
    def heal_network(self):
        self.network.heal_all()
        self.partitions.clear()

    @invariant()
    def agreement(self):
        # All nodes that have decided must have decided on the same value
        decided_values = [node.decided_value for node in self.nodes if node.decided_value is not None]
        if decided_values:
            assert len(set(decided_values)) == 1

    @invariant()
    def validity(self):
        # If all nodes proposed the same value, they must decide on that value
        proposed_values = {node.proposed_value for node in self.nodes if node.proposed_value is not None}
        if len(proposed_values) == 1:
            value = proposed_values.pop()
            for node in self.nodes:
                if node.decided_value is not None:
                    assert node.decided_value == value

    @invariant()
    def termination(self):
        # This is tricky: we can't assert termination in a finite test, but we can check that if a node has decided, it stays decided
        for node in self.nodes:
            if node.decided_value is not None:
                assert node.decided_value == node.decided_value  # trivial, but we can add more

This is a simplified example. In practice, you'd need to model the network more realistically, with message delays and potential loss. But the key is that the state machine generates random interleavings of actions, including partitions, and the invariants are checked after each step.

Generating Random Partitions

Network partitions are not just binary splits; they can be partial, with some nodes in one group and others in another, and they can change over time. hypothesis allows you to generate complex data structures, so you can generate a partition as a list of lists, where each sublist is a group of nodes. For example:

@st.composite
def partition_strategy(draw, num_nodes):
    # Generate a random partition of nodes into groups
    nodes = list(range(num_nodes))
    groups = []
    while nodes:
        group_size = draw(st.integers(min_value=1, max_value=len(nodes)))
        group = draw(st.sampled_from(nodes))
        groups.append(group)
        nodes = [n for n in nodes if n not in group]
    return groups

Then use this strategy in the rule:

@rule(partition=partition_strategy(num_nodes=5))
def partition_network(self, partition):
    self.network.partition(partition)

This gives you a wide variety of partition shapes: from a single group (no partition) to fully isolated nodes.

Determinism and Reproducibility

One of the challenges with property-based testing is that failures are random, so you need to be able to reproduce them. hypothesis handles this by printing a minimal failing example when a test fails. You can also set a fixed seed for the random generator to make the entire test run deterministic. For example:

@settings(max_examples=1000, seed=42)
def test_consensus_properties():
    ConsensusMachine.run()

This is crucial for debugging: you can take the minimal failing example and replay it in a debugger.

Interpreting Failures

When a property fails, hypothesis shrinks the failing input to a minimal case. For our consensus protocol, a failure might look like this:

• The network is partitioned into two groups: {0, 1} and {2, 3, 4}.
• Node 0 proposes value 10, node 2 proposes value 20.
• The partition heals, but some messages are lost.
• Eventually, node 0 decides on 10, but node 2 decides on 20.

The invariant agreement fails. This tells you that your protocol has a bug under this specific partition schedule. You can then examine the logs to see exactly what messages were sent and received, and why the nodes diverged.

Beyond Simple Consensus

This methodology extends to more complex scenarios: agents that need to agree on a shared state, or swarms that coordinate via a shared log. The key is to identify the invariants that must hold, and then use property-based testing to explore the failure space.

For example, in a multi-agent system where agents maintain a local view of the world, you might want to ensure that eventually all agents converge to the same state. You can define a property that checks convergence after a certain number of steps, given random partitions and message delays.

Another extension is to model Byzantine failures, where some agents send conflicting messages. Property-based testing can generate malicious behaviors, but you need to be careful to ensure that the properties are still valid under those conditions.

Practical Considerations

• Model the network faithfully: The network simulation should include realistic delays, message loss, and reordering. Otherwise, the tests will not reflect real-world conditions.
• Keep the state machine small: The more nodes and actions, the larger the state space, and the slower the tests. Start with 3-5 nodes and a limited set of operations.
• Use timeouts: To test termination, you can add a timeout to the test, and check that all nodes have decided before the timeout. But be careful: a timeout failure might be due to a slow test, not a protocol bug.
• Integrate with CI: Property-based tests can be run in CI, but they can be slow. Use a smaller number of examples in CI, and run a larger set nightly.

Conclusion

Property-based testing with random network partitions is a powerful tool for verifying agent consensus protocols. By generating random partition schedules and checking invariants, you can uncover bugs that would be impossible to find with hand-written tests. The methodology is not a silver bullet, but it's a key part of a robust testing strategy for distributed systems.

In the RiNET stack, we use this approach to validate our agent coordination layer, which relies on a consensus protocol to maintain a shared state across multiple nodes. The property-based tests run nightly, and they've caught several subtle issues that would have caused data inconsistencies in production.

If you're building distributed agent systems, I encourage you to adopt this methodology. Start with a simple protocol, define your invariants, and let the random chaos generator do the rest.