arXiv CS open access

Stream Learning: Partition-Fair Gossip Learning Without Tokens

2026 · arxiv_cs

arXiv CS · Papers · 2026

cloud distributed-computing parallel-computing

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Stream Learning: Partition-Fair Gossip Learning Without Tokens Fabien Mathieu Swapcard, Paris, France Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

Alexandre Pham Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

Maria Potop-Butucaru Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

Sébastien Tixeuil Sorbonne Université, CNRS, LIP6, F-75005 Paris, France Institut Universitaire de France, Paris, France

Abstract In gossip learning, a network of nodes trains a shared model collaboratively, without a central coordi nator, by repeatedly exchanging parts of their local models. The state-of-the-art protocol, Partitioned Token Gossip Learning (PTGL) of Hegedüs et al., splits the weight matrix into 𝑆 fixed partitions and disseminates them using a token-based fairness mechanism coupled with per-neighbor metadata exchange. We revisit partition scheduling by analogy with peer-to-peer live streaming, where model partitions act as video chunks and partition age acts as chunk scarcity. The analogy yields a design space of two-stage selection strategies (partition first, or neighbor first), from which we instantiate ten concrete protocols collectively called Stream Learning. Our main finding is that the simplest of these protocols, which transmits the locally least-trained partition to a uniformly random neighbor (Ri), matches PTGL on fault-free workloads while requiring neither token counters nor metadata exchange. Under an adversarial 30% permanent crash of the best-performing nodes, Ri matches or outperforms PTGL across all complete-graph configurations tested, with the gap reaching 5.53% on HAR and 5.41% on MNIST in the most heterogeneous regime (Dirichlet 𝛽 = 0.1). In our experiments, partition fairness, captured by a single local rule on partition age, accounts for the gap; token-based rate control and utility maximization do not improve over this rule and, under heterogeneity, sit below it. Keywords and phrases Gossip Learning, Decentralized Machine Learning, Empirical Crash Tolerance, Partition Scheduling Related Version Conference version to appear in the proceedings of SSS 2026 (Springer LNCS). Acknowledgements Experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).

Introduction

Many machine learning workloads (federated mobile devices, IoT swarms, cross-institution medical data) preclude centralizing the training data on a single server, whether for privacy, regulatory, or bandwidth reasons. Decentralized learning paradigms address this constraint by training a shared model through repeated exchanges of model parameters, with no transfer of raw data. Federated Learning (FL) [14] keeps data local but routes every update through a central server. The server is convenient, but it is also a synchronization bottleneck and a single point of failure. A fully decentralized family of protocols removes it and lets nodes exchange

Stream Learning parameters directly with their peers: by gossiping with one neighbor at a time [9, 15], by broadcasting to the whole neighborhood (epidemic learning [18]), or through hub-based variants [12]. The resilience of these protocols to faults and adversarial behavior is an active line of work [16]. We work in the gossip regime throughout the paper: at each activation, a node sends a representation of its current model to a single neighbor, which merges it into its own. The design space of partitioned gossip learning is organized around two scheduling ques tions: (i) what to send (the full model, a random sample of parameters, or a fixed partition), and (ii) when, and to whom. Hegedüs et al. [10] answer (i) with a partitioning scheme that splits the weight matrix into 𝑆 disjoint blocks, and (ii) with a token mechanism that locally balances proactive periodic sends against reactive sends, in order to prevent both flooding and starvation. The resulting algorithm, Partitioned Token Gossip Learning (PTGL), matches federated learning on the workloads it studies. Subsequent work targets adjacent axes of the same design space rather than the partition-scheduling question itself: Biswas et al. [4] maximize bandwidth use in asynchronous, straggler-prone environments; Biswas et al. [3] synchronize sample exchange in the round-based setting through a perround gossip matrix; Hu et al. [11] propose a pull-based variant where nodes request samples rather than push them; Biswas et al. [2] add a privacy layer via shared-seed disjoint subsampling.1 None of these works questions whether the control overhead they add (token counters, synchronization phases, per-neighbor metadata) is actually necessary for partition scheduling. In this paper, we revisit the when/who question by analogy with peer-to-peer live streaming [5]: model partitions play the role of video chunks, and the local age of a partition plays the role of chunk scarcity. The analogy yields a structured design space of two-stage selection strategies. A primary selection picks either the neighbor or the partition first; a secondary selection picks the other under the constraint already imposed. From this space we instantiate ten concrete protocols. The simplest of them, which sends the locally leasttrained partition to a uniformly random neighbor (we denote it Ri), matches PTGL on fault-free workloads while using neither token counters nor metadata exchange between neighbors. Under 30% permanent node crashes, Ri matches or outperforms PTGL across every configuration tested, with the gap widening as data heterogeneity grows. Convergence in partitioned gossip learning appears to be driven by fairness across partitions, not by utility maximization or token-based scheduling; PTGL’s token machinery can be dropped without loss of accuracy, with a measurable gain in crash tolerance. Contributions. We frame partitioned gossip learning under a peer-to-peer streaming analogy and define an explicit design space of two-stage partition-scheduling strategies (Section 4). We instantiate ten concrete strategies, including a lightweight optional metadata channel (map messages) for sharing partition ages between neighbors, and evaluate them against PTGL on MNIST and HAR across two Dirichlet-controlled data heterogeneity regimes (𝛽 ∈ {0.1, 100}). We study an adversarial crash setting in which the 30% of nodes with the highest individual test accuracy (BoTS) fail permanently, modeling a wipe-out of the most valuable participants.

The fragment construction of Biswas et al. [3, 4] diverges from the model partitioning of Hegedüs et al. [10]. To keep the comparison principled, we adopt the latter throughout this paper.

F. Mathieu, A. Pham, M. Potop-Butucaru, and S. Tixeuil

The Ri strategy matches or outperforms PTGL in every scenario, with the largest margin under adversarial crashes (5.53% on HAR at 𝛽 = 0.1 with 30% of the nodes failing). Ri uses neither tokens nor the map-message metadata channel: its selection rule reads only the local age vector.

System Model

Our system is modeled by an undirected, connected graph 𝐺 = (𝑉 , 𝐸) with 𝑛 = |𝑉 | nodes. Two nodes 𝑢, 𝑣 ∈ 𝑉 can communicate iff (𝑢, 𝑣) ∈ 𝐸. The state of 𝑢 is described by its local variables. A configuration of the system is the set of states of all nodes; an execution is a sequence of configurations where each transition results from an event: transmission of a message between two neighboring nodes, or local computation modifying the state of a node. We consider a round-based synchronous message-passing system [1]. The execution is divided into rounds. Each node 𝑢 has an incoming queue 𝐼𝑢 and an outgoing queue 𝑂𝑢 . During a round 𝑟, each node 𝑢 can perform a finite number of local actions: processing received messages, periodic activation, local computation. Between round 𝑟 and round 𝑟 + 1, all messages placed in 𝑂𝑢 destined for a neighbor 𝑣 are transferred to 𝐼𝑣 . Messages are never lost. The communication channels are FIFO and the transmission delays are bounded. We consider both fault-free and crash-prone models [1]. In the crash-prone model, up to 𝑓 < 𝑛 nodes stop executing their code at some point during the execution and never recover.

Gossip Learning Framework

We briefly recall the gossip learning framework of Hegedüs et al. [10]. Two mechanisms are central to it. A partition mechanism reduces message size: instead of transmitting the full set of model parameters, a node sends a single partition, a fixed slice of the weight matrix. A token mechanism regulates the message flow by interpolating between proactive (periodic) and reactive (event-triggered) sends, so as to prevent both flooding and starvation. A self-contained background on supervised machine learning and federated learning is provided in Appendix A. Partition mechanism. Each node 𝑢 holds a fixed local dataset 𝐷𝑢 and trains a model 𝑚𝑢 = (𝑤𝑢 , 𝑏𝑢 , 𝑡𝑢 ), where 𝑤𝑢 are the weights, 𝑏𝑢 is the bias, and 𝑡𝑢 ∈ ℕ𝑆+1 is an age vector recording, for each partition 𝑗 ∈ ⟦0, 𝑆 − 1⟧ and for the bias, the number of updates applied. All nodes share the same architecture and partitioning scheme: a weight matrix 𝑤 is split into 𝑆 disjoint partitions 𝑤[0], …, 𝑤[𝑆 − 1]. Let 𝒫︀(𝑤) ∈ {0, …, 𝑆 − 1}𝑑×𝐾 , where 𝐾 is the number of output classes and 𝑑 the input dimension, denote the partition assignment of 𝑤; we use the explicit assignment 𝒫︀(𝑤)𝑘,𝑙 = (𝑘𝐾 + 𝑙) mod 𝑆, which is one of the round-robin schemes consistent with the partitioning convention of [10]. The bias is shared across all partitions. Eq. (1) illustrates this scheme for 𝑑 = 3, 𝐾 = 5, 𝑆 = 3: each cell of 𝒫︀(𝑤) holds the partition index of the corresponding weight, and the 𝐾 entries of 𝑏 (one per output class, shown as •) are shared across all partitions. 0 1 2 0 1 𝒫︀(𝑤) = 0 1 2 0 1 𝑏 = (• • • • •) 0 1 2 0 1 [ ]

(1)

A node 𝑟 disseminates a slice of its model via a model message for partition 𝑗, defined as the 5-tuple msg = (𝑗, 𝑤𝑟 [𝑗], 𝑏𝑟 , 𝑡𝑟 [𝑗], 𝑡𝑟 [𝑆]), where 𝑤𝑟 [𝑗] denotes the 𝑗-th partition of 𝑤𝑟 (defined above as a slice of weights, indexed by the original coordinates 𝑖 such that 𝑖 mod 𝑆 = 𝑗).

Stream Learning

𝑚𝑢 = (𝑤𝑢 , 𝑏𝑢 , 𝑡𝑢 ) ← initial values 𝑐𝑢 ← initial values loop Wait(Δ) 𝑗 ← SelectPart() with probability 𝜎(𝑐𝑢 [𝑗]) do 𝑣 ← SelectRandomPeer() SendModelMessage(𝑣, 𝑗) else 𝑐𝑢 [𝑗] ← 𝑐𝑢 [𝑗] + 1 procedure OnReceiveModelMessage(msg = (𝑗, 𝑤𝑟 [𝑗], 𝑏𝑟 , 𝑡𝑟 [𝑗], 𝑡𝑟 [𝑆])) Merge(𝑚𝑢 , msg) Train(𝑚𝑢 , 𝐷𝑢 ) 𝑥 ← 𝜑(𝑐𝑢 [𝑗]) 𝑐𝑢 [𝑗] ← 𝑐𝑢 [𝑗] − 𝑥 repeat 𝑥 times 𝑣 ← SelectRandomPeer() SendModelMessage(𝑣, 𝑗) Algorithm 1 Partitioned Token Gossip Learning, running on node 𝑢. Native asynchronous presentation of [10]; Section 5 details the synchronous mapping used in simulations.

The bias 𝑏𝑟 is included in every model message to keep merges consistent. Upon reception, the recipient executes Merge followed by Train. Both operations modify 𝑚𝑢 in place. Train(𝑚𝑢 , 𝐷𝑢 ) performs one stochastic gradient descent step on 𝐷𝑢 (cf. Appendix A) and increments every component of 𝑡𝑢 by the batch size. Merge(𝑚𝑢 , msg) destructures the message msg, overwrites 𝑤𝑢[𝑗] and 𝑏𝑢 with the ageweighted average of the local and received values weighted by 𝑡𝑢[𝑗] , 𝑡𝑟[𝑗] (resp. 𝑡𝑢[𝑆] , 𝑡𝑟[𝑆] for the bias), and sets 𝑡𝑢[𝑗] and 𝑡𝑢[𝑆] to the element-wise maxima of the corresponding local and received ages. Token mechanism. Each node 𝑢 maintains a counter 𝑐𝑢 ∈ ℤ𝑆 . On each activation, 𝑢 samples 𝑗 ∈ ⟦0, 𝑆 − 1⟧ uniformly; with probability 𝜎(𝑐𝑢 [𝑗]) (where 𝜎 is increasing), it sends a model message for partition 𝑗 to a random neighbor, otherwise it increments 𝑐𝑢 [𝑗]. Upon receiving a model message for partition 𝑗, 𝑢 merges, trains, then sends 𝜑(𝑐𝑢 [𝑗]) model messages for partition 𝑗 to random neighbors2 and decrements 𝑐𝑢 [𝑗]. The counter acts as a fairness mechanism: a partition that has not been sent for a long time sees its transmission probability increase, while a reception triggers a burst of reactive sends. The full procedure is given in Algorithm 1.

Stream Learning Framework

We now turn to our contribution, Stream Learning. Stream Learning inherits the partition mechanism of PTGL: a model message for partition 𝑗 sent by node 𝑢 carries the same payload (𝑗, 𝑤𝑢 [𝑗], 𝑏𝑢 , 𝑡𝑢 [𝑗], 𝑡𝑢 [𝑆]) and triggers Merge then Train on reception. What differs is the rule that decides which partition to send to whom, and the (optional) metadata used to inform that rule. Following the P2P-streaming analogy of Section 1, we cast partition scheduling as a two-stage selection problem and instantiate an explicit family of strategies. To inform 2

𝜑 takes integer values and is applied on the bounded range of 𝑐𝑢 [𝑗], so the number of reactive sends per arrival is bounded.

F. Mathieu, A. Pham, M. Potop-Butucaru, and S. Tixeuil these decisions, Stream Learning introduces a second, lightweight message type: the map message, which carries only the age vector 𝑡𝑢 (𝑆 + 1 integers, several orders of magnitude smaller than a model message). Each node 𝑢 maintains, for each neighbor 𝑣, an estimate ̃𝑡𝑣 of 𝑡𝑣 , updated each time 𝑢 receives a map message from 𝑣 (we omit the dependence on 𝑢 for readability). On activation, 𝑢 sends a map message to a random neighbor and a model message chosen according to a strategy 𝑠. We define the utility of partition 𝑗 for a transmission from 𝑢 to 𝑣 as 𝑈 (𝑢, 𝑣, 𝑗) = 𝑡𝑢 [𝑗] − ̃𝑡𝑣 [𝑗], which measures how far 𝑣 is estimated to lag behind 𝑢 on 𝑗. We say 𝑗 is useful for 𝑣 when 𝑈 (𝑢, 𝑣, 𝑗) ≥ 0. The procedure is given in Algorithm 2. A strategy 𝑠 is a two-stage rule: a primary selection picks the first dimension (either the neighbor or the partition), and a secondary selection picks the second under the constraint imposed by the first. We consider four primary selections (three neighbor-first, one partition-first): R: choose the neighbor uniformly at random. U: choose the neighbor 𝑣 maximizing |{𝑗 : 𝑈 (𝑢, 𝑣, 𝑗) ≥ 0}| (the neighbor for whom the most partitions are useful). V: associate to each neighbor 𝑣 a partition 𝑗 drawn uniformly from those maximizing 𝑈 (𝑢, 𝑣, 𝑗); pick a neighbor uniformly; let 𝑗 be its associated partition; finally restrict the neighbor choice to those associated with that 𝑗 (a vote-like procedure). B (partition first): choose 𝑗 maximizing 𝑡𝑢 [𝑗] (the most-trained local partition). And five secondary selections: r: choose the partition uniformly at random. a: choose uniformly among partitions of maximal 𝑡𝑢 [𝑗]. i: choose uniformly among partitions of minimal 𝑡𝑢 [𝑗]. m: if 𝑣 is fixed, choose 𝑗 of maximal age among partitions useful to 𝑣; if 𝑗 is fixed, choose the neighbor that maximizes 𝑈 (𝑢, 𝑣, 𝑗) among the available ones. u: choose uniformly among partitions of utility 𝑈 ≥ 0. The four primary selections and the five secondary selections yield 4 × 5 = 20 combinations. We retain ten of them and discard the others either as semantically redundant (e.g. B-a collapses to B on its own, while B-i contradicts the partition-first primary) or as a priori unpromising (e.g. U-r uses utility to pick a neighbor but then makes a uniformly random partition choice, discarding the utility signal on the side where it could most naturally be used). The ten retained strategies are Rr, Ra, Rm, Ri, Ru, Bu, Vu, Vm, Uu and Um, summarized in Table 1. r

—

Table 1 The ten Stream Learning strategies retained for evaluation. Rows are primary selec tions, columns are secondary selections. Cells marked “—” are either semantically redundant with another strategy or a priori unpromising and are not evaluated.

Whenever a selection rule yields multiple candidates with the same maximizer or minimizer, ties are broken uniformly at random throughout the paper.

Stream Learning

𝑚𝑢 = (𝑤𝑢 , 𝑏𝑢 , 𝑡𝑢 ) ← initial values ̃𝑡 ← initial values at each round do 𝑣 ← SelectRandomPeer() SendMapMessage(𝑣) (𝑣, 𝑗) ← UseStrategy(𝑠, ̃𝑡) SendModelMessage(𝑣, 𝑗) procedure OnReceiveMapMessage(msg = (𝑟, 𝑡𝑟 )) ̃𝑡[𝑟] ← 𝑡𝑟 procedure OnReceiveModelMessage(msg = (𝑗, 𝑤𝑟 [𝑗], 𝑏𝑟 , 𝑡𝑟 [𝑗], 𝑡𝑟 [𝑆])) Merge(𝑚𝑢 , msg) Train(𝑚𝑢 , 𝐷𝑢 ) Algorithm 2 Push-based Stream Learning with strategy 𝑠, running on node 𝑢.

Map messages are optional. The metadata channel of Algorithm 2 (the ̃𝑡 table and the SendMapMessage/OnReceiveMapMessage handlers) is only consulted by strategies whose selection rule reads the ages of partitions held by other nodes, that is, the U-, V- and m-family strategies. Strategies in the R-i / R-a / R-r / B-u families derive their decision from the local age vector 𝑡𝑢 alone, in which case the entire map-message machinery can be elided at deployment time. Ri, the focus of Section 6, never invokes it.

Simulation Methodology

Round-based synchronous execution. The execution model follows Section 2: time is divided into rounds, each node 𝑢 has incoming and outgoing queues 𝐼𝑢 and 𝑂𝑢 , and messages placed in 𝑂𝑢 at round 𝑟 are delivered to neighbors’ incoming queues by round 𝑟 + 1. Within a round, 𝑢 processes at most one model message from 𝐼𝑢 (since a merge triggers a local training step, which is the costly operation), but may process all pending map messages, which carry only the age vector 𝑡𝑢 and require no training. All nodes are activated at the beginning of each round. Mapping algorithms to the synchronous model. PTGL (Algorithm 1) is presented in its native asynchronous form, paced by an activation period Δ; we simulate it by treating each iteration of its activation loop as one round, making Δ implicit. The proactive draw 𝜎 remains a per-round Bernoulli, and the reactive burst 𝜑 is capped at 2 model messages per round. With the 𝜎 and 𝜑 of Hegedüs et al. [10], the token counters remain bounded and PTGL sends one model message per round on average. Stream Learning (Algorithm 2) is presented directly in synchronous form: each node sends one map message and one model message per round. The incoming queue 𝐼𝑢 handles the resulting concurrent arrivals between rounds. Gossip and Stream Learning algorithms. For Partitioned Token Gossip Learn ing [10] (PTGL), we use the 𝜎 and 𝜑 functions of Hegedüs et al. [10], with counters initialized to the average value reported in [7]. We set the number of partitions to 𝑆 = 10. For Stream Learning, the map message carries only 𝑆 + 1 integers and is several orders of magnitude smaller than a model message. Datasets and machine learning model. We use the MNIST and HAR datasets, each split into a training set 𝒟︀train and a test set 𝒟︀test . An MNIST instance is a pair (𝑥, 𝑦) ∈ ℝ784 × ⟦0, 9⟧, where 𝑥 is a 28 × 28 pixel image and 𝑦 the depicted digit. An HAR instance is

F. Mathieu, A. Pham, M. Potop-Butucaru, and S. Tixeuil a pair (𝑥, 𝑦) ∈ ℝ561 × ⟦0, 5⟧, where 𝑥 aggregates smartphone sensor readings and 𝑦 encodes one of six physical activities. Instances of 𝒟︀train are partitioned (without replacement) across nodes, so that 𝐷𝑢 ∩ 𝐷𝑣 = ∅ for 𝑢 ≠ 𝑣. The characteristics of the datasets are summarized in Table 2. Datasets

MNIST

HAR

Training set size

60000

7352

Test set size

10000

2497

Input dimensions

784

561

Number of classes

Class imbalance

none

slight

Table 2 Characteristics of datasets studied in this paper

Each node 𝑢 trains a multinomial logistic regression, as in [10] and recalled in Section 3. Local datasets. We control the heterogeneity of the per-node local datasets via a Dirichlet distribution of concentration parameter 𝛽. A high 𝛽 produces near-uniform pernode label distributions (we refer to 𝛽 = 100 as the i.i.d. scenario); a low 𝛽 produces a highly skewed split (we refer to 𝛽 = 0.1 as the most heterogeneous non-i.i.d. scenario). We illustrate both regimes in Figure 1. Topology and scale. Simulations use a complete graph or a random 20-regular graph, both with 𝑛 = 100. The choice of a complete graph isolates the effect of the selection strategy from the influence of the topological structure, a known confounder in gossipprotocol evaluation. The choice of a random 20-regular graph is motivated by the fact that PTGL’s original authors studied their algorithm with a 20-out graph, and that some of our algorithms (e.g., Vm) require bidirectional links to work (otherwise, state messages are useless). The choice of 𝑛 = 100 is dictated by the heterogeneous regime: generating a usable Dirichlet split at 𝛽 = 0.1 becomes impractical at the larger scales (𝑛 > 4000) used in earlier gossip-learning studies.3 Metric. We evaluate both gossip learning and stream learning in terms of average accuracy, defined as the fraction of correct predictions on the global test set, averaged over all participating nodes. Higher values indicate better performance. Reproducibility. Each configuration is averaged over five independent runs (15 runs in Section 6.3). The standard deviation across runs is small relative to the curve separations of interest; we therefore omit error bars from the figures for readability. The code is based on gossipy [17] and is available at [13]. Model variants. On top of the base protocol of Section 4 and PTGL, we study two variants: Node failures (BoTS). At a given round, the 30% of nodes with the highest accuracy on the global test set crash simultaneously and permanently. This Best-on-Test-Set policy models an adversarial wipe-out of the most valuable participants. Crashed nodes are excluded from the reported metrics. The failure round is chosen so that the system has had enough rounds to start converging but is not yet at the plateau: 𝑟 = 21 at 𝛽 = 100 on both datasets, 𝑟 = 16 at 𝛽 = 0.1 on HAR, and 𝑟 = 11 at 𝛽 = 0.1 on MNIST (the MNIST runs converge faster, so the failure is triggered earlier on that dataset). 3

At larger scales, the 𝛽 = 0.1 regime produces nodes whose local sets are so skewed that some classes are entirely missing from many local sets, which prevents meaningful local training. We accept the smaller 𝑛 in exchange for being able to study the regime where the strategies actually differ.

Classes

Stream Learning

Classes

Client (a) 𝛽 = 0.1

Client (b) 𝛽 = 100

Figure 1 MNIST train set split across 10 clients using a Dirichlet distribution of parameter varying from 𝛽 = 0.1 (left) to 𝛽 = 100 (right), shown with 10 clients for visual clarity (experiments in Section 6 use 𝑛 = 100). The larger the circle is for a node and a class, the more data of this class is concentrated in this node.

Batched merge. Nodes process all model messages in 𝐼𝑢 within a single round: they perform one merge per partition represented in 𝐼𝑢 (i.e. from 1 to 𝑆 merges) before triggering a single local update.

Simulation Results

We now report our simulation results, under the methodology of Section 5. We proceed by elimination: we start in Section 6.1 by comparing four representatives of the design space of Table 1 against PTGL on the base protocol; we eliminate the strategies that exhibit anti-patterns (explained later in this section). The survivors are then evaluated under node crashes (Section 6.2), and finally under a batched-merge protocol variant (Section 6.3). Of the ten strategies of Table 1, four exhibit qualitatively distinct trajectories and are tracked throughout: Ri (the partition-age minimizer), Ra (its opposite, the partition-age maximizer), Rr (the degree-zero baseline that uses neither tokens nor metadata), and Vm (the best representative of the utility-driven family). The remaining six strategies sit between these representatives and are omitted for readability. Specialized to any R-secondary strategy (Ri, Ra, or the degree-zero baseline Rr), the generic protocol of Algorithm 2 collapses to Algorithm 3: no map-message exchange, no token counters, no per-neighbor metadata. The scheduling logic reduces to a single partitionselection rule on the local age vector 𝑡𝑢 , parameterized by the secondary selector 𝑠 (cf. Table 1).

6.1

Base Scenario

Figure 2 shows accuracy under the fault-free protocol for the four representative strategies Ri, Ra, Rr, Vm, and the PTGL baseline PT, across both datasets and both heterogeneity regimes in a complete graph topology. In the homogeneous regime (𝛽 = 100, top row), Ri, Rr and PT converge together to within visible noise on both datasets, plateauing around 0.88. Ra and Vm both trail by a small margin. With i.i.d. local data, partition-level scheduling is largely redundant: the degree-zero baseline Rr, which uses no age and no metadata, tracks the state-of-the-art PT. In the heterogeneous regime (𝛽 = 0.1, bottom row), Ri retains the convergence shape it had at 𝛽 = 100 and a comparable terminal plateau (within 4 points of accuracy), whereas both PT and Rr drop visibly. The final ordering is Ri > Rr > PT on both datasets, with Ri above PT by 14.38% on HAR and 12.15% on MNIST. The ordering reveals two points worth highlighting. First, PT plateaus below Rr by 3.94% on HAR and 7.81% on MNIST: when

F. Mathieu, A. Pham, M. Potop-Butucaru, and S. Tixeuil

𝑚𝑢 = (𝑤𝑢 , 𝑏𝑢 , 𝑡𝑢 ) ← initial values at each round do 𝑣 ← SelectRandomPeer() 𝑗 ← PickPartition(𝑡𝑢 , 𝑠) SendModelMessage(𝑣, 𝑗)

▷ 𝑠 ∈ {𝑖, 𝑎, 𝑟}

procedure PickPartition(𝑡𝑢 , 𝑠) if 𝑠 = 𝑖 : return argmin𝑘∈{0,…,𝑆−1} 𝑡𝑢 [𝑘] if 𝑠 = 𝑎 : return argmax𝑘∈{0,…,𝑆−1} 𝑡𝑢 [𝑘] if 𝑠 = 𝑟 : return Uniform({0, …, 𝑆 − 1})

▷ Ri ▷ Ra ▷ Rr

procedure OnReceiveModelMessage(msg = (𝑗, 𝑤𝑟 [𝑗], 𝑏𝑟 , 𝑡𝑟 [𝑗], 𝑡𝑟 [𝑆])) Merge(𝑚𝑢 , msg) Train(𝑚𝑢 , 𝐷𝑢 )

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Ri PT Rr Ra Vm

100 Round 𝑟 (a) HAR; 𝛽 = 100

1000

Ri PT Rr Ra Vm

100 Round 𝑟 (c) HAR; 𝛽 = 0.1

Accuracy

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Accuracy

Algorithm 3 Stream Learning under any R-secondary strategy (𝑠 ∈ {𝑖, 𝑎, 𝑟}), running on node 𝑢. Compared to Algorithm 2, the map-message machinery is removed and the partition selection reads only the local age vector. The three secondary rules differ only in how they pick a partition: the least-trained (Ri), the most-trained (Ra), or a uniformly random one (Rr).

1000

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Ri PT Rr Ra Vm

100 Round 𝑟 (b) MNIST; 𝛽 = 100

1000

Ri PT Rr Ra Vm

100 Round 𝑟 (d) MNIST; 𝛽 = 0.1

1000

Figure 2 Complete graph, average accuracy as a function of rounds under the fault-free protocol. Rows correspond to 𝛽 ∈ {100, 0.1}, columns to HAR and MNIST.

local data is skewed, the token machinery underperforms uniform random selection, which suggests that its fairness mechanism is misaligned with the partition-level imbalance induced by heterogeneity. Second, Ri leads Rr by 10.44% on HAR and 4.34% on MNIST. This isolates the contribution of the local age vector: that single piece of state, on its own, closes the heterogeneity gap. Neither observation makes use of PT’s tokens or of the metadata channel of Algorithm 2; Ri reads only 𝑡𝑢 , as shown in Algorithm 3.

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Ri PT Rr Ra Vm

100 Round 𝑟 (a) HAR; 𝛽 = 100

1000

Ri PT Rr Ra Vm

100 Round 𝑟 (c) HAR; 𝛽 = 0.1

Accuracy

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Accuracy

Stream Learning

Accuracy

1000

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Ri PT Rr Ra Vm

100 Round 𝑟 (b) MNIST; 𝛽 = 100

1000

Ri PT Rr Ra Vm

100 Round 𝑟 (d) MNIST; 𝛽 = 0.1

1000

Figure 3 Random 20-regular graph, average accuracy as a function of rounds under the faultfree protocol. Rows correspond to 𝛽 ∈ {100, 0.1}, columns to HAR and MNIST.

Anti-patterns. Two strategies exhibit pathological behavior and are eliminated from the rest of the analysis. Ra, which transmits the locally most-trained partition, sustains a reinforcement loop: high-age partitions get repeatedly sent and trained while others stagnate. The effect is mild at 𝛽 = 100 but severe at 𝛽 = 0.1 on HAR (Ra ends 31.81% below Ri). Vm, which optimizes utility through map-message-driven coordination, suffers from a related issue already visible at 𝛽 = 100: its joint maximization on neighbor and partition tends to send the same partition to the same node repeatedly, producing pseudo-collisions that defeat the intended diversification. At 𝛽 = 0.1 the effect compounds with heterogeneity and Vm plateaus around 0.54 on both datasets, i.e. 30.15% below Ri on HAR and 30.68% on MNIST. The three surviving strategies Ri, Rr, and PT are carried into the next two subsections, which test whether their ranking is preserved when 30% of the best-performing nodes are removed (Section 6.2) and when nodes batch their merges per round (Section 6.3). Similarly to Figure 2, Figure 3 shows results under the fault-free protocol, but in a random 20-regular graph. At convergence time, the ranking observed in the complete topology case remains the same here for both homogeneous and heterogeneous distributions. However, we do observe differences in convergence rates and values, especially for Ri in the heterogeneous regime (𝛽 = 0.1) for MNIST.

6.2

Node failures

Figure 4 overlays the BoTS failure scenario (solid) against the no-failure baseline (dashed) for the three survivors of Section 6.1. The 30% highest-accuracy nodes are removed at the

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Ri (NF) Ri PT (NF) PT Rr (NF) Rr

100 Round 𝑟 (a) HAR; 𝛽 = 100

1000

Ri (NF) Ri PT (NF) PT Rr (NF) Rr

100 Round 𝑟 (c) HAR; 𝛽 = 0.1

Accuracy

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Accuracy

F. Mathieu, A. Pham, M. Potop-Butucaru, and S. Tixeuil

1000

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Ri (NF) Ri PT (NF) PT Rr (NF) Rr

100 Round 𝑟 (b) MNIST; 𝛽 = 100

1000

Ri (NF) Ri PT (NF) PT Rr (NF) Rr

100 Round 𝑟 (d) MNIST; 𝛽 = 0.1

1000

Figure 4 Complete graph, average accuracy under best-on-test-set node failures (BoTS). The 30% of nodes with the highest individual test accuracy crash at the round marked by the vertical green line: round 21 at 𝛽 = 100 on both datasets (top row), round 16 on HAR 𝛽 = 0.1 (panel (c)), and round 11 on MNIST 𝛽 = 0.1 (panel (d), as MNIST converges faster). Solid curves are post-crash trajectories (BoTS); dashed curves are the corresponding no-failure baselines (NF) for reference. Rows correspond to 𝛽 ∈ {100, 0.1}, columns to HAR and MNIST.

round marked by the vertical green line, then excluded from the accuracy metric, and the run continues in a complete graph topology. At 𝛽 = 100 (top row), BoTS has essentially no effect. Ri, Rr and PT all complete the simulation within visible noise of their no-failure baselines; both PT and Rr finish very slightly above their NF curves on HAR, which foreshadows the recovery effect we describe below. Removing the 30% best-accuracy nodes does not stress the system in this regime, because the surviving nodes hold equivalent, redundant local datasets. At 𝛽 = 0.1 (bottom row), Ri remains clearly ahead under BoTS, but the gaps compress. Ri takes a mild post-crash dip (under 2 points of accuracy) and recovers smoothly, ending 5.53% above PT on HAR and 5.41% above on MNIST. The Ri / Rr gap also shrinks but stays in favor of Ri (6.74% on HAR, 2.42% on MNIST), while PT and Rr end close to each other (PT slightly ahead on HAR, Rr ahead on MNIST). The qualitative conclusion of Figure 2 carries over to the most stressful crash scenario we tested: local age information remains the differentiator. On the heterogeneous panels (c) and (d), both PT and, to a lesser extent, Rr eventually rise above their own no-failure baselines under BoTS: PT by 7.2 and 5.6 percentage points, Rr by 2.05 and 0.78 (HAR and MNIST respectively). Removing the 30% best-accuracy nodes thus improves the surviving nodes’ average accuracy under these two strategies. Ri shows no such effect and tracks its NF baseline closely, slightly below it. We report this pattern without a confirmed mechanistic explanation: it is consistent across our two datasets

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Ri (NF) Ri PT (NF) PT Rr (NF) Rr

100 Round 𝑟 (a) HAR; 𝛽 = 100

1000

Ri (NF) Ri PT (NF) PT Rr (NF) Rr

100 Round 𝑟 (c) HAR; 𝛽 = 0.1

Accuracy

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Accuracy

Stream Learning

Accuracy

1000

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Ri (NF) Ri PT (NF) PT Rr (NF) Rr

100 Round 𝑟 (b) MNIST; 𝛽 = 100

1000

Ri (NF) Ri PT (NF) PT Rr (NF) Rr

100 Round 𝑟 (d) MNIST; 𝛽 = 0.1

1000

Figure 5 Random 20-regular graph, average accuracy under best-on-test-set node failures (BoTS). The 30% of nodes with the highest individual test accuracy crash at the round marked by the vertical green line: round 21 at 𝛽 = 100 on both datasets (top row), round 16 on HAR 𝛽 = 0.1 (panel (c)), and round 11 on MNIST 𝛽 = 0.1 (panel (d), as MNIST converges faster). Solid curves are post-crash trajectories (BoTS); dashed curves are the corresponding no-failure baselines (NF) for reference. Rows correspond to 𝛽 ∈ {100, 0.1}, columns to HAR and MNIST.

but rests on a single failure mode (BoTS) and a single state-of-the-art baseline (PTGL), and a confirmation would require instrumenting per-node training trajectories across the failure event, which we leave to future work. A possible explanation is that even in a complete graph, due to the skewed data distribution, gossip learning algorithms are biased as pointed out by [8]. In our cases, nodes that perform well likely create biases towards their own data. Removing those nodes prevents them from continuously biasing the system and hurting overall performance. In essence, PT is similar to Rr (partitions sent proactively are chosen randomly), which would explain their similar behavior. It would also explain why Ri (which always sends the less trained partition, so the partition less likely to be biased) does not show this behavior. Similarly to Figure 4, Figure 5 shows results in the BoTS failures scenario, in a random 20-regular graph. Although there is no major difference from the complete graph topology in the homogeneous scenario (𝛽 = 100), the ranking observed earlier in the heterogeneous case is flipped. Under BoTS failures, we observe that Ri is slower than both Rr and PT. Due to the sparse nature of this topology, the fact that PT outperforms Ri with a 6.38% improvement (resp. 3.02%) on the MNIST (resp. HAR) dataset, while Rr outperforms Ri with a 8.03% improvement (resp. 7.04%) on the MNIST (resp. HAR) dataset suggests that under BoTS failures and specific topology, choosing a partition randomly is the decisive factor to recover faster from the failures, as Ri is inefficient here.

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Ri Ri (SM) PT PT (SM) Rr Rr (SM)

100 Round 𝑟 (a) HAR; 𝛽 = 100

1000

Ri Ri (SM) PT PT (SM) Rr Rr (SM)

100 Round 𝑟 (c) HAR; 𝛽 = 0.1

Accuracy

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Accuracy

F. Mathieu, A. Pham, M. Potop-Butucaru, and S. Tixeuil

1000

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Ri Ri (SM) PT PT (SM) Rr Rr (SM)

100 Round 𝑟 (b) MNIST; 𝛽 = 100

1000

Ri Ri (SM) PT PT (SM) Rr Rr (SM)

100 Round 𝑟 (d) MNIST; 𝛽 = 0.1

1000

Figure 6 Complete graph, batched-merge (solid) vs single-merge (dashed) for Ri, Rr, and PT. Rows: 𝛽 ∈ {100, 0.1}. Columns: HAR, MNIST. At 𝛽 = 100 (top row) BM and SM are visually indistinguishable for all three strategies. At 𝛽 = 0.1 (bottom row), BM has essentially no effect on Ri (already near-saturation) but lifts both laggards: roughly 10 points of accuracy on PT and 3 to 7 on Rr.

Also on the heterogeneous case, we still observe (to a lesser degree) the fact that PT under BoTS failures surpasses its baseline, while this is not the case for Rr.

6.3

Batched-merge variant

The last protocol variant of Section 5 lets each node process the entire incoming queue 𝐼𝑢 in one round: one merge per distinct partition received, then a single local update. We compare batched-merge (BM) against the single-merge base (SM, i.e. the protocol of Section 6.1) for the three survivors of Section 6.1 in a complete graph topology. Figure 6 shows the batched-merge trajectories alongside the single-merge baseline taken from Figure 2. At 𝛽 = 100 (top row), BM and SM are visually indistinguishable for all three strategies. At 𝛽 = 0.1 (bottom row), the two laggards of Section 6.1 both gain accuracy under BM: PT by 9.61% on HAR and 10.01% on MNIST, Rr by 7.37% on HAR and 3.51% on MNIST. Ri sits at the BM/SM common ceiling and gains essentially nothing. The ranking Ri ≥ Rr ≥ PT from Figure 2 is preserved under BM. For PT, the gain tracks its burstiness: PTGL emits up to one proactive plus two reactive model messages per round (Section 5), so a receiver’s incoming queue 𝐼𝑢 can hold several messages between rounds. Under SM the receiver processes only one per round, and the rest are deferred; the deferred merges are paid for as wasted training rounds on the corresponding partitions. Under BM the same receiver flushes all pending merges before its single local update, so PTGL’s bursts translate into integration progress rather than

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Ri Ri (SM) PT PT (SM) Rr Rr (SM)

100 Round 𝑟 (a) HAR; 𝛽 = 100

1000

Ri Ri (SM) PT PT (SM) Rr Rr (SM)

100 Round 𝑟 (c) HAR; 𝛽 = 0.1

Accuracy

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Accuracy

Stream Learning

Accuracy

1000

1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

Ri Ri (SM) PT PT (SM) Rr Rr (SM)

100 Round 𝑟 (b) MNIST; 𝛽 = 100

1000

Ri Ri (SM) PT PT (SM) Rr Rr (SM)

100 Round 𝑟 (d) MNIST; 𝛽 = 0.1

1000

Figure 7 Random 20-regular graph, batched-merge (solid) vs single-merge (dashed) for Ri, Rr, and PT. Rows: 𝛽 ∈ {100, 0.1}. Columns: HAR, MNIST. At 𝛽 = 100 (top row) BM and SM are visually indistinguishable for all three strategies. At 𝛽 = 0.1 (bottom row), BM has essentially no effect on Ri (already near-saturation) but lifts both laggards.

accumulated delay. Rr emits exactly one model message per round, like Ri, so per-receiver arrivals are similarly distributed and burstiness alone does not explain its gain. The likely mechanism is different: Rr picks a partition uniformly at random, which under skewed local data leaves some partitions chronically under-served at any given receiver. BM lets the receiver catch up on these partitions whenever they do arrive together with others in the same round, which Rr already needs more than Ri does because Ri picks the local underserved partition directly. The gain measured here is therefore not about absorbing bursts but about recovering from random misalignment. Similarly to Figure 6, Figure 7 shows the batched-merge trajectories alongside the singlemerge baseline, but in a random 20-regular graph. Similar to the observations made in Section 6.1 and Section 6.2, in the homogeneous case, results in the complete and random 20-regular graphs are close. In the heterogeneous case, we also observe that PT and Rr benefit from BM while Ri does not significantly gain from it.

Conclusion

We transposed peer-to-peer live-streaming strategies [5] to partitioned gossip learning and evaluated ten partition- and neighbor-selection strategies against the state-of-the-art tokenbased algorithm of Hegedüs et al. [10], by elimination across three settings: fault-free, adversarial 30% crash of best-performing nodes, and batched-merge. In a complete graph topology, one strategy emerges as the consistent leader: Ri, which sends the locally leasttrained partition to a uniformly random neighbor. Ri matches or outperforms PTGL in

F. Mathieu, A. Pham, M. Potop-Butucaru, and S. Tixeuil every configuration tested, while requiring neither token counters nor metadata exchange; it reads only the local age vector 𝑡𝑢 , and its margin over PT is largest under the realistic combination of adversarial crashes and data heterogeneity. However, in a random 20-regular graph topology, Ri outperforms PT and Rr in the fault-free and batched-merge scenario, but is inefficient in the adversarial 30% crash of best-performing nodes when data-distribution is skewed. In a complete graph topology, the structural reading is that PTGL’s token machinery (counters, 𝜎 and 𝜑 functions, reactive bursts) can be replaced by the rule “send the leasttrained partition you have”, with no loss of accuracy in the homogeneous regime and substantial gains in the heterogeneous one. Comparing Ri to its degree-zero baseline Rr (random partition, random neighbor, no age) isolates the contribution of the local age vector: under heterogeneity, Ri leads Rr substantially, both under the fault-free protocol and under BoTS crashes. The local age information thus carries the load, whereas the token machinery built on top of it actually underperforms uniform random selection in this regime. The batched-merge variant adds a complementary observation: at 𝛽 = 0.1 it lifts both PT and Rr while leaving Ri essentially unchanged. PT pays for its burstiness, Rr for random partition picks under heterogeneity, and BM mitigates both pathologies (see Section 6.3 for the detailed mechanisms); Ri exhibits neither and the merge policy is moot. The ranking Ri ≥ Rr ≥ PT is preserved under BM. From the perspective of distributed systems, partition scheduling under Ri reduces to a stateless, parameter-free local rule, which simplifies analysis, deployment, and reasoning about failure modes. In a random 20-regular graph topology, the observations made in the complete graph topology remain, except for one particular setting (adversarial failures and skewed data distribution). Prioritizing the less trained partition is then inefficient, when compared to the other 2 strategies selected, which use random partition selection. This study has clear limitations. Our PTGL implementation transcribes the original protocol into the synchronous round-based model of Section 5 with the reactive burst capped at 2 messages per round; we did not independently validate this against the published asynchronous behavior, so all PTGL numbers should be read as relative to our simulator. Beyond these limitations, extending the comparison to deeper architectures, richer bench marks, asynchronous settings [3, 4], and a formal convergence analysis of Ri, are all obvious next steps.

Stream Learning References [1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11] [12]

[13]

Hagit Attiya and Jennifer Lundelius Welch. 2004. Distributed Computing: Fundamen tals, Simulations, and Advanced Topics (2nd ed ed.). Wiley. https://doi.org/10.1002/ 0471478210 Sayan Biswas, Mathieu Even, Anne-Marie Kermarrec, Laurent Massoulié, Rafael Pires, Rishi Sharma, and Martijn de Vos. 2024. Noiseless Privacy-Preserving Decentralized Learning. In PETS 2025 - 25th Privacy Enhancing Technologies Symposium, July 2024. 824. https://doi.org/10.56553/popets-2025-0043 Sayan Biswas, Davide Frey, Romaric Gaudel, Nirupam Gupta, Anne-Marie Kermarrec, Dimitri Lerévérend, Rafael Pires, Rishi Sharma, François Taïani, and Martijn de Vos. 2026. Mosaic Learning: A Framework for Decentralized Learning with Model Fragmentation. Retrieved from http://arxiv.org/abs/2602.04352 Sayan Biswas, Anne-Marie Kermarrec, Alexis Marouani, Rafael Pires, Rishi Sharma, and Martijn de Vos. 2025. Boosting Asynchronous Decentralized Learning with Model Fragmentation. In Proceedings of the ACM on Web Conference 2025 (WWW '25), April 2025. Association for Computing Machinery, 685–696. https://doi.org/10.1145/3696410. 3714872 Thomas Bonald, Laurent Massoulié, Fabien Mathieu, Diego Perino, and Andrew Twigg. 2008. Epidemic Live Streaming: Optimal Performance Trade-Offs. In SIGMETRICS '08 - ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems - 2008, June 2008. ACM, 325–336. https://doi.org/10.1145/1375457. 1375494 Léon Bottou. 2012. Stochastic Gradient Descent Tricks. In Neural Networks: Tricks of the Trade: Second Edition, Grégoire Montavon, Geneviève B. Orr and Klaus-Robert Müller (eds.). Springer, 421–436. https://doi.org/10.1007/978-3-642-35289-8_25 Gábor Danner and Márk Jelasity. 2018. Token Account Algorithms: The Best of the Proactive and Reactive Worlds. In 2018 IEEE 38th International Conference on Distrib uted Computing Systems (ICDCS), July 2018. 885–895. https://doi.org/10.1109/ICDCS. 2018.00090 Lodovico Giaretta and Šarūnas Girdzijauskas. 2019. Gossip Learning: Off the Beaten Path. In 2019 IEEE International Conference on Big Data (Big Data), December 2019. 1117–1124. https://doi.org/10.1109/BigData47090.2019.9006216 István Hegedűs, Gábor Danner, and Márk Jelasity. 2019. Gossip Learning as a Decen tralized Alternative to Federated Learning. In Distributed Applications and Interoperable Systems (Lecture Notes in Computer Science), 2019. Springer International Publishing, 74–90. https://doi.org/10.1007/978-3-030-22496-7_5 István Hegedűs, Gábor Danner, and Márk Jelasity. 2021. Decentralized Learning Works: An Empirical Comparison of Gossip Learning and Federated Learning. Journal of Parallel and Distributed Computing 148, (February 2021), 109–124. https://doi.org/10.1016/j. jpdc.2020.10.006 Chenghao Hu, Jingyan Jiang, and Zhi Wang. 2019. Decentralized Federated Learning: A Segmented Gossip Approach. https://doi.org/10.48550/arXiv.1908.07782 Mohamed Amine Legheraba, Stefan Galkiewicz, Maria Potop-Butucaru, and Sébastien Tixeuil. 2025. HEAL: Resilient and Self-* Hub-Based Learning. In Advanced Informa tion Networking and Applications - Proceedings of the 39th International Conference on Advanced Information Networking and Applications, AINA 2025, Barcelona, Spain, 9-11 April 2025, Volume 2 (Lecture Notes on Data Engineering and Communications Technologies), 2025. Springer, 200–211. Fabien Mathieu, Alexandre Pham, Maria Potop-Butucaru, and Sébastien Tixeuil. 2026. Stream Learning: Partition-Fair Gossip Learning Without Tokens (Code). Re

F. Mathieu, A. Pham, M. Potop-Butucaru, and S. Tixeuil

[14]

[15]

[16]

[17] [18]

trieved from https://gitlab.lip6.fr/npa-dfl/stream-learning-partition-fair-gossip-learningwithout-tokens Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. 2017. Communication-Efficient Learning of Deep Networks from Decentralized Data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, April 2017. PMLR, 1273–1282. Retrieved from https://proceedings.mlr.press/ v54/mcmahan17a.html Róbert Ormándi, István Hegedűs, and Márk Jelasity. 2013. Gossip learning with linear models on fully distributed data. Concurrency and Computation: Practice and Experience 25, 4 (2013), 556–571. Alexandre Pham, Maria Potop-Butucaru, Sébastien Tixeuil, and Serge Fdida. 2024. Data Poisoning Attacks in Gossip Learning. In Advanced Information Networking and Applications - Proceedings of the 38th International Conference on Advanced Information Networking and Applications (AINA-2024), Kitakyushu, Japan, 17-19 April, 2024, Volume 2 (Lecture Notes on Data Engineering and Communications Technologies), 2024. Springer, 213–224. Mirko Polato. 2021. gossipy: A Python module for simulating gossip learning and decen tralized federated learning. Retrieved from https://github.com/makgyver/gossipy Martijn de Vos, Sadegh Farhadkhani, Rachid Guerraoui, Anne-Marie Kermarrec, Rafael Pires, and Rishi Sharma. 2023. Epidemic Learning: Boosting Decentralized Learning with Randomized Communication. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023.

Stream Learning

Background

A.1

Supervised Machine Learning

Machine learning (ML) aims to produce, from data, an algorithm that solves a given task. Within supervised ML, we focus on the classification problem. Given a dataset 𝒟︀ = {𝑋, 𝑌 } = {(𝑥1 , …, 𝑥𝑛𝒟︀ ), (𝑦1 , …, 𝑦𝑛𝒟︀ )}, with 𝑛𝒟︀ = |𝑋| = |𝑌 |, 𝑥𝑖 ∈ ℝ𝑑 and 𝑦𝑖 ∈ ⟦0, 𝐾 − 1⟧, where 𝐾 ≥ 2 is the number of classes, the goal is to map an instance 𝑥 to its label 𝑦 using a hypothesis function ℎ𝑤,𝑏 . Training minimizes the objective function Eq. (2) over the weights 𝑤 and bias 𝑏, using a loss function ℓ that measures the discrepancy between the prediction ℎ𝑤,𝑏 (𝑥) and the true label 𝑦. 𝑛

𝐽 (𝑤, 𝑏) =

1 𝒟︀ ∑ ℓ(ℎ𝑤,𝑏 (𝑥𝑖 ), 𝑦𝑖 ) 𝑛𝒟︀ 𝑖=1

(2)

Logistic Regression is a binary classification algorithm where 𝑦𝑖 ∈ {0, 1} and ℎ𝑤,𝑏 is defined in Eq. (3)4. After fixing a threshold 𝑚, 𝑥 is classified according to whether ℎ𝑤,𝑏 (𝑥) ≥ 𝑚. 1 ℎ𝑤,𝑏 (𝑥𝑖 ) = (3) 1 + 𝑒−𝑤𝑇 𝑥𝑖 +𝑏 The standard choice for ℓ in this setting is the regularized cross-entropy ℓ(𝑥, 𝑦) = −(𝑦 log(ℎ𝑤,𝑏 (𝑥)) + (1 − 𝑦) log(1 − ℎ𝑤,𝑏 (𝑥))) + 𝜆2 ‖𝑤‖22 . The optimization is typically per formed by Stochastic Gradient Descent [6], yielding the update rules Eq. (4) and Eq. (5). 𝑤𝑡+1 = 𝑤𝑡 − 𝜂∇𝑤 ℓ(ℎ𝑤,𝑏 (𝑥𝑖 ), 𝑦𝑖 ) (4) 𝑏𝑡+1 = 𝑏𝑡 − 𝜂(ℎ𝑤,𝑏 (𝑥𝑖 ) − 𝑦𝑖 )

(5)

In Eq. (4) and Eq. (5), 𝜂 and 𝜆 are hyper-parameters (not adjusted by the optimization process), called the learning rate and L2 regularization coefficient respectively. In this paper we use multinomial Logistic Regression, the natural generalization to 𝐾 > 2 classes. Letting ℳ︀𝑑,𝐾 denote the space of 𝑑 × 𝐾 matrices, the weights become 𝑤 ∈ ℳ︀𝑑,𝐾 (one logistic regression per class) and the prediction for an input 𝑥 is 𝑦pred = argmax (softmax (ℎ𝑤,𝑏 (𝑥))).

A.2

Federated Learning

In the standard supervised setting above, a single machine 𝑠 holds both the dataset 𝒟︀ and the trained model 𝑀 , which it serves to clients on request. Centralizing 𝒟︀ on 𝑠 is problematic when the data is sensitive (e.g. medical records). Federated Learning (FL) addresses this by training a shared model across multiple devices without ever pooling their datasets, while aiming for accuracy comparable to the centralized case. The standard FL algorithm, FederatedAveraging, was introduced by McMahan et al. [14]. The server 𝑠 no longer owns a dataset; instead, it builds 𝑀 by aggregating local models 𝑀𝑖 trained by clients 𝑐1 , …, 𝑐𝑛 , each 𝑐𝑖 solving the local version of Eq. (2) on its own dataset 𝐷𝑖 . Clients send their local models to 𝑠, which aggregates them and sends the result back for the next round. This procedure converges to the parameters (𝑤, 𝑏) that minimize the global objective Eq. (6).

𝐿 The name comes from the fact that this function is the standard logistic function 𝑓(𝑥) = 1+ exp(−𝑘(𝑥−𝑥 0 )) with 𝐿 = 𝑘 = 1 and 𝑥0 = 0.

F. Mathieu, A. Pham, M. Potop-Butucaru, and S. Tixeuil 1 𝑛 ∑𝐽 𝑛 𝑖=1 𝑖(𝑤𝑖 ,𝑏𝑖 )

19 (6)

Stream Learning: Partition-Fair Gossip Learning Without Tokens

Analyze & explore related research in Conceptio

Related documents