Multiparty Set Reconciliation

Abstract

The set reconciliation problem, that consists in bringing two or more replicas of a set into agreement is present in all databases, distributed ledgers and any large scale synchronization systems.While the two party case is well studied, the multiparty one exposes a large design space of protocols whose communication cost varies drastically with topology, replica count and the level of similarity.A very slow space to search on by hand.This thesis investigates the use of an autonomous agent loop as a research tool to navigate that specific design space.This means using an agent to iteratively propose, implement and evaluate reconciliation protocols against a single measurable objective until convergence is achieved.In this case, the objective was the total bytes transmitted, including state and metadata, taken as a geometric mean over an evaluation matrix with eighteen cells and three seeds.The search yielded MultiReplica, a topology dispatched protocol that combines all neighbor Bloom filter exchange on star and tree topologies with pairwise distance doubling on chord and that reduces communication cost by roughly 30 % relative to the strongest hand designed baseline while scaling to replica counts at which the baselines exhaust memory.The contribution is twofold.On one side the discovered protocol itself and a reproducible demonstration that an autonomous agent loop can serve as a credible, auditable method for distributed systems protocol research.