In one-shot federated learning, each client trains once on its private data and communicates once. The usual way to combine the resulting models is to send them to a server. The server labels a shared pool of unlabeled examples with the clients' ensemble and then trains one student model on those labels. We ask whether that server can be replaced by a peer-to-peer network. In our version, each client sends only tiny discrete votes (a class label, or "I abstain") to its graph neighbours, for a few rounds. The network agrees on a pseudo-label for every pool item, and every client then trains the same student locally. Majority-style voting protocols are the obvious engine. Theory shows they reach exact network-wide agreement in a number of rounds that grows only logarithmically with the number of agents, provided the leading opinion starts with a lead.
That proviso is where federated data breaks the theory. Under label skew, the correct label for a given image is often known only by the few clients that saw that class. Plain majority dynamics amplifies whatever answer is most common at the start. It will therefore reliably and quickly drive the network to the wrong answer. Our central claim is that letting clients abstain on classes they barely trained on fixes this. Abstaining clients become "undecided" agents in the sense of undecided-state dynamics, a known consensus protocol. This turns plurality consensus over all clients into plurality consensus over the clients that actually know the class, while keeping messages at $\lceil\log_2(k+1)\rceil$ bits for $k$ classes. We then measure how the communication graph's shape changes this: rings versus expanders versus stars, and 32 versus 500 clients. All comparisons run under a benchmarking protocol strict enough that a gain cannot come from tuning or splits.
Core Claim
Fix an unlabeled pool item $x$ with true label $y$. Client $i$ casts vote $v_i(x)=\hat y_i(x)$ only if two conditions hold: its own training set held at least $\tau$ examples of class $\hat y_i(x)$, and its softmax confidence exceeds $\gamma$. Otherwise it casts $v_i(x)=\bot$. Let $d_c(x)$ be the number of non-abstaining clients voting $c$. The quantity that matters is the expert margin
$$\Delta(x) = d_y(x) - \max_{c\neq y} d_c(x),$$
the lead of the correct label among clients that chose to speak.
Plain majority dynamics succeeds only when the correct label is also the raw plurality of all $n$ clients. Abstaining undecided-state dynamics needs only $\Delta(x)$ to be large enough that it survives the random early phase. For well-mixed pairwise interactions, Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model proves this threshold to be an additive lead of order $\sqrt{n}\log n$. That paper also shows convergence within $O(kn\log n)$ interactions, provided the number of opinions satisfies $k \le O(\sqrt{n}/\log^2 n)$.
We state plainly that at federated scales ($n\le 500$) these asymptotic thresholds exceed $n$ and are therefore vacuous. The theory predicts the direction of the effect; the claim itself has to be established empirically. The testable prediction has two parts. First, abstention raises pool-label accuracy from "raw plurality correct" toward "full centralized ensemble correct". Second, it does so at a bit cost far below gossiping continuous predictions to the same agreement level.
Positioning Against Prior Work
The one-shot aggregation step we decentralize comes from server-side distillation. Guha et al. and FedAD distill client models into one global model using unlabeled public data, always at a single server. We keep their assumption of a shared unlabeled pool and remove the server.
The data-free variants constrain our design by showing what the centralized ceiling looks like. DENSE synthesizes data from client batch-norm statistics. FEDCVAE ships conditional autoencoder decoders to a server. Both assume a star network, and we treat them as references rather than competitors.
FedPFT is the closest one-shot work to a decentralized setting. Clients fit Gaussian mixtures to frozen foundation-model features and send them in one round, and its abstract mentions decentralized scenarios. It does not characterize topology, and its messages are full covariance-bearing summaries rather than label votes. OFL-W3 decentralizes only storage, not aggregation.
On the consensus side, the logarithmic-time results for discrete agreement supply the mechanism. These include Giakkoupis et al., On the h-Majority Dynamics with Many Opinions (larger polling samples $h$ lower the required initial lead exponentially), and the undecided-state analysis above. All of them assume complete or well-mixed interaction, and all treat the initial plurality as the answer to be amplified.
Two results constrain the design. Silvestri et al. and Becchetti et al. show that 3-majority stalls from near-uniform starts. Vojnovic et al. show that convergence time blows up as the margin shrinks. Both warn that per-item margins in skewed federations may be too small for any amplification to be fast.
The topology literature poses the question we test. Which mode is better for federated learning? Centralized or Decentralized finds that iterative decentralized training collapses on rings and grids as clients grow from 100 to 500 under Dirichlet $\beta=0.1$, and attributes this to spectral gap. Beyond spectral gap argues the opposite for i.i.d. data: a local "effective number of neighbours" predicts decentralized SGD better than spectral gap. Both study continuous averaging during iterative training. We ask which of the two predicts rounds-to-agreement for discrete, one-shot votes under label skew.
Finally, A Fair Comparison of Graph Neural Networks for Graph Classification and Open Graph Benchmark supply our evaluation methodology. The first found that simple structure-agnostic baselines beat reported graph neural network gains once model selection and assessment were separated. The second showed that realistic splits change conclusions.
Research Program
We build a simulator with three layers. In the first layer, each client trains once, either as a linear head on frozen CLIP or ViT features (the FedPFT regime, where Wang et al. suggest shared initializations make combination easy) or as a small CNN from scratch. Clients then compute votes with the abstention rule.
In the second layer, the consensus phase runs every pool item as an independent, parallel instance of one of four dynamics:
- Plain $h$-majority: poll $h$ neighbours with replacement and adopt their plurality.
- Abstaining $h$-majority: polls ignore $\bot$.
- Plain undecided-state dynamics.
- Abstaining undecided-state dynamics: $\bot$ clients start undecided and are not re-counted as voters until they adopt an opinion.
Each variant runs on six graphs, drawn from the sets used by Sun et al. and Vogels et al.: ring, 2D torus, star, hypercube, one-peer exponential graph, and complete graph. Client counts are $n\in\{32,100,500\}$.
In the third layer, each client trains a student on the agreed labels. Where agreement is incomplete at the round budget, the client uses its local majority label. We log per-item pool-label accuracy, the fraction of items reaching exact agreement, rounds to agreement, total bits sent, and final student test accuracy.
On the analysis side, we will try to extend the undecided-state potential argument to the abstention start state, where many agents begin undecided, which matches that proof's first phase. We will also try to obtain a bound on bounded-degree expanders. We treat rings as an empirical question: majority dynamics on cycles is known to freeze into stable blocks, and we expect that failure rather than hope to avoid it.
Baselines
The naive reference point is local-only learning. Each client keeps its one-shot model, or distills from its own labels on the pool, with no communication. OFL-W3 found collaboration beat the weakest single client by 58.87 points on MNIST, so any method must clear the average local client by a wide margin to be worth its messages.
The ceiling is centralized ensemble distillation in the style of Guha et al., run on the same pool, clients and student architecture. We run both the averaged-softmax and the hard-plurality versions. For the strongest published star-topology one-shot reference in the extreme-skew regime, FEDCVAE reports 95.37% test accuracy on MNIST at Dirichlet $\alpha=0.001$, versus 45.12% for FedAvg. On CIFAR-10, DENSE reports 67.42% with heterogeneous client architectures. We will rerun both under our partitions rather than compare against these figures across setups. We found no reported result on Lacuna for any decentralized one-shot method on these benchmarks. Beating the centralized ceiling is not the goal; landing within a stated gap (we set two points on CIFAR-10) while sending no parametric model or feature summaries is.
The strongest decentralized competitor is continuous gossip averaging of client softmax vectors, run with push-sum on directed graphs. It runs both with the same round budget and, separately, quantized to the same total bit budget as the discrete protocols. This is the real threat, because its fixed point is exactly the centralized averaged ensemble.
A second strong competitor is decentralized FedPFT. Each client floods its Gaussian mixture summaries to every other client, then trains a head on sampled features. It is likely more accurate in the foundation-model regime, and we will report its byte cost and accuracy side by side with ours.
Two ablations isolate the key ingredients. Plain undecided-state and plain $h$-majority dynamics without abstention isolate abstention. Abstention combined with continuous gossip (averaging only over non-abstaining clients' predictions) isolates discrete amplification from expert filtering.
All methods share the same partitions, released per seed. Each method gets the same hyperparameter budget: a fixed number of configurations for $\tau$, $\gamma$, $h$, gossip step sizes and the student optimizer. Selection happens on a validation split carved from the pool and never from the test set, following the selection/assessment separation of A Fair Comparison of Graph Neural Networks for Graph Classification. We report mean and spread over at least five seeds per cell.
Why not just…?
Why not just gossip-average the soft predictions? Averaging converges to the averaged ensemble, which is at least as accurate as any vote-based label. On well-connected graphs with a generous bit budget it may win outright. Our claim is narrower: exact agreement at a fixed small bit budget. Quantized averaging loses precision exactly on low-margin items, while abstaining majority spends its bits amplifying the expert lead. The matched-bits comparison settles this. If quantized averaging matches abstaining undecided-state dynamics in accuracy per bit on the one-peer exponential graph, the discrete mechanism is unnecessary and the contribution shrinks to the abstention rule plus the topology study.
Why not just send everything to one server? Sun et al. show centralized training beating decentralized training on a ring by nearly 20 points at 100 clients, and a server needs no consensus at all. We run the server as the ceiling rather than argue against it. The proposal matters only where no trusted aggregator exists, and the result we report is the size of the gap to that ceiling, not a win over it.
Why not just flood all votes so every client computes the exact plurality? Flooding gives exact expert plurality in diameter-many rounds. On expanders it is a strong competitor. On a ring, the diameter is $n/2$ rounds and each client relays all $n$ votes per item, so total traffic scales with $n$ times the number of edges, against at most $O(\log n)$ rounds of single-label messages for majority dynamics where it works. We include flooding as a baseline and report the crossover in $n$ and topology at which it becomes cheaper.
Why not just share FedPFT Gaussian mixtures peer-to-peer? This is a genuine competitor in the frozen-backbone regime. Mixture summaries carry more information than labels, so it may be more accurate. The trade-off is message size and exposure: mixtures of foundation features are a distribution proxy that the one-shot literature flags as inversion-prone, and they do not apply to scratch-trained heterogeneous models. The experiment reports both axes. We do not claim superiority where the mixtures win.
Decisive Checks
The experiments use CIFAR-10, CIFAR-100, SVHN, FashionMNIST and MNIST. Client splits follow Dirichlet $\alpha\in\{0.001, 0.1, 0.5\}$. The unlabeled pool is drawn from the training split, disjoint from both client data and test data, and it is reported separately from the test score to avoid pool–test leakage.
The first check is whether amplification of the wrong answer is real. At $\alpha=0.001$, plain majority should converge quickly to pool labels whose accuracy tracks the raw-plurality rate, well below the centralized ensemble. Abstaining undecided-state dynamics should close most of that gap. If plain majority is already near the ensemble, the premise fails.
The second check is the topology predictor. Across the six graphs and three client counts, we regress rounds-to-agreement and pool-label accuracy on spectral gap and on the effective number of neighbours of Beyond spectral gap. This tells us which account carries over from continuous averaging to discrete votes under skew.
The third check is scaling on sparse graphs. Moving from 100 to 500 clients on the ring and torus shows whether one-shot discrete consensus inherits the collapse Sun et al. report for iterative training, or whether it avoids collapse because nothing is trained across rounds.
The fourth check is the matched-bits comparison against quantized averaging, which decides whether the discrete dynamics earns its place.
References
- Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model
- One-Shot Federated Learning.
- Ensemble Attention Distillation for Privacy-Preserving Federated Learning
- DENSE: Data-Free One-Shot Federated Learning
- Data-Free One-Shot Federated Learning Under Very High Statistical Heterogeneity
- Parametric Feature Transfer: One-shot Federated Learning with Foundation Models
- OFL-W3: A One-shot Federated Learning System on Web 3.0
- Bounds on the Voter Model in Dynamic Networks
- On the h-Majority Dynamics with Many Opinions
- Simple dynamics for plurality consensus
- Simple dynamics for plurality consensus
- Convergence Speed of Binary Interval Consensus
- Which mode is better for federated learning? Centralized or Decentralized
- Beyond spectral gap: the role of the topology in decentralized learning
- A Fair Comparison of Graph Neural Networks for Graph Classification
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- One Communication Round is All It Needs for Federated Fine-Tuning Foundation Models