1
Totoro+: An Adaptive and Scalable Edge Federated Learning System Abstract—Federated Learning (FL) is an emerging distributed machine learning (ML) technique that enables in-situ model training and inference on decentralized edge devices. We propose Totoro+ , a novel scalable FL system that enables massive FL applications to run simultaneously on edge networks. The key insight is to explore a distributed hash table (DHT)-based peer-topeer (P2P) model to re-architect the centralized FL system design into a fully decentralized one. In contrast to previous studies where many FL applications shared one centralized parameter server, Totoro+ assigns a dedicated parameter server to each application. Any edge node can act as any application’s coordinator, aggregator, client selector, worker (participant device), or any combination of the above, thereby radically improving scalability and adaptivity. Totoro+ introduces three innovations to realize its design: a locality-aware P2P multi-ring structure, a publish/subscribe-based forest abstraction, and a game-theoretic path planning model with a guarantee of an ϵ-approximate Nash equilibrium. Real-world experiments on 500 Amazon EC2 servers show that Totoro+ scales gracefully with the number of FL applications and N edge nodes speeds up the total training time by 1.2×−14.0×, achieves O(log N ) hops for model dissemination and gradient aggregation with millions of nodes, and efficiently adapts to the practical edge networks and churns. Index Terms—Distributed and parallel systems for machine learning, federated learning, game theory, and edge computing.
I. I NTRODUCTION ITH the rise of 5G and the growth of connected devices, federated learning (FL) enables local data processing and machine learning at the network edge. This approach reduces data transmission and enhances privacy by eliminating the need for centralized servers. FL has been applied in various domains, including human activity prediction [2], [3], sentiment analysis [4], language processing [5], [6], and enterprise systems [7]. The problem. We consider a typical edge computing architecture where millions of edge devices (e.g., smart wearables,
W
This work was supported in part by the National Science Foundation under Grants NSF-OAC-2313738, NSF-CAREER-2313737, and NSF-CNS2322919, and in part by the National Science and Technology Council under Grants 113-2221-E-194-040-MY3, and 114-2628-E-194-002-MY3. A preliminary version of this paper appeared at the Proceedings of the Nineteenth European Conference on Computer Systems (EuroSys’24) [1]. (Corresponding author: Liting Hu.) Cheng-Wei Ching and Liting Hu are with the Department of Computer Science and Engineering, University of California, Santa Cruz, Santa Cruz, CA 95064 USA (e-mail: [email protected]; [email protected]). Xin Chen is with the Department of Computer Science and Engineering, Georgia Institute of Technology, Atlanta, GA 30332 USA (e-mail: [email protected]). Taehwan Kim is with the Department of Computer Science, Virginia Tech, Blacksburg, VA, 24061 (e-mail: [email protected]). Jian-Jhih Kuo is with the Department of Computer Science and Information Engineering, National Chung Cheng University, Minhsiung, Taiwan (e-mail: [email protected]). Dilma Da Silva is with Texas A&M University, College Station, TX 77843 USA (e-mail: [email protected]).
App#1: Driver behavior prediction App#2: Traffic pattern analysis App#3: Vehicle anomaly detection ...
arXiv:2605.26323v1 [cs.DC] 25 May 2026
Cheng-Wei Ching , Xin Chen , Taehwan Kim , Jian-Jhih Kuo , Dilma Da Silva , and Liting Hu
V2V
Upload local model
V2I
V2I
Parameter server
V2X
Download global model
Edge Cloud
Fig. 1: An edge federated learning use case based on autonomous vehicles. autonomous vehicle sensors) connect to the cloud through an edge layer. This layer comprises hundreds of thousands of server-grade machines, gateways, and routers—termed “edge nodes”, managed by various providers across geographically distributed sites. Raw data is collected and stored on these edge nodes, enabling machine learning models to be trained locally without transferring raw data to a central server. Federated learning (FL) tools and frameworks—such as TensorFlow Federated [8], LEAF [9], FLOAT [10], REFL [11], and PySyft [12]—have gained traction. However, building an efficient FL system on practical edge networks remains challenging due to dynamic edge environments and the high scalability demands of emerging FL applications. Figure 1 illustrates a use-case scenario that highlights these challenges. In future intelligent transportation systems such as the efforts currently funded by the US Department of Transportation [13], autonomous vehicles are interconnected and equipped with wide-area network access They continuously collect sensor and behavioral data such as speed, engine performance, driving patterns, and environmental conditions. On the back end, numerous FL applications will run concurrently on these vehicles or edge nodes, performing insitu training using the collected data. Examples of such FL applications include driver behavior prediction, which trains Long-Short Term Memory (LSTM) networks [14] to anticipate lane change actions [15]; traffic pattern analysis, which learns traffic patterns to redirect optimal routes [16]; and anomaly detection, which employs federated learning to identify and respond to vehicle malfunctions or hazardous road conditions in real time [17]. Our solution: Totoro+ . We present Totoro+ , an adaptive and scalable federated learning (FL) system designed to support large-scale concurrently running FL applications on edge networks and adapt to edge dynamics. Rather than modifying existing FL systems, we adopt a fully decentralized architecture. Unlike prior approaches where multiple FL applications
2
rely on shared centralized parameter servers, Totoro+ assigns each application its own parameter server, preventing overload on any single edge node. Moreover, any edge node can dynamically serve as an application’s coordinator, aggregator, client selector, worker, or any combination of these roles, significantly enhancing scalability and adaptivity. The key idea is to leverage a distributed hash table (DHT)based peer-to-peer (P2P) architecture to redesign FL systems. P2P models, widely used in file sharing (e.g., BitTorrent [18], Storj [19], Freenet [20]), peer-assisted CDNs [21], and blockchains [22], treat all nodes equally, without a central server, as they collaborate to perform tasks or deliver services. For instance, in BitTorrent [18], users both download and upload file pieces to/from peers. Inspired by this model, we enable all edge nodes to jointly handle FL training and testing for a large number of applications in parallel. Totoro+ introduces three innovations to realize its fully decentralized design: a locality-aware P2P multi-ring structure, a publish/subscribe-based forest abstraction, and a gametheoretic path planning model. First, edge nodes self-organize into a scalable DHT-based P2P overlay. The locality-aware P2P multi-ring structure enforces administrative boundaries between edge sites, enabling efficient local FL execution and preserving site-specific control flows. Second, Totoro+ builds a publish/subscribe-based forest abstraction on top of the locality-aware P2P multi-ring structure for model broadcasting and gradient aggregation. This decouples the centralized FL architecture into a “fully” decentralized architecture, where each FL application operates on an independent dataflow tree, significantly enhancing system scalability. Besides individual dataflow trees for FL applications, we introduce an advertise-discover (AD) tree that enables edge nodes to publish and locate FL applications within the overlay. Third, to address edge dynamics (e.g., link failures, stragglers, and bandwidth constraints over edge networks) Totoro+ employs a game-theoretic path planning model that dynamically replans data transfer paths, ensuring robust and adaptive model broadcast and gradient aggregation. Summary of results. We implement Totoro+ using the open-source Pastry DHT [23] and PyTorch [24] frameworks, 1 and evaluate it on various FL tasks with real-world datasets across 500 Amazon EC2 servers. Compared to state-of-theart FL systems [25], [26], Totoro+ achieves superior scalability and load balancing, efficiently distributing masters across large-scale edge networks without overloading individual nodes. It accelerates total training time by 1.2× to 14.0×, supports O(log N ) hops for model dissemination and gradient aggregation at million-node scales, and robustly handles network churn and unreliable edge conditions. Contributions. This paper makes the following contributions : Problem: We analyze the software architecture of current FL systems and identify key challenges in applying FL to practical edge networks. + • Key idea: Totoro explores the DHT-based P2P model to propose a novel, fully decentralized “many masters/many •
1 https://github.com/UCSC-ELVES-Lab/Totoro-EuroSys-2024
Features
Totoro [1]
Totoro+ (this work)
Application advertisement and discovery Path planning model
Join-by-AppId
Advertise-discover tree
Algorithmic complexity Theoretical guarantee
Bandit model without traffic congestion O(log N · IKL ) Heuristic
Failure recovery
Worker
Game-theoretic model with traffic congestion O(log N · M atmul) ϵ-approximate Nash equilibrium Worker and master
TABLE I: Comparison between Totoro and Totoro+ , where IKL is the iteration complexity of solving the Kullback–Leibler divergence-based convex feasibility, and M atmul is matrix multiplication. workers” architecture that significantly enhances scalability and adaptability. + • Totoro design & implementation: Totoro+ incorporates three key innovations: a locality-aware P2P multi-ring structure, a publish/subscribe-based forest abstraction, and a game-theoretic path planning model with theoretical guarantees of an ϵ-approximate Nash equilibrium. + • Results: Our evaluation demonstrates Totoro ’s substantial improvements in scalability and adaptability over state-ofthe-art FL systems. A preliminary conference paper version [1] has been published in Proceedings of the Nineteenth European Conference on Computer Systems (EuroSys’24). The summary of changes is presented in Table I. In this journal version, we provide the following three significant improvements: First, we introduce the advertise-discover (AD) tree to the publish/subscribe-based forest abstraction. The AD tree enables edge nodes to advertise and discover FL applications running over the DHT-based P2P overlay for FL application searching and crowdsourcing [27], [28] (see Appendix A for a detailed comparison with the conference version). Secondly, we replace the bandit-based path planning model with the game-theoretic path planning model, which formalizes the path planning problem as a congestion game with bandit feedback and introduces a game-theoretic distributed hop-by-hop algorithm with the guarantee of an ϵ-approximate Nash equilibrium (see Appendix B for a detailed comparison with the conference version). Thirdly, we provide respective failure recovery mechanisms for master and worker node failures. When a worker node fails, its child node sends a JOIN message using AppId as the key to find a new parent node to recover the dataflow tree. The master node in each communication round replicates the training state across k nodes in its neighborhood set. When the master node fails, its immediate node sends a JOIN message using AppId as the key to find an alternative master node. The new master node retrieves a state replica to proceed with the training process. Finally, we demonstrate that the game-theoretic path planning model is a better solution for adapting to edge dynamics with experiments on packet latency, and Nash regret. Also, we provide more extensive experiment results to demonstrate further Totoro+ ’s scalability to massive FL applications, fault tolerance to simultaneous node failures, and adaptivity to edge dynamics.
Parameter server(s)
User queries FL model N
FL model 2
Federated learning applications
FL model 1
II. BACKGROUND We start with a quick primer on the software architecture used in state-of-the-art federated learning (FL) frameworks. State-of-the-art FL frameworks (e.g., Meta’s PAPAYA [29], LinkedIn’s FLINT [30], Google’s federated learning framework [31], IBM Federated Learning framework [7], and Apple’s federated task processing system [32]) commonly adopt a centralized or hierarchical “single master/many workers” architecture. In this architecture, the master is typically deployed on a parameter server, acting as a coordinating service provider without data. The workers, on the other hand, connect to numerous edge devices and serve as both the data owners and beneficiaries of federated learning. Figure 2 illustrates the data pipeline between these components in a typical FL framework. The high-level design involves two parts: the parameter server that runs the “master”, and the end-user devices that run the “workers”. The parameter server comprises three main components: Coordinator, Selector, and Aggregator. While the number of Selectors and Aggregators can scale elastically based on the workload demand, there is only one Coordinator. We summarize the functions of these components as follows. Coordinator. The Coordinator performs three main functions: • Task Assignment. Whenever a new FL application is submitted to the system, the Coordinator assigns the application to a single Aggregator based on the workload among Aggregators and the estimated workload of the application such as application concurrency and model size. • Client Assignment. For each available client, the Coordinator constructs a list of eligible applications. The Coordinator assigns each client to an application. • Task Migration. The Coordinator moves applications between Aggregators when it detects failed or overloaded Aggregators. Aggregator. The Aggregators are persistent and stateful to avoid a substantial cold start overhead for a new application. Each Aggregator is responsible for one single FL application and carries out three main responsibilities. • Gradient Aggregation. Once a client completes training, it uploads the trained serialized gradient update to the server. This update is then pushed into an in-memory queue on the Aggregator, which aggregates client gradient updates to produce new versions of the server model of an application. • Client Guidance. The Aggregator guides clients into running the client protocol, such as downloading, uploading, and training configurations, by responding clients requests from the Selector. • Client Tracking. The Aggregator is responsible for tracking (i) if clients are satisfied with their assigned applications, and (ii) if clients are still eligible for their assigned applications. The tracking information will be used by the Coordinator to run client assignments. Selector. The Selector is the only component that directly communicates with clients and plays two roles: • Task Advertisement. The clients check in with the Selector and report their eligibility for available applications. The Selector summarizes client availability for the Coordinator.
FL model 3
3
…… Coordinator coordinates
coordinates
creates
Master aggregator creates
creates
Aggregator … Aggregator Selector … Selector Model broadcast & Gradient aggregation
Edge physical networks
Fig. 2: The data pipeline in a typical FL framework. •
Request Forwarding. When a client is assigned an eligible application. The Selector forwards the client to the Aggregator responsible for that application. The Selector also routes clients’ requests to the corresponding Aggregator, such as model broadcasting, and reporting client status and gradient updates. III. C HALLENGES
We highlight the challenges that we face when applying FL to real-world edge networks in this section. Challenge #1: Scaling gracefully with the number of diverse FL applications and edge nodes. As emerging edge applications and edge devices grow in quantity and complexity, the number of FL applications submitted to the edge will likely become huge. As shown in Figure 1, different FL applications may require training of various FL models for different driver profiles (e.g., speeds, distances, passengers), vehicle conditions, and environmental factors (e.g., intersections, pedestrians, moving objects) simultaneously based on the same raw data. This results in the generation of a vast number of FL tasks. Therefore, key considerations in addressing this challenge include: Distributed task management. As shown in Figure 2, existing production FL systems typically rely on a single instance of Coordinator to direct Aggregators and Selectors across all FL training and testing tasks. While this hierarchical design scales well in datacenter environments, it struggles in edge systems with millions of nodes and many concurrent FL applications. The challenge is amplified by the presence of multiple edge providers [33], each managing its own set of edge nodes, resulting in no global view of workloads and resources. Without this global view, existing FL systems cannot balance FL tasks effectively across the edge, hindering
4
Totoro+ API (Section IV-E)
Layer-3
their ability to scale with new nodes and applications and increasing overall training time. Besides longer training time, existing FL systems may fail to advertise the existing/new FL tasks to new/existing clients to further strengthen model accuracy without a global view of running applications. Application-specific customization. As FL applications diversify with emerging use cases, flexible designs for participant selection [34]–[36], compression [37], [38], and communication protocols—synchronous [39], semi-synchronous [40], or asynchronous [41]—are increasingly needed. However, existing FL systems typically share a single parameter server across applications and enforce fixed FL policies, limiting their ability to support diverse requirements. Achieving applicationspecific customization often requires using multiple FL frameworks, which compromises efficiency, maintainability, and simplicity.
Subscribers (Section IV-C) aggregation
Publisher
Failure recovery (Section IV-D)
Layer-2
Replicate
Game-theoretic path planning model (Section V) High Bandwidth Nodes
JOIN
broadcast AD tree & Dataflow trees (Section IV-C) Root
App 1
App 2
App 3
Layer-1
Master
Multi-ring structure (Section IV-B)
Multi-ring
Node 103220 edge node
Routing table
m*O(logN) hops 031120
031120 0 100221
1 110003 101203 103112 103210
201303 120132 102303 2 2
312201 132012 3 103302
103302
103330
0
DHT-based overlay
120132 312201
Leaf set 103123
103210
Neighborhood set 031120
312201
120132
101203
Edge node 103220 in a 12-bit identifier space and a base of 4 (l=12, b=2)
Edge physical networks
Challenge #2: Adapt to practical edge network conditions such as varying bandwidths, unreliable links, high churn, and workload surges. The second challenge arises from the first one. To scale with massive FL applications, cloud administrators usually partition all nodes into many sets and assign a parameter server per each set of nodes in a static manner (e.g., one parameter server per rack) [10], [11], [26]. While this assignment approach may work well in datacenters, it lacks the agility to adapt quickly to edge platforms that have millions of resource-constrained nodes. Edge environments are characterized by the following unique difficulties: (1) edge network link delays are unpredictable and vary stochastically due to unreliable links and random access protocols (e.g., in wireless networks [40], [42]), client mobility (e.g., in mobile ad-hoc networks [27], [43]), and randomness of demand (e.g., workload surges [44], [45]) in arbitrary (and dynamic) geographical edge locations, and (2) edge nodes fail or lag unexpectedly (e.g., due to signal attenuation, interference, and wireless channel contention [40], [42]). However, unlike datacenter servers, edge nodes have limited computing resources (few-core processors, little memory, and little permanent storage [44]) and no backpressure [46]. As such, there is little room to adapt to the edge dynamics or handle stragglers by over-provisioning resources or replicating links like previous studies. Moreover, edge nodes may belong to different owners who do not share operation or application information and have to compete for communication resources over edge networks [47], [48]. Therefore, efforts should be made to replan the data transfer paths dynamically and autonomously to adapt to the edge dynamics and constrained network bandwidth. IV. T OTORO+ DESIGN +
Totoro proposes a novel scalable FL system for practical edge networks. To achieve this, Totoro+ incorporates several key techniques and components, which we describe in detail. A. Overview Totoro+ ’s system goals are:
Fig. 3: The Totoro+ system overview. Scalability. Totoro+ can scale to process a vast number of FL applications’ tasks simultaneously on millions of edge nodes without introducing any centralized bottleneck. + • Adaptivity. Totoro can quickly adapt to the practical edge networks characterized by varying bandwidths, unreliable links, high churn (nodes join and leave), and workload surges in arbitrary geographical edge locations. • Good FL performance. When handling a vast number of FL applications, Totoro+ can speed up the training process for each of them. As shown in Figure 3, Totoro+ has three layers: a localityaware P2P multi-ring structure, a publish/subscribe-based forest abstraction, and a high-level API. Layer 1: locality-aware P2P multi-ring structure. All distributed edge nodes are self-organized into a DHT-based P2P overlay. Each node has a unique 128-bit NodeId in a very large circular NodeId space. In an edge network with N nodes, the DHT-based P2P overlay guarantees that, no matter where the source node is, any FL data (e.g., model or gradient) can be routed to any destination node within O(log N ) hops. Compared to existing DHTs studies [49]–[51], our innovations are: (1) Totoro+ divides the original single P2P ring structure into many smaller, more manageable locality-aware P2P multiring structures that enable locality-aware FL processing; and (2) Totoro+ designs a new boundary-aware two-level routing table that ensures administrative isolation for privacy concerns. Layer 2: publish/subscribe-based forest abstraction. Built upon Layer 1’s locality-ware P2P multi-ring structure, Totoro+ introduces a new publish/subscribe-based forest abstraction that manages a vast number of FL applications in a scalable manner. Each FL application is assigned a dynamically structured dataflow tree that operates with maximum independence and is responsible for disseminating the model from the master to the workers and aggregating the gradients from the workers to the master. In addition to dataflow trees, the masters of all dataflow trees construct an advertise-discover (AD) tree to advertise and discover FL applications running over the overlay. These trees together form a “forest”. Our •
5
innovations are (1) a fully decentralized architecture—unlike other federated learning systems, our system does not have a static assignment of parameter servers. Instead, any edge node can be automatically promoted as a parameter server (master) when workload surges, which significantly improves load balancing and scalability. (2) Advertising and discovering FL applications—new edge nodes that just joined the overlay can easily locate and subscribe the FL applications running over the overlay. (3) DHT-based routing—the time complexity of model/AppId broadcast, and gradient/AppId aggregation is limited to O(log N ) hops. Layer 3: high-level API. We provide a high-level API to abstract away the complexities of P2P overlay construction, dynamic-structured dataflow tree construction, model/AppId dissemination, and gradient/AppId aggregation. Totoro+ supports application-specific customization, allowing application owners to set their own FL policies. B. Layer 1: locality-aware P2P multi-ring structure Many times, geographic diversity or location matters for training FL applications. For example, a road traffic detection application may require nodes with varying weather condition information in different geographic locations [15]–[17]. Training a model on a medical disease prevalent in a certain region may require information from a specific location [52], [53]. Therefore, we organize distributed edge nodes into a locality-aware P2P multi-ring structure to enable localityaware FL processing. First, we organize distributed edge nodes into a DHT-based P2P ring overlay, which is similar to the BitTorrent nodes that use the Kademila DHT [54] for “trackerless” torrents. Each edge node is assigned a unique 128-bit NodeId in a very large circular NodeId space (e.g., 0 ∼ 2128 ). NodeIds are used to identify edge nodes and route FL data (e.g., model or gradient) over large-scale edge networks. To do that, each node needs to maintain three data structures: a routing table, a leaf set, and a neighborhood set. • Routing table is used for routing FL data. It consists of node characteristics organized in rows by the length of the common prefix. The routing works based on prefix-based matching. Every node knows m other nodes in the ring and the distance of the nodes it knows increases exponentially. The routing jumps closer and closer to the destination, like a greedy algorithm, within ⌈log2b N −1⌉ hops, where 2b −1 is the routing table’s entry size. • Leaf set is used for rebuilding the routing tables upon failures. • Neighborhood set contains a fixed number of nodes that are “physically” closest to that node for maintaining the locality properties. Second, we divide the original large P2P ring into m smaller, more manageable, locality-aware rings, which we call “multi-rings”, using Ratnasamy and Shenker’s distributed binning algorithm [55] (m is a configurable parameter). Each ring is an “edge zone” and is characterized by a maximum desired network round-trip time (RTT), called diameter. Third, we design a new routing table to enable administrative isolation. The challenge is, how to achieve path
convergence to enable administrative isolation, i.e., data paths from different nodes in an edge site should converge at a node in that edge site? Existing DHTs [49]–[51], [54] do not guarantee path convergence as those systems try to optimize the search path to reduce response latency. To route a packet to an arbitrary destination key, the packet will be routed to the destination node in another site as long as it has a longer NodeId prefix matching the key. To address this challenge, we make the following changes to existing routing tables: (1) each NodeId now has (m + n)-bit, where the m-bit prefix presents the zone Id and the n-bit suffix represents the NodeId within a zone. Let P denote the prefix of NodeId, i.e., P1 ...Pn . Let S denote the suffix of NodeId, i.e., S1 ...Sn . Then the NodeId equals D = P ∗2n +S; correspondingly (2) each node’s routing table will have two levels: the level 1 routing table and the level 2 routing table. The ith entry in the level 1 routing table with m entries at peer x equals to (Px + 2i−1 )mod 2m ∗ 2n . The ith entry in the level 2 routing table with n entries at peer y equals to (Sy + 2i−1 )mod 2n . To achieve administration isolation, the administrator of an edge site can leverage the level 1 routing table to control the data flow among different edge zones. For example, when an FL application should be running only within an edge site, any packet generated by that FL application should only travel within this edge site. Administrators can check the destination of packets. If the packet’s destination shares a different prefix with the administrator’s zone Id, the administrator can block the packet before routing it outside the edge zone. C. Layer 2: publish/subscribe-based forest abstraction Built upon Layer 1, Totoro+ introduces a new publish/subscribe-based “forest” abstraction for managing a vast number of FL applications in a scalable manner. Specifically, our goal is to achieve a balanced distribution of masters for hundreds of thousands of FL applications, ensuring that they are not concentrated on a few overloaded nodes. The key innovation is leveraging DHTs to decompose the FL system architecture from 1:n to m:n, where each FL application can be assigned a dynamic-structured dataflow tree that operates with maximum independence, thereby radically improving load balance and scalability. A DHT is a hash table that partitions the key space and distributes the parts across a set of nodes, providing a lookup service similar to a hash table. The trick with DHTs is that the node that gets to store a particular key is found by hashing that key, so in effect, the hash-table buckets are now independent nodes in a network. We utilize the fully decentralized nature of DHT to process FL applications’ tasks at an extreme scale: unlike other FL systems, Totoro+ does not have a static assignment of a parameter server. Instead, the parameter server is broken down into many components, such as the coordinator, client selector, and aggregator. Any edge node can act as any FL application’s coordinator, aggregator, client selector, worker (participating edge device), or any combination of the above, thereby radically improving load balance and scalability. Figure 4 lays out the construction of the publish/subscribebased “forest”. It has the following steps.
6
Hash(“App1”)=77 N77 N78
Master N2
N69
Hash(“App2”)=2
N72
N55 N50
App1
App2
App3
Advertise-discover tree
Master
Master
Master
Root
N78
N2
N22
N11
Workers
N49
N15
N47
N17
N27
N72
N69
N21
AppIds
N29 N17
N10
N11 N15
N33
N38
N35
N33
N29
N21 N22
N22
Hash(“AD app”)=21 N47
N49
N50
N55
N18
N20
N38
N42
App3's tree Gradient aggregation
N35 AppIds
Hash(“App3”)=22
App1's tree App2's tree
N20 N27
Root node of advertise-discover tree
Model dissemination
Gradient aggregation
N18
Root N42
Master node Worker node
N10
N78
N2
Model dissemination AppIds dissemination & aggregation
Fig. 4: The workflow of Totoro+ ’s publish/subscribe-based “forest” abstraction with three dataflow trees for three FL applications and an advertise-discover tree for application advertise and discovery. Built on top of Layer 1, all edge nodes are structured into a DHT-based P2P overlay. Here we use one ring as an example. The DHT-based P2P overlay guarantees that: given a message and a key, no matter where the source node is, the message can be reliably routed to the node whose NodeId is numerically closest to that key, within ⌈log2b N − 1⌉ hops, where 2b − 1 is the routing table’s entry size. The first step is constructing application-based logical “trees” of nodes and ensuring that these trees are well balanced over the large-scale edge topologies (Figure 4 left). a. When any new FL application is launched, we calculate the application’s AppId, which equals the cryptographic hash of the application’s textual name, the creator’s public key, and a random salt, AppId=hash(“FL application”). The hash is computed using the collision resistant SHA-1 hash function, ensuring a uniform distribution of AppIds. b. Then, the edge node processing the application’s data routes a JOIN message using AppId as the key. Since all nodes belonging to the same application use the same key, their JOIN messages eventually arrive at a rendezvous node, with NodeId numerically close to AppId. The rendezvous node is set as the root of this application’s tree. c. The unions of all JOIN messages’ paths are registered to construct the tree, in which the internal node, as the forwarder, maintains a children table for the group containing an entry (IP address and AppId) for each child. All of the trees together form a “forest” abstraction. d. For each application’s tree, we designate the root node as the master, the internal nodes as the coordinator, aggregator, and client selector components, and the leaf nodes as the workers (participating edge devices). Rationale: (1) Since different applications have different AppIds, the paths and the rendezvous nodes of their spanning trees will also differ, resulting in an even distribution of trees across all edge nodes. (2) Because all nodes are equal, each node can serve as a leaf, internal, or root node for different applications, thus removing the scalability bottleneck without overburdening any single node. The second step is implementing a topic-based publish/ subscribe messaging protocol within the dataflow tree. Each FL application has a “topic”. The master is the “publisher”, and the workers are the “subscribers”. a. Model broadcast. The master disseminates the FL model to the workers along the tree. Then each worker inde-
pendently trains a local model and computes the model updates (e.g., gradients and weights) on the local data. b. Gradient aggregation. Once the workers have completed the computation, the master aggregates model updates from the workers, in which each level of the tree progressively aggregates the updates from tree leaves to the root. To meet the diverse needs of different applications, owners can specify different aggregation functions in their trees. For instance, FedAvg [39] works well in most situations, while FedProx [56] demonstrates superior performance in highly heterogeneous settings for more stable and accurate convergence. Rationale: (1) Due to the loosely coupled interaction between the publisher and subscribers, Totoro+ can simultaneously support a large number of dataflow trees with a wide range of tree sizes and a high rate of membership turnover. (2) The use of DHTs enables the efficient construction of aggregation trees and multicast services, as their converging properties guarantee model broadcast or gradient aggregation to be fulfilled within only O(log N ) hops, which places an upper bound on worstcase latency for data transfers. The third step is constructing an advertise-discover (AD) tree that enables edge nodes to advertise and discover FL applications running over the overlay (Figure 4 right). a. Similar to the first step, each master of various applications’ trees routes a JOIN message using AppId=hash(“AD application”) as the key. Since all masters use the same key, their JOIN messages eventually arrive at a rendezvous node whose NodeId is numerically closest to AppId. The rendezvous node becomes the root of the AD tree. b. The unions of all JOIN messages’ paths are registered to construct the AD tree. In addition to children tables for FL applications, the internal node in the tree works as a forwarder that maintains a children table consisting of the IP addresses of each child and AppIds of FL applications each child is hosting. c. The root of the AD tree is the “publisher”, and other nodes are the “subscribers”. The publisher disseminates AppIds of FL applications to each node along the tree, whereas the subscribers in different levels of the tree progressively aggregate AppIds of FL applications to the root. d. Whenever a new edge node that joins the DHT-based P2P overlay wants to discover FL applications running over
7
the overlay or an existing edge node intends to switch to a different FL application running on the overlay, it can route a JOIN message using the same AppId to join the AD tree as a subscriber and receive the AppIds of interest. After that, it can route a LEAVE message using the same AppId to leave the AD tree. Rationale: (1) Since edge nodes may join and leave the overlay frequently and suddenly, joining nodes can subscribe to the AD tree first and receive the information of current FL applications instead of sending broadcast messages to all other nodes, making Totoro+ adaptive to practical edge networks. (2) Because edge nodes can leave the AD tree immediately after they receive the necessary information, the tree may have M nodes plus some intermediate nodes N ′ most of the time and N ′ << N , where M denotes the number of current FL applications and N denotes the number of nodes in the overlay. Therefore, with the use of DHTs, the AppId broadcast and aggregation can also be fulfilled within O(log(M +N ′ )) hops. A comparison of Totoro and Totoro+ in terms of FL application discovery and advertisement is presented in Appendix A.
Join(IP, port, site) Edge node joins the DHT-based P2P overlay network. CreateTree(app id) Application owner creates a dynamic-structured dataflow tree and configures the parameters (e.g., fanout). Subscribe(app id) Edge node sends a JOIN message to subscribe to a dynamicallystructured dataflow tree with the topic equal to app id. Application owner can specify her client selection function in the API. Unsubscribe(app id) Edge node sends a LEAVE message to unsubscribe to a dynamically-structured dataflow tree with the topic equal to app id. Broadcast(app id, object) Application’s master disseminates the model or AppIds to workers along its dynamically-structured dataflow tree. Application owner can specify her compression function in the API. onBroadcast(app id, object) Callback. Invoked when the worker receives any model, updates, or AppIds from the application’s master. Aggregate(app id, object) Application’s master aggregates updates or AppIds from the workers to the root. Application owner can specify her aggregation function in the API. onAggregate(app id, object) Callback. Invoked when any internal node receives updates or AppIds from a child node. onTimer(app id) Callback. Invoked periodically. Application’s master uses it to get the information about the progress of training (e.g., round num, accuracy, straggler id) and inference.
TABLE II: Totoro+ API. E. Layer 3: high-level API D. Failure recovery In the case of node failures, we use a parallel recovery approach to repairing the dynamic-structured dataflow trees. A dataflow tree has a master and several workers, and the parallel recovery approach leverages two respective ways to deal with the failure of a worker and the failure of a worker. Worker node fails. Periodically, each internal node in the tree sends a keep-alive message to its child nodes. A child node suspects its parent fails when it cannot receive keepalive messages from its parent node. In such a scenario, the child node routes a JOIN message using AppId as the key. The overlay network will route the message to a new parent, create an alternative route, and repair the dataflow tree. Master node fails. In each training round, we replicate the state associated with each application’s master across the k nodes in its neighborhood set (k = 2, by default), which consists of a fixed number of nodes that are “physically” closest to the master node. If the master node fails, its immediate child node will detect it, route a JOIN message using AppId as the key, and identify a new master node to take over the role of the failed master. According to Layer 2: publish/subscribe-based forest abstraction, the new master node’s NodeId will be numerically closest to the AppId, and it will first contact the nodes that have state replicas to recover the state and inform workers to continue the training tasks like aggregation, global model update, and broadcast. The tree repair process scales well: failure detection is done by sending messages to child nodes only. Failure recovery is also local. Only a small number of nodes (O(log2b N )) is involved, in which 2b is the fanout of the tree. In addition, the replicas of states are typically transmitted over local networks with plentiful bandwidth; hence, the communication overhead is negligible.
We abstract key components of Totoro+ to provide an easy-to-use API (see Table II). Totoro+ supports applicationspecific customization, allowing application owners to set their own FL policies. The Pastry DHT and Scribe multicast infrastructure are written in Java, with end-user functionality encapsulated in a Python API. This is done so that users do not have to deal with two libraries in separate languages. Thus Totoro+ can be easily integrated with popular FL frameworks such as PyTorch [24], PySyft [12], and TensorFlow Federated [8]. Application-level customization. Totoro+ ’s APIs support application-level customization. For example, to prevent potential leakage of model weights to other nodes, application owners can specify various privacy techniques in Aggregate(app_id, object), such as differential privacy [57], secure aggregation [29], and homomorphic encryption [58]. Nodes that subscribe to an FL application adhere to the privacy technique specified by that application during the FL process. Take differential privacy as an example, if an application owner launches an FL application and specifies the use of differential privacy with Gaussian noise to secure weights, the edge nodes, as the master, coordinator, aggregator, and client selector, will operate following the privacy technique. Similarly, the leaf nodes, serving as workers, will apply Gaussian noise to local training. Moreover, to realize client selection techniques, application owners can rule out edge nodes that do not meet specific requirements (e.g., data distributions, battery, network conditions, etc.) when receiving JOIN messages from edge nodes. Multi-rings. Application owners can specify whether their applications span multiple zones. For example, a road traffic detection application may require nodes with different weather condition information in different geographical locations. If an application needs to ingest data sources across multiple zones,
8
it will traverse multiple zones (at most m) to build the dataflow tree, resulting in m × O(log N ) routing hops. V. G AME - THEORETIC PATH P LANNING M ODEL Totoro+ introduces a new game-theoretic path planning model that can replan the data transfer paths in dynamically structured dataflow trees to adapt to unreliable edge networks. In most real-world edge networks, link delays are unpredictable and vary stochastically [59]. When a link becomes slow, it can disrupt communication with its child and parent nodes, thereby affecting the entire path from the leaves to the root passing through this link in dataflow trees. The challenge is that, in many cases, we don’t know the quality of the network links in advance, such as the probability of successfully transmitting packets in wireless sensor networks [59]. This information is often obtained by actually sending packets and observing the outcomes. Furthermore, the network links have limited capacities [59]. When a link carries too much traffic, its overall data rate dramatically decreases. Therefore, we face two dilemmas when planning the paths for model dissemination and gradient aggregation. One is whether to explore new or unknown links or exploit well-known ones. If we only rely on the known links, we may miss out on finding a better one with a higher success rate or data rate. However, exploring too many new links may result in more packet losses and higher communication delays. The other is whether to prioritize link quality or link capacity. Maximizing link quality avoids packet loss and errors but may overload these paths, leading to congestion and increased latencies. However, prioritizing link capacity may increase the risk of transmission failures instead. This is where Multi-Armed Bandit (MAB) algorithms [60], [61] and game theory [48], [62], [63] come into play. Imagine someone at a bustling amusement park, surrounded by various facilities like roller coasters, merry-go-rounds, and Ferris wheels. Each facility differs in its entertainment type and its queue length. Initially, she explores different facilities randomly, collecting data on two key aspects: the joy each ride brings and the length of the waiting time. Her goal is to maximize her day by finding the facilities that offer the best balance of fun and short waiting times. However, her decision-making process influences the decisions of others. The presence of other tourists, who also choose facilities based on their own experiences and preferences, affects the queues at each location. The collective decisions of all tourists shape these queues, each acting on their assessments of enjoyment and waiting times. As time passes, some facilities may become busier, while others may see reduced waiting times. She must constantly adapt to these changing conditions, balancing her preferences for fun with the evolving waiting times. Therefore, the path-planning problem can be formulated as a general-sum congestion game with bandit feedback [64], [65]: we follow a policy to explore different paths to learn about their rewards (e.g., link quality and link capacity) or exploit the paths that offer the highest rewards and update the policy based on the rewards. And the rewards are influenced by collective decisions on paths. We gradually find out the optimal policy to select paths over edge networks.
The formal definitions and theoretical concepts underlying this formulation are provided in Appendix C. Specifically, we review general-sum matrix games, policy representations, Nash equilibrium and Nash regret, as well as potential and congestion games, together with different feedback models. In the following, we build upon these preliminaries to formulate a routing problem, define the corresponding optimization objective, and develop a game-theoretic algorithm with theoretical performance guarantees. In addition, we present a comparison of the mathematical models underlying Totoro and Totoro+ in Appendix B. A. Problem formulation A dataflow tree in Totoro+ consists of at most N nodes, and there are at most P paths to reach the root of the tree. Since each path p ∈ [P ] has different success rate, and capacity, we let Rp (·|k, θp ) ∈ [0, 1] denote the reward distribution for path p with mean rp (k, θp ) given that k nodes select path p with mean success rate being θp . The higher the mean success rates, the higher the rewards. In contrast, the more nodes select the same path, the less the rewards they receive as the success rate and data rate drop. Suppose the joint paths chosen by all nodes are denoted by p = [p1 , p2 , · · · , pN ], where pn denotes the path selected by node n, then we let np (p) denote the number of nodes selecting path p given the joint action p. A node n selects path p and gets the reward rn (p) drawn from the reward distribution Rp (·|np (p), θp ) with mean rp (np (p), θp ). Optimization objective. We aim to efficiently route T packets (such as gradients in many rounds) from a worker node to a master node, minimizing the overall time taken. In other words, our goal is to maximize total rewards. Also, since collective actions taken by all nodes influence the rewards, we resort to see how those actions affect others’ decisions. First, we define policy πn followed by node n to select paths, where πn is from the probability simplex over node n’s action space Pn , denoted by ∆(Pn ), where Pn ⊆ [P ] is the set of paths available for node n’s selection. Similarly, we can define a general policy π = [π1 , π2 , · · · , πN ] as a tuple in the joint space ∆(P1 ) × · · · × ∆(PN ). Hence, we can have i.i.d p = (p1 , p2 , · · · , pN ) ∼ π and pn ∼ πn . Then, since the policy influences the rewards the nodes receive, we use the rewards to represent the value of a policy. We define the value of policy π for node n as Vnπ = Ep∼π [rn (p)], where rn (p) = rpn (npn (p), θpn ). Let π−n be the marginal joint policy of nodes 1, · · · , n − 1, n + 1, · · · , N . We refer to [48], [63] to define the Nash Regret after T packets as Nash-Regret(T ) =
T X t=1
t π + ,π−n
max (Vn n
n∈[N ]
t
− Vnπ ),
(1)
t
where π t is the policy for packet t, Vnπ is the value of policy µ,π t π t for node n, πn+ = arg maxµ∈∆(Pn ) Vn −n represents the π + ,π t
best response of node n under policy π, and Vn n −n is the t value of the policy (πn+ , π−n ). The Nash Regret indicates the value difference between when a node unilaterally switches its policy and when it follows the same policy. The optimization
9
Algorithm 1 Game-theoretic distributed hop-by-hop routing algorithm Input: mixture weights α, β ∈ [0, 1]; initial policy πn1 for all n ∈ N . 1: for episode k = 1, 2, · · · do 2: for packet t = 1, · · · , τ do k 3: Each node n in parallel selects hop pk,t n ∼ πn to send a packet, observes reward rnk,t . 4: for node n = 1, · · · , N do in parallel 5: ρkn ← arg minλ∈∆(Pn ) det(M (λ)). k,t b kn Φ(p) ← 1 Pτ ψ(p)⊤ M (πnk )−1 ψ(pk,t 6: ∇ n )rn , for t=1 τ all p ∈ Pn . b kn Φ⟩. 7: π̃nk+1 ← arg maxλ∈∆(Pn ) ⟨λ, ∇ k k+1 k+1 8: πn ← α πn + β(π̃n − πnk ) + (1 − α)ρkn . | | {z } {z } Frank-Wolfe update
Exploration
objective is to learn a general policy π ∗ over T packets such that Nash-Regret(T ) ≤ ϵ,
(2)
where ϵ > 0 is a given tolerance threshold. B. Our algorithm We propose a game-theoretic distributed hop-by-hop routing algorithm based on the bandit feedback model [48], [60], [62], [66], [67]. The pseudo-code of the game-theoretic distributed hop selection algorithm is presented in Algorithm 1. The notations used in the algorithm are summarized in Appendix D. When node n receives a packet t in episode k from a previous node, it follows the current policy πnk to select the next hop pk,t n , sends the packet, and observes the corresponding reward rnk,t (line 3). Whenever node n has sent τ packets and collected τ rewards, it updates the policy πnk based on the τ rewards collected. First, we identify an exploratory policy with its policy correlation matrix: X M (λ) = λ(p)ψ(p)ψ(p)⊤ , (3) p∈λ
which has the minimum determinant among all possible policies in the probability simplex ∆(Pn ) over node n’s action space Pn (line 5), where λ(p) denotes the probability of selecting the next hop p, and ψ(p) represents the vector-valued function mapping hop p to a one-hot vector. Next, we use linear regression with τ rewards to estimate the gradient of the mapping from policy πnk to potential rewards for node n (line 6), where M (πnk )−1 represents the inverse of M (πnk ). We yield |Pn | gradient estimators, which form a b kn Φ = [∇ b kn Φ(p1 ), · · · , ∇ b kn Φ(p|P | )]. |Pn |-dimension vector ∇ n With the gradient estimator for all possible hops, we calculate the dot product of the estimator and all possible policies λ ∈ ∆(Pn ) and obtain the optimal policy π̃nk+1 that yields the maximum dot product (line 7). Lastly, we leverage the Frank-Wolfe method [68] to linear combine current policy πnk with optimal policy π̃nk+1 : πnk + β(π̃nk+1 − πnk ),
(4)
where β is in the range [0, 1]. The Frank-Wolfe update in Eq. (4) guarantees that the results of the linear combination fall in the probability simplex ∆(Pn ). In addition, we add exploratory policy ρkn to the Frank-Wolfe update (line 8): α πnk + β(π̃nk+1 − πnk ) + (1 − α)ρkn , (5) where α is also in the range [0, 1] and determines the extent to explore different policies. Node n follows the final policy πnk+1 by Eq. (5) to route packet τ +1 to τ +τ in episode k +1, and hence each episode k has individual policy πnk to route τ packets. We provide a numerical example to illustrate the workflow of Algorithm 1 in Appendix E, discuss how local congestion is observed and inferred at the application level in Appendix F, and analyze the implementation and adaptivity of Algorithm 1 in Appendix G. C. Theoretical analysis. We conduct a theoretical analysis on Algorithm 1 in two aspects: the Nash regret bound and time complexity. Theorem 1. Let T = kτ and assume that each policy in ∆(Pn ) has no zero element for all n. By running Algorithm 1 b kn Φ(p) defined in line 6 and exwith gradient estimator ∇ k ploratory policy ρn defined in line 5, if k ≥ N2 , then with probability 1 − δ, we have Nash-Regret(T ) ≤ Õ(N 2 T 5/6 log N ).
The proof details of Theorem 1 are given in Appendix H. The results in Theorem 1 demonstrate a sublinear Nash regret with polynomial dependence on N , the number of nodes. Following Definition 1 in [48] and Section 3 in [63], we obtain the following corollary. Corollary 1. Algorithm 1 reaches an ϵ-approximate Nash equilibrium. Corollary 1 tells us that nodes that run Algorithm 1 to update their policies can find a general policy such that a node receives at most ϵ more rewards by unilaterally changing its policy, implying reaching an ϵ-approximate Nash equilibrium. In addition, we provide the Nash regret guarantee under bounded asynchrony in the following corollary. Corollary 2. Under bounded asynchrony, the Nash regret guarantee in Theorem 1 continues to hold, up to an additional sublinear regret term induced by asynchrony. The proof details of Corollay 2 are given in Appendix I. Finally, we analyze the time complexity of Algorithm 1 in the following theorem. Theorem 2. The time complexity of Algorithm 1 in each episode is O(τ log3 N + |∆(Pn )| log3 N ), where τ represents the number of packets sent in each episode, and |∆(Pn )| denotes the number of policies node n can adopt. The proof details of Theorem 2 are given in Appendix J. VI. I MPLEMENTATION
10
We implement Totoro+ on top of the Pastry (v.2.1) [23] and PyTorch (v.2.10.0) [69] software stacks. Such implementation choice is motivated by the following considerations: (1) Pastry [49] is a widely used overlay and routing network for the implementation of a DHT similar to Chord [50]. Instead of implementing another distributed system core, we can leverage Pastry’s excellent routing substrate (e.g., O(log N ) node lookup), self-repairing routing table, message transportation layer, and scalable application-level multicast infrastructure (Scribe [70]). These features greatly simplify the development process. (2) PyTorch [24] provides a flexible and intuitive API for building neural networks. It also offers a rich ecosystem of libraries (e.g., TorchVision [71] and HuggingFace Transformers [72]) that support many modern neural network models. We made the following major modifications: (1) We changed the original single P2P ring structure to a new locality-aware P2P multi-ring structure. (2) We implemented a fully decentralized “many masters/many workers” architecture by utilizing DHTs and adding several data structures: a list of operations for tracking routing paths, selecting masters and workers, and constructing dynamically structured training trees. (3) We implemented a publish/subscribe messaging pattern for scalable model propagation and gradient aggregation. We introduced a serialization mechanism to convert trained models into binary arrays for low-cost communication over edge networks. (4) We introduced an advertise-discover mechanism to enable nodes to advertise and discover FL applications running over the overlay. We implemented a parallel recovery approach to dealing with the failure of masters and the failure of workers. (5) We implemented a game-theoretic path planning model to “autonomously” replan or repair the dynamically structured dataflow tree by collecting feedback, detecting node stragglers or failures, balancing network traffic, and creating alternative routes. We discuss the adaptivity of Totoro+ to edge heterogeneity in Appendix K.
VII. E VALUATION We evaluate Totoro+ ’s performance in a real-world distributed environment that includes 500 Amazon EC2 nodes and uses real-world computer vision (CV) and natural language processing (NLP) datasets at different scales. We have the following key results. Totoro+ scales the number of masters to handle a varying workload (from 125 to 2000 concurrently running FL applications) in real-world edge topologies (Section VII-B). + • Totoro achieves O(log N ) hops for model dissemination and gradient aggregation (Section VII-C). + outperforms state-of-the-art FL systems • Totoro (OpenFL [25] and FedScale [26]) by speeding up the training time 1.2×-14.0× to reach the equivalent model accuracy (Section VII-D). + • Totoro efficiently adapts to edge networks with constrained bandwidth capacity (Section VII-E). + • Totoro recovers from node failures to adapt to node churns (Section VII-F). •
A. Methodology Experimental setup. Totoro+ is designed to operate in large deployments with millions of edge nodes. However, such a deployment is prohibitively expensive and impractical in an academic environment. As such, we resort to emulating a realworld edge setting on 500 AWS EC2 t2.medium nodes, each of which has 2 vCPUs and 4GB of RAM, and 100 GB of disk: (1) we use one JVM to represent one edge node and emulate up to 100k edge nodes on the testbed; (2) we divide the 100k edge nodes into geo-distributed zones based on the real-world EUA dataset [73], which consists of 95,271 edge nodes distributed across 12 Australian states and regions. To emphasize the system-level benefits of Totoro+ , we conduct experiments using homogeneous nodes in the main paper. Experimental results under heterogeneous node settings are reported in Appendix L. Baselines. We use OpenFL (v.1.3) [25] and FedScale (v.0.5) [26] as the baseline. FedScale is a scalable and extensible open-source FL system and benchmarking suite developed by Symbiotic Lab [74], which provides high-level and flexible API to implement, evaluate, and deploy FL algorithms easily in both standalone (single CPU/GPU) and distributed (multiple machines) settings. OpenFL is an open-source framework developed by Intel that runs FL in a single-machine setting. Parameters. Totoro+ ’s Pastry DHT is configured with a leaf set of 24, max open sockets of 5000, and a transport buffer size of 6 MB. We configure different fanouts 8 (23 ), 16 (24 ), and 32 (25 ) for Totoro+ ’s dataflow trees by changing the DHT routing table base bit values to 3, 4, and 5, respectively. The minibatch size of each node is 20 in image classification and speech recognition tasks. The initial learning rate for the ShuffleNet V2 model is 0.05 and 0.1 for the ResNet-34 model. Metrics. We focus on Totoro+ ’s scalability, adaptivity, and FL effectiveness. To evaluate scalability, we measure how numerous applications’ dataflow trees are distributed over largescale edge topologies. We also measure how Totoro+ scales with the number of nodes in terms of model broadcast time and gradient aggregation time. To evaluate the FL effectiveness, we measure time-to-accuracy performance, which is the duration of model training tasks on the testing set to achieve the target accuracy. To evaluate adaptivity, we measure cumulative packet latency, Nash regret, node selection frequencies, and failure recovery time. We also measure Totoro+ ’s runtime overhead. B. Scalability analysis Figure 5(a) shows the real-world edge zones generated from the EUA dataset [73]. Australian Communications and Media Authority publishes the EUA dataset [73], which contains the geographical locations of 95,271 cellular base stations in 12 states of Australia (ACT: 931, ANT: 15, EXT: 8, ISL: 36, NSW: 24574, NT: 3137, QLD: 21576, SA: 7682, TAS: 3213, VIC: 18163, WA: 15933, WLD: 3). We estimate the maximum roundtrip time based on the distances between nodes in the dataset, and then use Ratnasamy and Shenker’s distributed binning algorithm [55] to divide them into different zones. Totoro+ fairly distributes masters. Figure 5(b) shows the normal probability plot of the number of masters mapped on
1 R U P D O 3 H U F H Q W L O H
Latitude (South)
11
' D W D I O R Z 7 U H H V ' D W D I O R Z 7 U H H V ' D W D I O R Z 7 U H H V 5 H I H U H Q F H / L Q H
$ S S O L F D W L R Q 0 D V W H U V S H U 1 R G H
(a) Real-world edge topologies generated from the EUA dataset [73].
(b) Normal probability plot of the number of masters mapped per node.
(c) Totoro+ scales with #masters to handle the varying workload.
20° 22° 24° 26° 28° 30°
M L1 L2 L3 L4 L5
141° 143° 145° 147° Longitude (East)
(d) The distribution of Totoro’s dataflow trees over edge topologies.
1 X P E H U R I ( G J H 1 R G H V
(a) Model dissemination time.
7 R W R U R 5 H V 1 H W 7 R W R U R 5 H V 1 H W 7 R W R U R 6 K X I I O H 1 H W 9 7 R W R U R 6 K X I I O H 1 H W 9
1 X P E H U R I ( G J H 1 R G H V
(b) Gradient aggregation time.
) D Q R X W ) D Q R X W
) D Q R X W ) D Q R X W
) D Q R X W
1 X P E H U R I ( G J H 1 R G H V
(c) Model dissemination time of different fanouts.
* U D G L H Q W $ J J U H J D W L R Q 7 L P H P V
7 R W R U R 5 H V 1 H W 7 R W R U R 5 H V 1 H W 7 R W R U R 6 K X I I O H 1 H W 9 7 R W R U R 6 K X I I O H 1 H W 9
0 R G H O ' L V V H P L Q D W L R Q 7 L P H P V
* U D G L H Q W $ J J U H J D W L R Q 7 L P H P V
0 R G H O ' L V V H P L Q D W L R Q 7 L P H P V
Fig. 5: Totoro+ excels at scalability by fairly distributing many dynamic-structured dataflow trees across large-scale edge topologies.
) D Q R X W ) D Q R X W
) D Q R X W ) D Q R X W
) D Q R X W
1 X P E H U R I ( G J H 1 R G H V
(d) Gradient Aggregation time of different fanouts.
7 R W R U R 7 & 3 % D V H O L Q H V 7 & 3
1 X P E H U R I ' D W D I O R Z 7 U H H V (a) TCP traffic cost.
7 U D I I L F 5 D W L R S H U 1 R G H
7 U D I I L F 5 D W L R S H U 1 R G H
Fig. 6: Totoro+ scales with an exponentially increasing number of edge nodes for model dissemination and gradient aggregation.
7 R W R U R 8 ' 3 % D V H O L Q H V 8 ' 3
1 X P E H U R I ' D W D I O R Z 7 U H H V (b) UDP traffic cost.
Fig. 7: Totoro+ reduces communication cost. each node in a 1000-node edge zone under stress testing. The results show that when we create a large number of dataflow trees like 500, 99.5% of the nodes are the roots of 3 trees or less. The results illustrate a good load balance among participating devices when performing a large number of FL applications’ tasks simultaneously. Figure 5(c) shows the distribution of Totoro+ ’s masters over different edge zones that have different workloads. We assume densely populated topologies have heavy workloads and sparsely populated topologies have light workloads. The results show that Totoro+ automatically scales the number of masters to handle the varying workload. Totoro+ excels at load balancing. Figure 5(d) shows the distribution of all branches in 17 Totoro+ dataflow trees on 1946 edge nodes over the 3 most popular topologies. Each tree has a fanout of 8 (23 ) and a random number of depths (from level 1 to level 6). Different colors represent different levels of nodes in a tree, with the darkest color representing the root node. The results show that these dataflow trees are well balanced across different topologies, not only the root nodes but also the forwarder nodes and the leaf nodes, demonstrating Totoro+ ’s attractive scalability and load balancing properties.
C. Model dissemination and gradient aggregation Totoro+ scales with #nodes. Figure 6(a) and Figure 6(b) show Totoro+ ’s model dissemination and gradient aggregation times for an exponentially increasing number of edge nodes in a single training tree. When the number of nodes grows exponentially (from 20 to 5120), the dissemination time and aggregation time only increase linearly. This is because the dissemination time and aggregation time are limited by the dataflow tree depth (O(log N )) by using the DHT-based P2P overlay. Therefore, when the number of edge devices grows to the scale of millions or even billions, Totoro+ guarantees that only a few extra hops are needed for them to receive updated FL models or send updated gradients. Totoro+ offers flexible tree fanouts. Figure 6(c) and Figure 6(d) show the model dissemination time and gradient aggregation time of different tree fanouts for the ResNet34 model. We can observe that a larger fanout leads to less model dissemination and gradient aggregation times because the dataflow trees become less deep. However, if an internal node fails or leaves, the new one needs to rebuild many connections between the child nodes and the parent nodes to rebuild the tree, and the new node may become an I/O or communication bottleneck. Totoro+ reduces communication cost. Figure 7 shows the comparison of the traffic per node of Totoro+ and the baseline FL systems. Communication is a critical bottleneck in FL systems. We can observe that the additional network traffic imposed by Totoro+ is small. The network traffic is increased by only 1.19× for TCP and 1.29× for UDP when the number of dataflow trees is increased by 10×. This is because when a new training tree is created, it merely routes JOIN messages toward the root of the tree using the overlay, adding overlay links to reconstruct the tree without establishing a new
12
Task
Dataset
Accuracy Target
Model
Speech Recognition
Google Speech [75]
53.0%
ResNet-34 [76]
Image Classification
FEMNIST [9]
75.5%
ShuffleNet V2 [77]
Number of Applications 5 10 20 5 10 20
Speedup for OpenFL [25] Fan.=8 Fan.=16 Fan.=32 3.7× 3.1× 3.5× 6.4× 6.2× 6.9× 13.0× 11.8× 14.0× 1.2× 1.4× 3.1× 2.4× 3.2× 5.6× 5.0× 5.5× 10.3×
Speedup for FedScale [26] Fan.=8 Fan.=16 Fan.=32 3.6× 3.0× 3.4× 6.2× 6.0× 6.7× 12.4× 11.3× 13.5× 1.4× 1.6× 3.4× 2.7× 3.5× 6.1× 5.6× 6.1× 11.5×
TABLE III: Summary of time-to-accuracy comparison of Totoro+ , OpenFL, and FedScale. We set three different fanouts for Totoro+ ’s dataflow tree: 8, 16, and 32. Totoro+ outperforms state-of-the-art FL systems by speeding up the training time at different scales. The speedup gap increases as the number of concurrently running applications’ tasks increases.
7 R W D O 7 U D L Q L Q J 7 L P H K R X U V
(a) 1 application’s model
7 R W R U R I 7 R W R U R I 7 R W R U R I 2 S H Q ) / ) H G 6 F D O H
7 R W D O 7 U D L Q L Q J 7 L P H K R X U V
(b) 5 models trained simultaneously
7 R W R U R I 7 R W R U R I 7 R W R U R I 2 S H Q ) / ) H G 6 F D O H
$ F F X U D F \
7 R W R U R I 7 R W R U R I 7 R W R U R I 2 S H Q ) / ) H G 6 F D O H
$ F F X U D F \
$ F F X U D F \
$ F F X U D F \
7 R W D O 7 U D L Q L Q J 7 L P H K R X U V
(c) 10 models trained simultaneously
7 R W R U R I 7 R W R U R I 7 R W R U R I 2 S H Q ) / ) H G 6 F D O H
7 R W D O 7 U D L Q L Q J 7 L P H K R X U V
(d) 20 models trained simultaneously
Fig. 8: Time-to-accuracy comparison of Totoro+ , OpenFL, and FedScale. When 5∼20 applications’ models are simultaneously trained, Totoro+ speeds up the total training time 3.0×-14.0× to reach the equivalent model accuracy on the middle-scale Google Speech dataset.
7 R W D O 7 U D L Q L Q J 7 L P H K R X U V
(a) 1 application’s model
7 R W R U R I 7 R W R U R I 7 R W R U R I 2 S H Q ) / ) H G 6 F D O H
7 R W D O 7 U D L Q L Q J 7 L P H K R X U V
(b) 5 models trained simultaneously
7 R W R U R I 7 R W R U R I 7 R W R U R I 2 S H Q ) / ) H G 6 F D O H
7 R W D O 7 U D L Q L Q J 7 L P H K R X U V
(c) 10 models trained simultaneously
$ F F X U D F \
7 R W R U R I 7 R W R U R I 7 R W R U R I 2 S H Q ) / ) H G 6 F D O H
$ F F X U D F \
$ F F X U D F \
$ F F X U D F \
7 R W R U R I 7 R W R U R I 7 R W R U R I 2 S H Q ) / ) H G 6 F D O H
7 R W D O 7 U D L Q L Q J 7 L P H K R X U V
(d) 20 models trained simultaneously
Fig. 9: Time-to-accuracy comparison of Totoro+ , OpenFL, and FedScale. When 5∼20 applications’ models are simultaneously trained, Totoro+ speeds up the total training time 1.2×-11.5× to reach the equivalent model accuracy on the large-scale FEMNIST dataset. connection. Then the overhead for creating new dataflow trees can be amortized over the overhead of the overlay.
D. Federated learning effectiveness In this section, we evaluate Totoro+ ’s performance on model training when an increasing number of models (1 to 20) are simultaneously trained on large-scale edge topologies, and compare it with OpenFL [25] and FedScale [26]. Both FedScale and OpenFL rely on a server-client architecture and leverage a logically central coordinator to spawn aggregators and orchestrate many distributed clients to collaboratively train a model. For both the Google Speech [75] and FEMNIST [9] datasets, we evenly partitioned the data across the edge nodes such that each node contains samples from all classes. This IID setting allows us to isolate and compare pure systemlevel performance differences among Totoro+ , OpenFL, and FedScale under the same controlled conditions. All compared systems follow the same data partitioning strategy.
Totoro+ reduces the total model training time. Table III summarizes the results of time-to-accuracy comparison of Totoro+ , OpenFL and FedScale. When 5∼20 models are simultaneously trained on the same platform, we notice that Totoro+ speeds up the total training time 3.0×-14.0× to reach the equivalent model accuracy on the middle-scale Google Speech dataset; speedup on the large-scale FEMNIST dataset is 1.2×-11.5×. The speedup gap increases as the number of concurrently running applications’ tasks increases. This is because both OpenFL and FedScale rely on a server-client architecture where a logically central coordinator orchestrates many distributed clients to collaboratively train a model. When there are a massive number of models that need to be trained simultaneously, the central coordinator needs to handle them one by one on a first-come, first-served basis, which causes large queuing delays. By contrast, Totoro+ ’s distributed masters can train many models in parallel, thus precluding them from being stuck in a central coordinator. To further evaluate the effectiveness of Totoro+ , we compare it
13
/ D W L W X G H 6 R X W K
6 H U Y H U V
( Q G G H Y L F H V
/ R Q J L W X G H ( D V W
Fig. 10: 100 edge servers and 900 end devices in Melbourne, Australia, from the EUA dataset [73] with decentralized federated learning baselines on additional models and datasets. The results are presented in Appendix M. Totoro+ scales with #applications. Figure 8 and Figure 9 show the time-to-accuracy performance comparison of Totoro+ , OpenFL, and FedScale. The shaded regions represent the standard deviations, and the red dotted lines represent the target accuracies for Google Speech (53.0%) and FEMNIST (75.5%). The results show that Totoro+ scales well with a large number of applications’ training tasks. Totoro+ takes almost the same total training time to reach model convergence for training 1 model (15.41 hours), 5 models (15.43 hours), 10 models (15.44 hours), and 20 models (15.47 hours) when fanout is equal to 32. The rationale behind the results lies in that (1) Totoro+ decomposes the conventional “1:n” architecture into an “m:n” architecture, which ensures that every peer can participate in the process of model training, gradients calculation, and aggregation; and (2) ideally, any peer in the system can act as a worker, a master, a forwarder, or any combination of the above. This helps avoid the scalability bottleneck caused by any single node, auto-scale as needed, balance the workload, and improve the scalability. E. Adaptivity analysis We evaluate Totoro+ ’s game-theoretic distributed hop-byhop routing algorithm using a real-world distribution of edge servers and end devices in the EUA dataset [73]. We randomly extracted 900 end devices and 100 edge servers in Melbourne, Australia, from coordinate −37.820 to −37.808 in latitude and 144.955 to 144.975 in longitude, as shown in Figure 10. These 1,000 nodes establish a dataflow tree, where the 900 end devices are worker nodes, an edge server serves as a master, and the remaining 99 edge servers are internal nodes. The worker and internal nodes run three algorithms to select the next hops for model updates. + • Totoro : The game-theoretic distributed hop-by-hop routing algorithm in Algorithm 1. • Totoro [1]: The bandit-based distributed hop-by-hop algorithm that does not consider bandwidth capacities. • OPT: The optimal algorithm that always selects the optimal next hop and considers bandwidth capacities. We refer to [59], [78] to set the constrained bandwidth of each node in the range between 20Mbps and 100Mbps. Each worker and internal node has constrained bandwidth. The more packets it forwards simultaneously, the slower its data rate becomes. For example, if a node with 100Mbps bandwidth
needs to forward model updates from four nodes, the data rate is 100/4 = 25. Also, the higher the data rate, the higher the corresponding reward. Totoro+ adapts to edge networks with constrained bandwidth capacity. Figure 11 shows the cumulative packet latency of three algorithms. We can see that Totoro+ achieves a cumulative packet latency that grows slowly. In contrast, Bandit suffers a higher cumulative packet latency. This is because Totoro+ considers that nodes’ bandwidth decreases proportionally if they have to forward many packets simultaneously. Hence, Totoro+ tends to distribute network traffic more evenly over all nodes. Figure 12 shows cumulative probabilities of different algorithms over latency. Totoro+ consistently outperforms Totoro in latency, regardless of the choice of α, delivering nearly all responses under 2000 ms. The results explain why Totoro+ can achieve lower cumulative packet latency in Figure 11. Totoro+ achieves an ϵ-approximate Nash equilibrium. Figure 13 shows the Nash regret comparison of Totoro+ , OPT, and a reference line. We refer to the solution from [48] as the reference line, where the solution is proved to achieve sublinear Nash regret with the G-optimal design. The results show that Totoro+ achieves a sublinear Nash regret closer to OPT. Therefore, according to Corollary 1, Totoro+ achieves an ϵ-approximate Nash equilibrium. In contrast, Totoro does not consider bandwidth capacities but selects the optimal next hop so far. Therefore, when too many nodes select the same next hop, the overall communication time increases, which significantly increases Nash regret. Figure 14 shows the node selection frequencies generated by different algorithms, in which each color grid shows the frequencies of selecting the xth node for each packet. The X-axis represents the sequential order of next-hop nodes. The Y -axis represents the sequential order of packets. Although Totoro relies on a distributed hop-by-hop routing algorithm to send packets, it does not distribute packets evenly across all possible next hops. Instead, Totoro+ ’s improved gametheoretic routing algorithm considers bandwidth capacities across nodes and distributes packets more evenly across all possible next hops, thereby leading to lower Nash regret. Totoro+ forwards packets rapidly. Figure 15 shows the running time comparison of Totoro and Totoro+ . We can see that Totoro+ maintains consistently low running time (≈50 ms) regardless of the number of nodes, whereas Totoro’s running time sharply increases up to around 1500 ms when the number of nodes increases from 0 to 100. This is because a node has to run the convex optimization to evaluate the empirical transmission cost for each possible hop. Instead, Totoro+ ’s operations can be implemented by parallel matrix multiplications. Figure 16 shows the Totoro+ ’s running time breakdown. Lines 5, 6, 7, and 8 represent 4 lines in Algorithm 1. We can see that the proportion of Line 5 increases significantly when the number of nodes increases. This is because Line 5 requires calculating determinant among all possible policies, which is consistent with the results in Theorem 2.
3 D F N H W V (×100)
Fig. 11: Cumulative packet latency of different algorithms.
/ L Q H
1 R G H V
) D L O X U H 5 H F R Y H U \ 7 L P H P V
Fig. 15: Running time comparison. ) D Q R X W
) D Q R X W
) D Q R X W
1 X P E H U R I ) D L O H G 1 R G H V +
/ L Q H
1 R G H V
Fig. 16: Totoro+’s running time breakdown.
) D Q R X W
) D Q R X W
) D Q R X W
3 D F N H W , '
7 R W R U R
7 R W R U R
6 H O H F W L R Q ) U H T X H Q F \
H
O L Q
I H U H Q F H
5 H
7 R W R U R
(α = 0.1) (α = 0.5) (α = 0.9)
1 R G H , '
Fig. 14: Node selection frequencies generated by different algorithms. 0 D V W H U 7 U D L Q L Q J : R U N H U 7 U D L Q L Q J
7 L P H V
2 S H Q ) / ) H G 6 F D O H
7 L P H V
overhead. 7 L P H V (b) The memory +
(a) The CPU overhead.
Fig. 19: Overhead comparison of Totoro , OpenFL, and FedScale. without having to talk to a central coordinator, so many simultaneous failures can be repaired in parallel.
0 D V W H U 2 Y H U O D \ : R U N H U 2 Y H U O D \
/ L Q H
7 R W R U R
Fig. regret of dif13: Nash 3 D F N H W V (×algorithms. 100) ferent
& 3 8 8 V D J H
7 R W R U R 7 R W R U R
3 H U F H Q W D J H
/ L Q H
) D L O X U H 5 H F R Y H U \ 7 L P H P V
5 X Q Q L Q J 7 L P H P V
Fig. 12: Cumulative probabilities of different algorithms over latency.
0 H P R U \ 8 V D J H
& 3 8 8 V D J H
7 R W R U R α = 0.9 7 R W R U R α = 0.5 7 R W R U R α = 0.1 / D W H Q F \ ×100 P V 3 D F N H W V (×100) 1 D V K 5 H J U H W
2 3 7
& X P X O D W L Y H 3 D F N H W / D W H Q F \ V
7 R W R U R
& X P X O D W L Y H 3 U R E D E L O L W \
& X P X O D W L Y H 3 D F N H W / D W H Q F \ V
14
1 X P E H U R I ' D W D I O R Z 7 U H H V +
Fig. 17: Totoro tolerates Fig. 18: Totoro achieves many simultaneous node fail- a stable recovery time for many simultaneous node failures in a tree. ures in many trees. F. Failure recovery analysis In this section, we evaluate how long it takes Totoro+ to recover from node failures in a single and many dataflow trees. Totoro+ tolerates simultaneous node failures in a dataflow tree. Figure 17 shows the failure recovery time for recovering a single dataflow tree with an exponentially increasing number of failed nodes. The tree has 1,000 nodes at the beginning, and then a varying number of random nodes fail or leave the tree simultaneously. The results show that the failure recovery time increases linearly when the number of failed nodes grows exponentially (from 1 to 128). This is because only O(log2b N ) nodes are involved in recovering the tree. Even though the root fails, its immediate child nodes can locate a new root, and it can recover the state from the replicas. Totoro+ achieves a stable recovery time for many simultaneous trees’ failures. Figure 18 shows the failure recovery time for an exponentially increasing number of dataflow trees. Each tree has at most 1,000 nodes, and 5% of nodes fail or leave simultaneously. The results show that Totoro+ achieves a stable recovery time for many simultaneous trees’ failures. This is because each failed node can be quickly detected and recovered by its neighbors through keep-alive messages
G. Overhead analysis We train a feedforward model for text classification with a single Totoro+ ’s dataflow tree of 10 nodes and compare the overhead with OpenFL and FedScale. CPU overhead. Figure 19(a) shows the CPU overhead comparison of Totoro+ , OpenFL, and FedScale. For a fair comparison, we divide the CPU overhead into two parts: “Overlay” and “Training”, where Overlay represents DHT-related tasks(including constructing P2P overlay, overlay maintenance, building dataflow trees, replanning paths, etc.), whereas Training includes any FL-related tasks (e.g., model training, model validation, model aggregation, etc.). Also, “Master” and “Worker” represent resource usage on the master node and worker node in a Totoro+ ’s dataflow tree, respectively. The results show that the master and worker nodes collaboratively run the FL-related tasks, so the CPU usage on these two nodes takes turns reaching the peak. In contrast, OpenFL and FedScale maintain high CPU usage all the time. For DHTrelated tasks, Totoro+ only adds negligible CPU overhead, demonstrating Totoro+ ’s portability to resource-constrained edge nodes. Memory overhead. Figure 19(b) shows the memory overhead comparison of Totoro+ , OpenFL, and FedScale. The initial increase in the memory overhead of Overlay is because of the construction of the P2P overlay, routing tables, neighborhood sets, leaf sets, and dataflow trees. After the DHT starts functioning, no additional memory overhead is added in either the master (root node) or the leaf nodes. For FL-related
15
Federated learning systems
Architecture
FedAT [79], TiFL [34], Oort [35], PyramidFL [80] FLOAT [10], REFL [11] AdaFL [81], FeS [82], DoFed-SPP [83] Client-edge-cloud [84], Edge-DemLearn [45] HiFlash [85], Hwamei [86], ShapeFL [87], FedUC [88], AHFL [89] D2 [90], BrainTorrent [91], Lalitha et al. [92] ByRDiE [93], BRIDGE [94], Gupta et al. [95] Bellet et al. [96], Vanhaesebrouck et al. [97] AsyDFL [98], YOGA [99], FRACTAL [100], DFLStar [101], FedHP [102]
Centralized Centralized Centralized Hierarchical
Central parameter server ✓ ✓ ✓ ✓
Hierarchical Decentralized Decentralized Decentralized
Totoro+
Datacenter Cloud Edge Edge
Master/worker communication structure Hub-and-spoke Hub-and-spoke Hub-and-spoke Hub-and-spoke
Type of learned model Global consensus Global consensus Global consensus Global consensus
Scale to massive diverse applications ✗ ✗ ✗ ✗
Adapt to edge networks ✗ ✓ ✓ ✗
✓
Edge
Dynamically structured tree
Global consensus
✗
✓
✗ ✗ ✗
Datacenter Datacenter Datacenter
P2P (one-hop neighbor) P2P (one-hop neighbor) P2P (one-hop neighbor)
Global consensus Global consensus Personalized
✗ ✗ ✗
✗ ✗ ✗
Decentralized
✗
Edge
P2P (one-hop neighbor)
Personalized
✗
✓
Decentralized
✗
Edge
Dynamically structured tree
Global consensus
✓
✓
Computing environment
TABLE IV: Overview of state-of-the-art federated learning system designs compared to Totoro+ . tasks, the memory usage of Training on the master and worker nodes matches the trend of CPU usage. OpenFL and FedScale demand more and more memory as they allocate and cache models, training data, and other necessary metadata in memory all the time. VIII. R ELATED W ORK This section discusses existing FL system designs and their shortcomings for deployment in edge platforms (Table IV). Centralized FL systems. The centralized server-client architecture is widely used in state-of-the-art FL systems such as Oort [35], FedAT [79], PyramidFL [80], TiFL [34], and FEDRECON [103]. In these systems, a powerful centralized parameter server and sufficient node-to-server bandwidth are provided to maintain the communications between the parameter server and clients. These systems focus on optimizing participant selection strategies [34], [35], [79], [80], improving communication efficiency [39], [104], tackling data heterogeneity [56], [83], [105], or ensuring privacy [57], [106]. For example, many algorithms have been proposed to reduce the communication overhead concentrated on the central server by reducing communication rounds with local updates allowance [107], [108], employing compression techniques to reduce the transmitted bits [109], [110], and sampling a subset of clients [34], [35], [79]. Some systems harness workers’ resource strengths with feedback integration [10], [11], [81], [82]. FLOAT [10] adopts a multi-objective reinforcement learning agent that autonomously selects optimization techniques and configurations to meet individual client resource conditions. AdaFL [81] aims at NLP federated learning and introduces an online configurator that automatically adjusts the tuning depth and width based on training accuracy, perround training time, and network time for each communication round. While these systems work well in resource-rich datacenters, the centralized control plane with a static assignment of parameter servers may not adapt well to resourceconstrained edge settings with millions of nodes, numerous FL applications, and unreliable network links. Hierarchical FL systems. In hierarchical FL systems, an intermediate layer (e.g., edge servers) is inserted between the central server and client devices to perform partial aggregations on distributed local models before the global aggregation. The intermediate layer helps mitigate the non-independent and identically distributed (non-IID) effects of client data [45], control the staleness of model updates [85] from client devices
with heterogeneous resources, synchronize edge and cloud aggregation frequencies [86], associate client devices with edge servers for training and communication efficiency [87], [88], reduce the communication burden on the central server [84], [111], and offload the computation burden from client devices to edge servers [89]. Abad et al. [111] employ small cell-base stations to orchestrate federated learning among mobile users and periodically exchange model updates with the macro-base station for global model learning. AHFL [89] proposes to offload the training overhead from end devices to edge servers and inject local noise to secure data privacy while the cloud is responsible for model aggregation only. Although this structure enhances scalability with additional edge aggregators, they may become points of failure, causing disconnection between the central server and client devices and interrupting the training process. Some studies like HiFlash [85], FedUC [88], and AHFL [89] leverage asynchronous aggregation between edge aggregators and cloud aggregators to avoid points of failure, but additional efforts to balance cloud aggregation and edge aggregation frequencies. Peer-to-peer FL (P2PFL) systems. P2PFL is a distributed learning protocol without a central parameter server. The key idea is to leverage P2P communication between individual clients to exchange model updates. Model aggregation and updates are performed locally on client nodes with the acquired gradients from their one-hop neighbors. Previous P2PFL research considered design from different angles: adversarial models (non-Byzantine vs. Byzantine settings) and learned models (global consensus vs. personalized). Non-Byzantine algorithms [90]–[92] focus on improving convergence speed. Conversely, Byzantine algorithms [93]–[95] aim to ensure that the trained model remains close to the model learned without adversaries. Global consensus learning [90]–[95] aims to generate a single global model at the end of training, while personalized learning [96], [97] allows each peer to train a unique model. Some studies aim to improve the training efficiency of P2PFL [98]–[100], [102]. AsyDFL [98] proposes to push a subset of gradient updates to peer to trade-off communication cost and training accuracy and leverage asynchronous model aggregation to mitigate the straggler effect. FedHP [102] integrates adaptive control of both local updating frequency and network topology to speed up convergence and improve model accuracy. These efforts mostly focus on novel algorithm development for P2P model aggregation and communication topology construction without considering cross-layer support of implementation. Totoro+ backs up the P2PFL work with
16
a back-end architecture for task management, applicationspecific customization, and failure recovery. IX. C ONCLUSION We present Totoro+ , a novel scalable federated learning system for edge networks. It presents three design innovations: a locality-aware P2P multi-ring structure, a publish/subscribebased forest abstraction, and a game-theoretic path planning model. We evaluate Totoro+ on 500 Amazon EC2 nodes using real-world CV and NLP datasets at different scales. We compare Totoro+ with the state-of-the-art and demonstrate substantial advancements in scalability and load balancing while significantly speeding up the total training time for many concurrently running applications, reducing the communication overhead, and efficiently adapting to unreliable edge networks and churns. We provide a theoretical guarantee that the game-theoretic path planning model achieves an ϵapproximate Nash equilibrium. We present the discussions and future work in Appendix N. ACKNOWLEDGMENT The authors would like to thank the Editor-in-Chief, the associate editor, and the reviewers for their valuable comments and constructive suggestions, which significantly improved the quality of this article. The authors also thank Yue Lin and Shih-Jhi Liang for their assistance in the experimental evaluation and validation of the proposed routing algorithm. R EFERENCES [1] C.-W. Ching, X. Chen, T. Kim, B. Ji, Q. Wang, D. Da Silva, and L. Hu, “Totoro: A scalable federated learning engine for the edge,” in Proceedings of the Nineteenth European Conference on Computer Systems, 2024, p. 182–199. [Online]. Available: https://doi.org/10.1145/3627703.3629575 [2] Y. Chen, Y. Ning, M. Slawski, and H. Rangwala, “Asynchronous online federated learning for edge devices with non-iid data,” in IEEE International Conference on Big Data, 2020, pp. 15–24. [3] Y. Chen, X. Sun, and Y. Jin, “Communication-efficient federated deep learning with layerwise asynchronous model update and temporally weighted aggregation,” IEEE Transactions on Neural Networks and Learning Systems, vol. 31, no. 10, pp. 4229–4238, 2020. [4] V. Smith, C.-K. Chiang, M. Sanjabi, and A. S. Talwalkar, “Federated multi-task learning,” Advances in neural information processing systems, vol. 30, 2017. [5] A. Hard et al., “Federated learning for mobile keyboard prediction,” arXiv preprint arXiv:1811.03604, 2018. [6] T. Yang et al., “Applied federated learning: Improving google keyboard query suggestions,” arXiv preprint arXiv:1812.02903, 2018. [7] H. Ludwig et al., “IBM federated learning: an enterprise framework white paper v0. 1,” arXiv preprint arXiv:2007.10987, 2020. [8] Tensorflow federated: Machine learning on decentralized data. https: //www.tensorflow.org/federated. [9] S. Caldas et al., “Leaf: A benchmark for federated settings,” arXiv preprint arXiv:1812.01097, 2018. [10] A. F. Khan, A. A. Khan, A. M. Abdelmoniem, S. Fountain, A. R. Butt, and A. Anwar, “FLOAT: Federated learning optimizations with automated tuning,” in Proceedings of the Nineteenth European Conference on Computer Systems, 2024, pp. 200–218. [11] A. M. Abdelmoniem, A. N. Sahu, M. Canini, and S. A. Fahmy, “REFL: Resource-efficient federated learning,” in Proceedings of the Eighteenth European Conference on Computer Systems, 2023, pp. 215–232. [12] PySyft: A library for easy federated learning. https://github.com/ OpenMined/PySyft. [13] “United states department of transportation annual modal research plans,” https://www.transportation.gov/sites/dot.gov/files/2024-08/ AMRP%20FY2024%20-%202025%20ITSJPO.pdf.
[14] S. Hochreiter and J. Schmidhuber, “Long short-term memory,” Neural Computation, vol. 9, no. 8, pp. 1735–1780, 1997. [15] R. Du, K. Han, R. Gupta, S. Chen, S. Labi, and Z. Wang, “Driver monitoring-based lane-change prediction: A personalized federated learning framework,” in IEEE Intelligent Vehicles Symposium, 2023, pp. 1–7. [16] N. Wang, X. Li, Z. Guan, and S. Yuan, “Fedstream: A federated learning framework on heterogeneous streaming data for next-generation traffic analysis,” IEEE Transactions on Network Science and Engineering, vol. 11, no. 3, pp. 2485–2496, 2023. [17] X. Wang, W. Liu, H. Lin, J. Hu, K. Kaur, and M. S. Hossain, “Aiempowered trajectory anomaly detection for intelligent transportation systems: A hierarchical federated learning approach,” IEEE Transactions on Intelligent Transportation Systems, vol. 24, no. 4, pp. 4631– 4640, 2022. [18] Bittorrent. http://www.bittorrent.com/. [19] Storj.io. http://storj.io/. [20] Freenet: The free network. https://freenetproject.org/. [21] M. Zhao et al., “Peer-assisted content distribution in akamai netsession,” in Proceedings of the 2013 conference on Internet measurement conference, 2013, pp. 31–42. [22] K. Croman et al., “On scaling decentralized blockchains: (a position paper),” in International conference on financial cryptography and data security. Springer, 2016, pp. 106–125. [23] Pastry. https://www.freepastry.org/FreePastry/. [24] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, “PyTorch: An imperative style, high-performance deep learning library,” in Advances in Neural Information Processing Systems, vol. 32. Curran Associates, Inc., 2019. [Online]. Available: https://proceedings.neurips.cc/paper files/ paper/2019/file/bdbca288fee7f92f2bfa9f7012727740-Paper.pdf [25] OpenFL - an open-source framework for federated learning. https:// openfl.readthedocs.io/. [26] F. Lai, Y. Dai, S. Singapuram, J. Liu, X. Zhu, H. Madhyastha, and M. Chowdhury, “FedScale: Benchmarking model and system performance of federated learning at scale,” in Proceedings of the 39th International Conference on Machine Learning, vol. 162. PMLR, 17–23 Jul 2022, pp. 11 814–11 827. [Online]. Available: https://proceedings.mlr.press/v162/lai22a.html [27] S. R. Pandey, N. H. Tran, M. Bennis, Y. K. Tun, A. Manzoor, and C. S. Hong, “A crowdsourcing framework for on-device federated learning,” IEEE Transactions on Wireless Communications, vol. 19, no. 5, pp. 3241–3256, 2020. [28] R. Xiong et al., “CoPiFL: A collusion-resistant and privacy-preserving federated learning crowdsourcing scheme using blockchain and homomorphic encryption,” Future Generation Computer Systems, vol. 156, pp. 95–104, 2024. [29] D. Huba et al., “PAPAYA: Practical, private, and scalable federated learning,” Proceedings of Machine Learning and Systems, vol. 4, pp. 814–832, 2022. [30] E. Wang, B. Chen, M. Chowdhury, A. Kannan, and F. Liang, “FLINT: A platform for federated learning integration,” Proceedings of Machine Learning and Systems, vol. 5, pp. 21–34, 2023. [31] K. Bonawitz et al., “Towards federated learning at scale: System design,” in Proceedings of Machine Learning and Systems, vol. 1, 2019, pp. 374–388. [32] M. Paulik et al., “Federated evaluation and tuning for on-device personalization: System design & applications,” arXiv preprint arXiv:2102.08503, 2021. [33] R. Pietrantuono, M. Ficco, and F. Palmieri, “Testing the resilience of mec-based iot applications against resource exhaustion attacks,” IEEE Transactions on Dependable and Secure Computing, vol. 21, no. 2, pp. 804–818, 2024. [34] Z. Chai et al., “TiFL: A tier-based federated learning system,” in Proceedings of the 29th international symposium on high-performance parallel and distributed computing, 2020, pp. 125–136. [35] F. Lai, X. Zhu, H. V. Madhyastha, and M. Chowdhury, “Oort: Efficient federated learning via guided participant selection,” in 15th USENIX Symposium on Operating Systems Design and Implementation, 2021, pp. 19–35. [36] T. Nishio and R. Yonetani, “Client selection for federated learning with heterogeneous resources in mobile edge,” in IEEE International Conference on Communications, 2019, pp. 1–7. [37] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic, “QSGD: Communication-efficient sgd via gradient quantization and encoding,” Advances in neural information processing systems, vol. 30, 2017.
17
[38] J. Bernstein, J. Zhao, K. Azizzadenesheli, and A. Anandkumar, “signSGD with majority vote is communication efficient and fault tolerant,” in International Conference on Learning Representations, 2019. [39] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in Artificial intelligence and statistics. PMLR, 2017, pp. 1273–1282. [40] D. Stripelis, P. M. Thompson, and J. L. Ambite, “Semi-synchronous federated learning for energy-efficient training and accelerated convergence in cross-silo settings,” ACM Transactions on Intelligent Systems and Technology, vol. 13, no. 5, pp. 1–29, 2022. [41] C. Xie, S. Koyejo, and I. Gupta, “Asynchronous federated optimization,” in Advances in Neural Information Processing Systems Workshop on Optimization for Machine Learning, 2020. [42] S. Wang et al., “Adaptive federated learning in resource constrained edge computing systems,” IEEE Journal on Selected Areas in Communications, vol. 37, no. 6, pp. 1205–1221, 2019. [43] L. U. Khan et al., “Federated learning for edge networks: Resource optimization and incentive mechanism,” IEEE Communications Magazine, vol. 58, no. 10, pp. 88–93, 2020. [44] M. S. Aslanpour et al., “Serverless edge computing: vision and challenges,” in Proceedings of the 2021 Australasian computer science week multiconference, 2021, pp. 1–10. [45] S. R. Pandey et al., “Edge-assisted democratized learning toward federated analytics,” IEEE Internet of Things Journal, vol. 9, no. 1, pp. 572–588, 2022. [46] C.-W. Ching, X. Chen, C. Kim, T. Wang, D. Chen, D. Da Silva, and L. Hu, “Agiledart: An agile and scalable edge stream processing engine,” IEEE Transactions on Mobile Computing, 2025. [47] Z. Fu, J. Ren, D. Zhang, Y. Zhou, and Y. Zhang, “Kalmia: A heterogeneous qos-aware scheduling framework for dnn tasks on edge servers,” in Conference on Computer Communications, 2022, pp. 780– 789. [48] Q. Cui, Z. Xiong, M. Fazel, and S. S. Du, “Learning in congestion games with bandit feedback,” Advances in Neural Information Processing Systems, vol. 35, pp. 11 009–11 022, 2022. [49] A. Rowstron and P. Druschel, “Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems,” in IFIP/ACM International Conference on Distributed Systems Platforms. Springer, 2001, pp. 329–350. [50] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, “Chord: A scalable peer-to-peer lookup service for internet applications,” ACM SIGCOMM computer communication review, vol. 31, no. 4, pp. 149–160, 2001. [51] B. Zhao, L. Huang, J. Stribling, S. Rhea, A. Joseph, and J. Kubiatowicz, “Tapestry: a resilient global-scale overlay for service deployment,” IEEE Journal on Selected Areas in Communications, vol. 22, no. 1, pp. 41–53, 2004. [52] Y. Chen, X. Qin, J. Wang, C. Yu, and W. Gao, “Fedhealth: A federated transfer learning framework for wearable healthcare,” IEEE Intelligent Systems, vol. 35, no. 4, pp. 83–93, 2020. [53] D. Y. Zhang, Z. Kou, and D. Wang, “Fedsens: A federated learning approach for smart health sensing with class imbalance in resource constrained edge computing,” in IEEE Conference on Computer Communications, 2021, pp. 1–10. [54] P. Maymounkov and D. Mazieres, “Kademlia: A peer-to-peer information system based on the xor metric,” in International workshop on peer-to-peer systems. Springer, 2002, pp. 53–65. [55] S. Ratnasamy, M. Handley, R. Karp, and S. Shenker, “Topologically-aware overlay construction and server selection,” in Proceedings.Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, 2002, pp. 1190–1199 vol.3. [56] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, “Federated optimization in heterogeneous networks,” Proceedings of Machine learning and systems, vol. 2, pp. 429–450, 2020. [57] R. C. Geyer, T. Klein, and M. Nabi, “Differentially private federated learning: A client level perspective,” in Advances in Neural Information Processing Systems Workshop: Machine Learning on the Phone and other Consumer Devices, 2017. [58] C. Zhang, S. Li, J. Xia, W. Wang, F. Yan, and Y. Liu, “BatchCrypt: Efficient homomorphic encryption for Cross-Silo federated learning,” in USENIX annual technical conference, 2020, pp. 493–506. [59] C. Wang, S. Zhang, Y. Chen, Z. Qian, J. Wu, and M. Xiao, “Joint configuration adaptation and bandwidth allocation for edge-based real-time video analytics,” in IEEE Conference on Computer Communications, 2020, pp. 257–266.
[60] M. S. Talebi, Z. Zou, R. Combes, A. Proutiere, and M. Johansson, “Stochastic online shortest path routing: The value of feedback,” IEEE Transactions on Automatic Control, vol. 63, no. 4, pp. 915–930, 2018. [61] S. Bubeck et al., “Regret analysis of stochastic and nonstochastic multi-armed bandit problems,” Foundations and Trends® in Machine Learning, vol. 5, no. 1, pp. 1–122, 2012. [62] T. Roughgarden, “Algorithmic game theory,” Communications of the ACM, vol. 53, no. 7, pp. 78–86, 2010. [63] D. Ding, C.-Y. Wei, K. Zhang, and M. Jovanovic, “Independent policy gradient for large-scale Markov potential games: Sharper rates, function approximation, and game-agnostic convergence,” in International Conference on Machine Learning. PMLR, 2022, pp. 5166–5220. [64] J. W. Crandall and M. A. Goodrich, “Learning to compete, compromise, and cooperate in repeated general-sum games,” in Proceedings of the 22nd International Conference on Machine Learning, 2005, p. 161–168. [Online]. Available: https://doi.org/10. 1145/1102351.1102372 [65] B. Hambly, R. Xu, and H. Yang, “Policy gradient methods find the nash equilibrium in n-player general-sum linear-quadratic games,” Journal of Machine Learning Research, vol. 24, no. 139, pp. 1–56, 2023. [Online]. Available: http://jmlr.org/papers/v24/21-0842.html [66] T. Lattimore and C. Szepesvári, Bandit algorithms. Cambridge University Press, 2020. [67] Z. Wen, B. Kveton, M. Valko, and S. Vaswani, “Online influence maximization under independent cascade model with semi-bandit feedback,” Advances in neural information processing systems, vol. 30, 2017. [68] M. Frank et al., “An algorithm for quadratic programming,” Naval research logistics quarterly, vol. 3, no. 1-2, pp. 95–110, 1956. [69] PyTorch. https://pytorch.org/. [70] M. Castro, P. Druschel, A.-M. Kermarrec, and A. Rowstron, “Scribe: a large-scale and decentralized application-level multicast infrastructure,” IEEE Journal on Selected Areas in Communications, vol. 20, no. 8, pp. 1489–1499, 2002. [71] torchvision. https://docs.pytorch.org/vision/stable/index.html. [72] Hugging Face Transformers. https://huggingface.co/docs/transformers/ en/index. [73] P. Lai et al., “Optimal edge user allocation in edge computing with variable sized vector bin packing,” in 16th International Conference on Service-Oriented Computing. Springer, 2018, pp. 230–245. [74] “Symbiotic lab,” https://symbioticlab.org/. [75] P. Warden, “Speech commands: A dataset for limited-vocabulary speech recognition,” arXiv preprint arXiv:1804.03209, 2018. [76] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, June 2016. [77] N. Ma, X. Zhang, H.-T. Zheng, and J. Sun, “ShuffleNet V2: Practical guidelines for efficient cnn architecture design,” in Proceedings of the European Conference on Computer Vision, September 2018. [78] B. Zhang, X. Jin, S. Ratnasamy, J. Wawrzynek, and E. A. Lee, “AWStream: Adaptive wide-area streaming analytics,” in Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, 2018, pp. 236–252. [79] Z. Chai, Y. Chen, A. Anwar, L. Zhao, Y. Cheng, and H. Rangwala, “FedAT: A high-performance and communication-efficient federated learning system with asynchronous tiers,” in Proceedings of the international conference for high performance computing, networking, storage and analysis, 2021, pp. 1–16. [80] C. Li, X. Zeng, M. Zhang, and Z. Cao, “PyramidFL: A fine-grained client selection framework for efficient federated learning,” in Proceedings of the 28th Annual International Conference on Mobile Computing And Networking, 2022, pp. 158–171. [81] D. Cai, Y. Wu, S. Wang, F. X. Lin, and M. Xu, “Efficient federated learning for modern NLP,” in Proceedings of the 29th Annual International Conference on Mobile Computing and Networking, 2023, pp. 1–16. [82] D. Cai, S. Wang, Y. Wu, F. X. Lin, and M. Xu, “Federated fewshot learning for mobile NLP,” in Proceedings of the 29th Annual International Conference on Mobile Computing and Networking, 2023, pp. 1–17. [83] C.-W. Ching, J.-M. Chang, J.-J. Kuo, and C.-Y. Wang, “Dual-objective personalized federated service system with partially-labeled data over wireless networks,” IEEE Transactions on Services Computing, vol. 16, no. 5, pp. 3265–3279, 2023. [84] L. Liu, J. Zhang, S. Song, and K. B. Letaief, “Client-edge-cloud hierarchical federated learning,” in IEEE International Conference on Communications, 2020, pp. 1–6.
18
[85] Q. Wu et al., “HiFlash: Communication-efficient hierarchical federated learning with adaptive staleness control and heterogeneity-aware clientedge association,” IEEE Transactions on Parallel and Distributed Systems, vol. 34, no. 5, pp. 1560–1579, 2023. [86] T. Qi, Y. Zhan, P. Li, J. Guo, and Y. Xia, “Hwamei: A learning-based synchronization scheme for hierarchical federated learning,” in IEEE 43rd International Conference on Distributed Computing Systems, 2023, pp. 534–544. [87] Y. Deng et al., “A communication-efficient hierarchical federated learning framework via shaping data distribution at edge,” IEEE/ACM Transactions on Networking, vol. 32, no. 3, pp. 2600–2615, 2024. [88] Q. Ma, Y. Xu, H. Xu, J. Liu, and L. Huang, “FedUC: A unified clustering approach for hierarchical federated learning,” IEEE Transactions on Mobile Computing, vol. 23, no. 10, pp. 9737–9756, 2024. [89] Y. Guo, F. Liu, T. Zhou, Z. Cai, and N. Xiao, “Privacy vs. efficiency: Achieving both through adaptive hierarchical federated learning,” IEEE Transactions on Parallel and Distributed Systems, vol. 34, no. 4, pp. 1331–1342, 2023. [90] H. Tang, X. Lian, M. Yan, C. Zhang, and J. Liu, “D2 : Decentralized training over decentralized data,” in International Conference on Machine Learning. PMLR, 2018, pp. 4848–4856. [91] A. G. Roy, S. Siddiqui, S. Pölsterl, N. Navab, and C. Wachinger, “BrainTorrent: A peer-to-peer environment for decentralized federated learning,” arXiv preprint arXiv:1905.06731, 2019. [92] A. Lalitha, S. Shekhar, T. Javidi, and F. Koushanfar, “Fully decentralized federated learning,” in Third workshop on bayesian deep learning, vol. 2, 2018. [93] Z. Yang and W. U. Bajwa, “ByRDiE: Byzantine-resilient distributed coordinate descent for decentralized learning,” IEEE Transactions on Signal and Information Processing over Networks, vol. 5, no. 4, pp. 611–627, 2019. [94] C. Fang, Z. Yang, and W. U. Bajwa, “BRIDGE: Byzantine-resilient decentralized gradient descent,” IEEE Transactions on Signal and Information Processing over Networks, vol. 8, pp. 610–626, 2022. [95] N. Gupta and N. H. Vaidya, “Byzantine fault-tolerance in peer-to-peer distributed gradient-descent,” arXiv preprint arXiv:2101.12316, 2021. [96] A. Bellet, R. Guerraoui, M. Taziki, and M. Tommasi, “Personalized and private peer-to-peer machine learning,” in International Conference on Artificial Intelligence and Statistics. PMLR, 2018, pp. 473–481. [97] P. Vanhaesebrouck, A. Bellet, and M. Tommasi, “Decentralized collaborative learning of personalized models over networks,” in Artificial Intelligence and Statistics. PMLR, 2017, pp. 509–517. [98] Y. Liao, Y. Xu, H. Xu, M. Chen, L. Wang, and C. Qiao, “Asynchronous decentralized federated learning for heterogeneous devices,” IEEE/ACM Transactions on Networking, vol. 32, no. 5, pp. 4535–4550, 2024. [99] J. Liu, J. Liu, H. Xu, Y. Liao, Z. Wang, and Q. Ma, “YOGA: Adaptive layer-wise model aggregation for decentralized federated learning,” IEEE/ACM Transactions on Networking, vol. 32, no. 2, pp. 1768–1780, 2024. [100] Q. Ma, J. Liu, H. Xu, Q. Jia, and R. Xie, “FRACTAL: Data-aware clustering and communication optimization for decentralized federated learning,” IEEE Transactions on Big Data, pp. 1–16, 2024. [101] B. Soltani, V. Haghighi, Y. Zhou, Q. Z. Sheng, and L. Yao, “DFLStar: A decentralized federated learning framework with self-knowledge distillation and participant selection,” in Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, 2024, pp. 2108–2117. [102] Y. Liao, Y. Xu, H. Xu, L. Wang, C. Qian, and C. Qiao, “Decentralized federated learning with adaptive configuration for heterogeneous participants,” IEEE Transactions on Mobile Computing, vol. 23, no. 6, pp. 7453–7469, 2024. [103] K. Singhal, H. Sidahmed, Z. Garrett, S. Wu, J. Rush, and S. Prakash, “Federated reconstruction: Partially local federated learning,” Advances in Neural Information Processing Systems, vol. 34, pp. 11 220–11 232, 2021. [104] Z. Li, D. Kovalev, X. Qian, and P. Richtarik, “Acceleration for compressed gradient descent in distributed and federated optimization,” in International Conference on Machine Learning. PMLR, 2020, pp. 5895–5904. [105] S. J. Reddi et al., “Adaptive federated optimization,” in International Conference on Learning Representations, 2021. [106] A. Girgis, D. Data, S. Diggavi, P. Kairouz, and A. T. Suresh, “Shuffled model of differential privacy in federated learning,” in International Conference on Artificial Intelligence and Statistics. PMLR, 2021, pp. 2521–2529.
[107] T. Lin, S. U. Stich, K. K. Patel, and M. Jaggi, “Don’t use large minibatches, use local SGD,” in International Conference on Learning Representations, 2020. [108] J. Wang and G. Joshi, “Adaptive communication strategies to achieve the best error-runtime trade-off in local-update SGD,” Proceedings of Machine Learning and Systems, vol. 1, pp. 212–229, 2019. [109] D. Basu, D. Data, C. Karakus, and S. N. Diggavi, “Qsparse-LocalSGD: Distributed SGD with quantization, sparsification, and local computations,” IEEE Journal on Selected Areas in Information Theory, vol. 1, no. 1, pp. 217–226, 2020. [110] D. Rothchild, A. Panda, E. Ullah, N. Ivkin, I. Stoica, V. Braverman, J. Gonzalez, and R. Arora, “FetchSGD: Communication-efficient federated learning with sketching,” in International Conference on Machine Learning. PMLR, 2020, pp. 8253–8265. [111] M. S. H. Abad, E. Ozfatura, D. GUndUz, and O. Ercetin, “Hierarchical federated learning across heterogeneous cellular networks,” in IEEE International Conference on Acoustics, Speech and Signal Processing, 2020, pp. 8866–8870. [112] M. D. Corner, B. N. Levine, O. Ismail, and A. Upreti, “Advertisingbased measurement: A platform of 7 billion mobile devices,” in Proceedings of the 23rd Annual International Conference on Mobile Computing and Networking, 2017, p. 435–447. [Online]. Available: https://doi.org/10.1145/3117811.3117844 [113] Y. Xiao, J. Du, S. Zhang, W. Zhang, Q. Yan, D. Zhang, and D. Kifer, “Click without compromise: Online advertising measurement via per user differential privacy,” in IEEE Symposium on Security and Privacy (SP), 2025, pp. 2919–2937. [114] D. Monderer and L. S. Shapley, “Potential games,” Games and economic behavior, vol. 14, no. 1, pp. 124–143, 1996. [115] A. Sawarni, S. Pal, and S. Barman, “Nash regret guarantees for linear bandits,” in Advances in Neural Information Processing Systems, vol. 36. Curran Associates, Inc., 2023, pp. 33 288–33 318. [Online]. Available: https://proceedings.neurips.cc/paper files/paper/ 2023/file/69bf9fd8d3b7b792b6c8c19149024d22-Paper-Conference.pdf [116] Q. Liu, T. Yu, Y. Bai, and C. Jin, “A sharp analysis of model-based reinforcement learning with self-play,” in Proceedings of the 38th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 139. PMLR, 18–24 Jul 2021, pp. 7001–7010. [Online]. Available: https://proceedings.mlr.press/v139/ liu21z.html [117] D. Ding, C.-Y. Wei, K. Zhang, and M. Jovanovic, “Independent policy gradient for large-scale Markov potential games: Sharper rates, function approximation, and game-agnostic convergence,” in Proceedings of the 39th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 162. PMLR, 17–23 Jul 2022, pp. 5166–5220. [Online]. Available: https://proceedings.mlr.press/v162/ding22b.html [118] H. Nikaidô and K. Isoda, “Note on non-cooperative convex games,” Pacific Journal of Mathematics, 1955. [119] A. Raghunathan, A. Cherian, and D. Jha, “Game theoretic optimization via gradient-based nikaido-isoda function,” in Proceedings of the 36th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 97. PMLR, 09–15 Jun 2019, pp. 5291–5300. [Online]. Available: https: //proceedings.mlr.press/v97/raghunathan19a.html [120] D. Monderer and L. S. Shapley, “Potential games,” Games and economic behavior, vol. 14, no. 1, pp. 124–143, 1996. [121] A. Krizhevsky, G. Hinton et al., “Learning multiple layers of features from tiny images,” 2009. [122] S. Mehta and M. Rastegari, “MobileViT: Light-weight, generalpurpose, and mobile-friendly vision transformer,” in International Conference on Learning Representations, 2022. [Online]. Available: https://openreview.net/forum?id=vh-0sUt8HlG [123] J. FitzGerald, C. Hench, C. Peris, S. Mackie, K. Rottmann, A. Sanchez, A. Nash, L. Urbach, V. Kakarala, R. Singh, S. Ranganath, L. Crist, M. Britan, W. Leeuwis, G. Tur, and P. Natarajan, “MASSIVE: A 1M-example multilingual natural language understanding dataset with 51 typologically-diverse languages,” in Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for Computational Linguistics, Jul. 2023, pp. 4277–4302. [Online]. Available: https://aclanthology.org/ 2023.acl-long.235/ [124] Z. Lan, M. Chen, S. Goodman, K. Gimpel, P. Sharma, and R. Soricut, “ALBERT: A lite bert for self-supervised learning of language representations,” in International Conference on Learning Representations, 2020. [Online]. Available: https://openreview.net/ forum?id=H1eA7AEtvS
19
[125] S. M. Sajjadi Mohammadabadi, L. Yang, F. Yan, and J. Zhang, “Communication-efficient training workload balancing for decentralized multi-agent learning,” in IEEE 44th International Conference on Distributed Computing Systems (ICDCS), 2024, pp. 680–691. [126] Z. Tang, S. Shi, B. Li, and X. Chu, “GossipFL: A decentralized federated learning framework with sparsified and adaptive communication,” IEEE Transactions on Parallel and Distributed Systems, vol. 34, no. 3, pp. 909–922, 2023. [127] Z. Qin, X. Yan, M. Zhou, and S. Deng, “BlockDFL: A blockchainbased fully decentralized peer-to-peer federated learning framework,” in Proceedings of the ACM Web Conference 2024, 2024, p. 2914–2925. [Online]. Available: https://doi.org/10.1145/3589334.3645425 [128] D. Chen, D. Gao, Y. Xie, X. Pan, Z. Li, Y. Li, B. Ding, and J. Zhou, “FS-REAL: Towards real-world cross-device federated learning,” in Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023, p. 3829–3841. [Online]. Available: https://doi.org/10.1145/3580305.3599829 [129] Internet corporation for assigned names and numbers (icann). https: //www.icann.org/. [130] Verisign. https://www.verisign.com/. [131] X. Kang, G. Yu, J. Wang, W. Guo, C. Domeniconi, and J. Zhang, “Incentive-boosted federated crowdsourcing,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 5, 2023, pp. 6021–6029. [132] X. Jiang, J. Zhang, M. Wu, and V. S. Sheng, “TiFedCrowd: Federated crowdsourcing with time-controlled incentive,” IEEE Transactions on Emerging Topics in Computational Intelligence, vol. 9, no. 2, pp. 1514– 1526, 2025. [133] Y. Xu, M. Xiao, J. Wu, H. Tan, and G. Gao, “A personalized privacy preserving mechanism for crowdsourced federated learning,” IEEE Transactions on Mobile Computing, vol. 23, no. 2, pp. 1568–1585, 2024. [134] X. Xu, H. Li, Z. Li, and X. Zhou, “Safe: Synergic data filtering for federated learning in cloud-edge computing,” IEEE Transactions on Industrial Informatics, vol. 19, no. 2, pp. 1655–1665, 2023. [135] J. Li, G. Li, H. Cheng, Z. Liao, and Y. Yu, “FedDiv: Collaborative noise filtering for federated learning with noisy labels,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 38, no. 4, 2024, pp. 3118–3126. [136] X. Ji, Z. Zhu, W. Xi, O. Gadyatskaya, Z. Song, Y. Cai, and Y. Liu, “FedFixer: Mitigating heterogeneous label noise in federated learning,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 38, no. 11, 2024, pp. 12 830–12 838.
Cheng-Wei Ching received the MS degree in Computer Science and Information Engineering from National Chung Cheng University, Taiwan, in 2021. He is pursuing a PhD in Computer Science and Engineering at the University of California Santa Cruz, USA. His research interests include distributed systems for machine learning, approximation algorithms and their applications, and mobile edge computing.
Xin Chen received the BS degree in Computer Science from Shandong University, China, in 2009, the MS degree in Software Engineering from Tsinghua University, China, in 2012, and the PhD degree in Computer Science from the Georgia Institute of Technology, USA, in 2020. His research focuses on computer systems and machine learning systems, including solving path planning and collision detection problems.
Taehwan Kim received his BS from Bucknell University in 2020 and his MS from Virginia Tech in 2022. He is now a software engineer at Google, where he focuses on Gemini post-training infrastructure.
Jian-Jhih Kuo (Member, IEEE) received the B.S. and Ph.D. degrees in computer science from National Chung Cheng University (CCU), Taiwan, in 2008, and National Tsing Hua University, Taiwan, in 2014, respectively. He was a Postdoctoral Fellow in the Institute of Information Science, Academia Sinica, Taiwan. He joined the Department of Computer Science and Information Engineering, CCU, Taiwan, in 2018, where he is currently an associate professor. His research interests include computer networking, quantum networking, traffic engineering, and cloud and edge computing. He was a recipient of the Ta-You Wu Memorial Award from National Science and Technology Council (NSTC), Taiwan, in 2025, NSTC Project for Excellent Junior Research Investigators in 2022 and 2025, and CCU Young Faculty Award in 2021.
Dilma Da Silva is a Regents Professor and holder of the Ford Design Professorship II in the Department of Computer Science and Engineering at Texas A&M University. From 2022 to 2026, she served in several leadership roles at the U.S. National Science Foundation. Her primary research interests include distributed systems, high-performance computing, operating systems, computer science education, and quantum computing. Dilma received her Ph.D. in computer science from the Georgia Institute of Technology in 1997.
Liting Hu received the BS degree in Computer Science from the Huazhong University of Science and Technology, China, in 2007, and the PhD degree in Computer Science from the Georgia Institute of Technology, USA, in 2016. She conducts AI-driven experimental computer systems research in stream processing systems, cloud and edge computing, distributed systems, and systems virtualization. Currently she is an associate professor at the University of California Santa Cruz.
20
A PPENDIX A A PPLICATION A DVERTISEMENT AND D ISCOVERY IN T OTORO AND T OTORO+ Totoro’s design and limitations. In Totoro, the system does not have an independent system component for federated learning (FL) application advertisement and discovery. Instead, Totoro implicitly relies on the AppId and its DHT-based P2P overlay as a rendezvous mechanism for applications. Once an FL application is created, the node whose node ID is numerically closest to the AppId is automatically designated as the master. The system assumes that participating nodes already know the corresponding AppId of the application, and they route JOIN messages through the overlay network toward that AppId. Due to the properties of the P2P overlay, JOIN messages are eventually aggregated at the master node or any other nodes in the dynamically constructed dataflow tree, allowing nodes to participate in model dissemination or gradient aggregation. This design essentially abstracts application access and participation as a join-by-identifier mechanism, rather than providing an explicit application directory or advertisement plane. However, this design also introduces several system-level challenges. First, due to the absence of an explicit application advertisement or discovery plane, nodes cannot directly query or enumerate the FL applications currently running in the system. As a result, application existence and access rely on additional, out-of-band coordination mechanisms (e.g., a third party advertisement platform [112], [113]). Second, application-related metadata (e.g., model type, resource requirements, data constraints, or participation conditions) is not natively published or disseminated within the system, limiting the ability of nodes to perform conditional matching or application selection based on their own capabilities or environmental states. Finally, as the number of concurrently running FL applications increases, AppId dissemination and participant management increasingly depend on external control planes. In heterogeneous and highly dynamic edge environments, this dependency may further increase system management complexity and coordination overhead. Advertise-discover tree in Totoro+ . To address the above limitations in application advertisement and discovery, Totoro+ introduces an additional application management structure, namely the Advertise-Discover Tree (AD tree). In Totoro+ , when a new FL application is created, its corresponding master node immediately subscribes to a globally shared AD tree. This subscription process follows the same mechanism as a standard FL application dataflow tree. After joining the AD tree, the new master uploads the AppId and associated metadata of the FL application it manages to the AD tree. At the same time, the master receives broadcast messages from the AD tree containing the AppIds and corresponding information of all FL applications currently running in the overlay. Following this mechanism, the AD tree forms a distributed and scalable application directory that continuously maintains and updates application-level state within the overlay network. When a new node joins the Totoro+ overlay network and wants to explore which FL applications are currently available,
it only needs to subscribe to the AD tree to obtain the list of active applications along with their descriptive metadata. Based on the AppIds obtained from the AD tree, the node can then subscribe to the corresponding FL application dataflow tree and participate in training. By explicitly abstracting application advertisement and discovery as an independent dataflow tree, Totoro+ provides native application visibility and dynamic exploration capabilities while preserving decentralization. Moreover, the additional overhead introduced by the AD tree is negligible, as only the masters of FL application dataflow trees need to subscribe to the AD tree, and newly joined nodes can unsubscribe after identifying the desired FL application.
A PPENDIX B BANDIT-BASED M ODEL V. S . G AME -T HEORETIC M ODEL We compare the mathematical models adopted in Totoro+ (game-theoretic) and Totoro (bandit-based) formulations in this section. The comparison is conducted along five dimensions: decision maker, reward mechanism, source of uncertainty, optimization objective, and optimal solution. Decision maker. In the bandit-based model, each node is modeled as an independent learner. In each round, a node selects a single action, namely choosing one path pk ∈ P from the set of all possible paths P. The decision made by one node does not affect the decisions of other nodes, as nodes are unaware of each other’s existence. Moreover, the model does not consider interference or competition effects when multiple nodes select the same path. Using a casino analogy, each node corresponds to an independent player, and each action represents choosing a slot machine to play. Although multiple players may be selecting and playing slot machines simultaneously, they are assumed to be unaware of one another, and the payoff of a slot machine does not change despite being played by multiple players (e.g., jackpots or missed pulls). In contrast, the game-theoretic model jointly considers the simultaneous path selection decisions of N nodes. Q The action N space expands from P to the Cartesian product n=1 Pn , representing all possible combinations of paths chosen by the N nodes. Accordingly, the action in each round is no longer a single path pk , but a vector p = (p1 , · · · , pN ), which captures the paths selected by all nodes. Under the casino analogy, this corresponds to a setting where N players are simultaneously present in the casino. Each player chooses a slot machine to play, while being aware of the presence of other players. Each player therefore considers whether a slot machine remains worthwhile after it has been played by others, or whether switching to a different machine would yield a better payoff. From the perspective of decision making, the game-theoretic formulation more closely reflects practical networking scenarios. In particular, when multiple nodes select the same path, the effective performance of that path may degrade due to shared transmission resources (e.g., under bandwidth-sharing assumptions), a phenomenon that is naturally captured in the game-theoretic model but ignored in the bandit formulation.
21
Reward mechanism. In the bandit-based model, the reward is defined as the path delay, X 1 Dθ = xi · , θi i∈E
where xi indicates whether link i is included in a selected path, and θi denotes the success probability of link i. Under this formulation, although θi is unknown, it can be learned from historical observations. Importantly, the reward associated with a path is independent of the actions of other nodes. The model does not account for performance degradation when multiple nodes select the same link, as the environment is assumed to be stationary and exogenous. In contrast, the game-theoretic model defines the mean reward of node n as pn
pn
rn (p) = r (n (p), θpn ) after selecting path pn , where θpn represents the quality of path pn , and the reward explicitly depends on the number of nodes selecting the same path, denoted by npn (p). As a result, the reward is endogenous and jointly determined by the collective actions of all nodes. From the perspective of reward mechanisms, the game-theoretic formulation better reflects practical networking environments. When a path is utilized by multiple nodes, the reward should decrease due to reduced transmission efficiency and increased delay caused by shared resources. This congestion effect is naturally captured in the game-theoretic model but ignored in the bandit-based model. Uncertainty source. In the bandit-based model, uncertainty primarily arises from the unknown environmental parameters. Specifically, the success probability θi of each link i ∈ E is modeled as an unknown but fixed random but i.i.d parameter that remains unchanged throughout the routing process. Although θi is unknown a priori, it can be gradually estimated and learned from historical transmission outcomes. Consequently, the uncertainty in the bandit-based model is statistical uncertainty, which stems from estimation errors of random environmental parameters rather than from the behavior of other nodes. Since the reward (or delay) depends solely on the selected path and its underlying link success rates, the environment is assumed to be stationary and exogenous, and is not affected by the decisions of other nodes. In contrast, in the game-theoretic model, uncertainty does not arise solely from the unknown path quality θp , but more fundamentally from the strategic choices of other nodes. As the reward obtained by node n, rn (p) = rpn (npn (p), θpn ), explicitly depends on the joint action p = (p1 , · · · , pN ), a single node cannot determine its realized reward without considering the actions of other nodes, even if θpn is known. In other words, each node faces strategic uncertainty, which arises from the decisions of other rational nodes operating on the same time scale, rather than from an independently learnable random environment. From the perspective of uncertainty sources, the bandit-based model focuses on how to learn in a fixed and exogenous stochastic environment,
whereas the game-theoretic model characterizes how to cope with uncertainty induced by strategic interactions among multiple nodes. In addition to unknown path qualities, the latter must account for the actions of other nodes, and thus more accurately reflects the dynamics and uncertainty of practical edge routing scenarios, where multiple nodes simultaneously compete for limited network resources. Optimization objective. In the bandit-based model, the routing problem is formulated as an online learning problem, whose optimization objective is to minimize the cumulative regret with respect to a fixed optimal path. Specifically, the bandit-based model defines the regret at time K as " K # X π π R (K) = E D (k) − KDθ (p∗ ), k=1 ∗
where p ∈ arg minp∈P Dθ (p) denotes the single path with the minimum expected delay under the true but unknown environment parameter θ. This objective reflects the central concern of the bandit-based model: in a stationary and exogenous environment, how to gradually learn and approach a fixed optimal path with minimal exploration cost. Accordingly, regret measures the additional delay incurred during the learning process due to incomplete information, and fundamentally serves as an indicator of learning efficiency. In contrast, in the game-theoretic model, the optimization objective is not defined relative to a static optimal path, but is instead evaluated using Nash regret. The model focuses on whether, under simultaneous path selection by multiple nodes, any node has an incentive to unilaterally deviate from the currently adopted joint policy. The objective function at time T is defined as Nash-Regret(T ) =
T X t=1
t π + ,π−n
max (Vn n
n∈[N ]
t
− Vnπ ),
where πn+ denotes the best-response policy of node n given t that the strategies of all other nodes are fixed, π−n represents the marginal joint policy of nodes 1, · · · , n − 1, n + 1, · · · , N at time t, and Vnπ represents the value of policy π for node n. This objective captures strategy stability, rather than the learning of a globally shortest path. When the Nash regret is sufficiently small, no individual node can significantly improve its expected reward through unilateral strategy deviation. Therefore, from the perspective of optimization objectives, the bandit-based model aims to rapidly identify a fixed optimal action, whereas the game-theoretic model emphasizes suppressing incentives for deviation and promoting stability in strategic interactions. The corresponding regret definitions, comparison baselines, and performance interpretations of the two models thus differ in a fundamental manner. Optimal solution. In the bandit-based model, the notion of an optimal solution does not correspond to a static strategy equilibrium, but rather to a learning policy π that guarantees sublinear regret. The optimality of such a policy is evaluated by whether, as K increases, Rπ (K) → 0, K which ensures that the system’s average latency converges
22
to the latency of the optimal path p∗ in the long run. In other words, the optimal solution in the bandit-based model emphasizes learning dynamics and convergence speed, and assumes that once the environment parameters are sufficiently learned, the system behavior eventually concentrates on a single optimal path. In contrast, in the game-theoretic model, the concept of an optimal solution is closely tied to equilibrium. The objective is not to identify a single path that is globally optimal for all nodes, but to learn a joint policy π ∗ under which no node can achieve a significant gain by unilaterally changing its strategy. When the Nash regret converges to zero, the resulting solution can be interpreted as an approximate Nash equilibrium or a coarse correlated equilibrium. Such solutions reflect a stable operating state under multi-node competition and resource sharing, rather than the minimization of a single performance metric. Therefore, from the perspective of optimal solutions, the bandit-based model focuses on how to efficiently learn a globally optimal behavior, whereas the game-theoretic model focuses on whether the system can reach a stable strategy profile with no incentive for unilateral deviation under strategic coupling and competition. The former prioritizes learning efficiency and asymptotic performance, while the latter places greater emphasis on system-level stability and fairness. As a result, the game-theoretic formulation is better suited to path selection in edge environments with limited resources and multiple competing nodes. A PPENDIX C P RELIMINARIES ON G AMES This section presents the game-theoretic preliminaries that form the foundation of the mathematical modeling and algorithmic design of Totoro+ . The problem studied in this work involves multiple nodes making decentralized routing decisions under shared resource constraints, where the reward obtained by each node depends on both its own action and the collective behavior of other nodes. Such interactions are naturally captured by game-theoretic models, especially in settings with incomplete information and limited feedback. We first introduce general-sum matrix games [64], [65] as a general framework for modeling multi-agent decision-making with possibly misaligned objectives. We then introduce the notion of general policies for these games [48], [114]. Within this framework, we review equilibrium notions and performance metrics, including Nash equilibrium and Nash regret [115], [116], which are central to the analysis of learning dynamics in repeated games. We then discuss potential games [114] and congestion games [48], which impose additional structure on general-sum games and allow us to explicitly model performance degradation due to resource contention. Finally, we describe different types of feedback available to agents in congestion games, distinguishing between semi-bandit and bandit feedback. In this work, we focus on the bandit feedback setting, which reflects realistic communication constraints and directly motivates the learning algorithms developed for Totoro+ . General-sum matrix games [64], [65]. We study the framework of general-sum matrix games, which is specified by the
tuple G = ({Ai }m i=1 , R), where m denotes the number of players, Ai is the action space of player i, and R(· | a) represents a reward distribution supported on [0, rmax ]m with mean r(a). Let A = A1 × · · · × Am denote the joint action space, and let a = (a1 , . . . , am ) ∈ A be a joint action profile. Once all players select actions a ∈ A, a reward vector is drawn according to r ∼ R(· | a), and player i receives a reward ri ∈ [0, rmax ] with expectation ri (a). Each player aims to maximize her own expected reward. General policy [48], [114]. A general policy π is defined as a probability distribution in ∆(A), the simplex over the joint action space A. A product policy π = (π1 , . . . , πm ) corresponds to an element of ∆(A1 ) × · · · × ∆(Am ), under which a = (a1 , . . . , am ) ∼ π indicates that each ai is i.i.d. independently sampled according to ai ∼ πi . The value of a policy π for player i is defined as Viπ = Ea∼π [ri (a)]. Nash equilibrium and Nash regret [115], [116]. Given a general policy π, let π−i denote the marginal joint policy of all players except player i. The best response of player i to policy π is given by µ,π−i
πi† = arg max Vi
,
µ∈∆(Ai )
π † ,π
†,π
with the corresponding value Vi −i := Vi i −i . Our objective is to characterize approximate Nash equilibria of the matrix game, defined as follows. Definition 1. A product policy π is an ϵ-approximate Nash †,π equilibrium if maxi Vi −i − Viπ ≤ ϵ. An ϵ-approximate Nash equilibrium can be achieved by ensuring sublinear growth of the Nash regret, which we define below. For a more comprehensive discussion, see Section 3 in Ding et al. [117]. Definition 2. With π k denoting the policy at the k-th episode, the Nash regret after K episodes is defined as K X k †,π k Nash-Regret(K) = max Vi −i − Viπ . k=1
i∈[m]
Remark 1. If i∈[m] in the definition of Nash regret is Pmax m , replaced by i=1 the resulting single-step Nash regret at episode k reduces to the Nikaidô–Isoda function evaluated at π k , which is a widely used objective for equilibrium computation [118], [119]. Such a replacement increases the regret bounds by a factor of m, but does not affect our main conclusions. Potential games [114]. A potential game is a class of general-sum games for which there exists a potential function Φ : ∆(A) → [0, Φmax ] such that, for any player i ∈ [m] and any policies πi , πi′ , π−i , the following condition holds: π ,π−i
Φ(πi , π−i ) − Φ(πi′ , π−i ) = Vi i
π ′ ,π−i
− Vi i
.
It follows directly that any policy maximizing the potential function constitutes a Nash equilibrium. Congestion games [48]. A congestion game models competitive interactions over shared resources whose performance degrades as the level of simultaneous usage increases. Formally,
23
f the game is specified by G = (F, {Ai }m i=1 , {R }f ∈F ), where f F = [F ] denotes the set of facilities, and R (· | n) ∈ [0, 1] is the reward distribution associated with facility f when it is used by n ∈ [m] players, with mean reward rf (n). Each player i selects an action ai ∈ Ai , where an action corresponds to a subset of facilities, i.e., ai ⊆ F. Given a joint action profile a ∈ A selected by all players, f each facility f generates a random Pmreward according to r ∼ Rf (· | nf (a)), where nf (a) = i=1 1{f ∈ ai } denotes the number of players concurrently utilizing facility f . The total reward obtained by player i isPthe aggregate reward over all facilities included in ai , ri = f ∈ai rf , with expected value P ri (a) = f ∈ai rf (nf (a)) ∈ [0, F ]. Connection to potential games [114]. Congestion games constitute a special class of potential games in which individual incentives are aligned with a global objective. Specifically, P Pnf (a) they admit the potential function Φ(a) = f ∈F i=1 rf (i). This potential captures the cumulative impact of congestion on each facility. For any player i, a unilateral deviation from ai to a′i while holding a−i fixed leads to a change in the potential that exactly matches the corresponding change in the player’s reward:
Φ(ai , a−i ) − Φ(a′i , a−i ) = ri (ai , a−i ) − ri (a′i , a−i ). Extending the definition to mixed strategies, we define
Notation N P p ∈ [P ] Pn θp Rp (· | k, θp ) rp (k, θp ) p = (p1 , . . . , pN ) pn np (p) rn (p) πn ∆(Pn ) π = (π1 , . . . , πN ) π−n
Φ(π) = Ea∼π [Φ(a)].
Vnπ
As a consequence, for any unilateral policy deviation of player i, we have
πn+
π ,π−i
Φ(πi , π−i ) − Φ(πi′ , π−i ) = Vi i
π ′ ,π−i
− Vi i
.
This connection will be instrumental in our subsequent analysis of learning dynamics under bandit feedback. Types of feedback. In congestion games, the reward information available to each player can take one of two standard forms: semi-bandit feedback or bandit feedback, depending on the level of observability in the model. Under semi-bandit feedback, after selecting an action, player i observes the reward rf associated with each facility f ∈ ai . In contrast, under bandit feedback, after taking P the action, player i only observes the aggregated reward ri = f ∈ai rf without access to the individual components rf . In this work, we focus on the bandit feedback setting as it captures more realistic operating conditions in practical scenarios, where fine-grained information about the contribution or delay of each individual component is typically unavailable. In particular, in Totoro+ , a node can usually observe only the overall end-to-end transmission time or aggregate performance of a selected path, rather than the latency or success rate incurred at each intermediate resource. Accordingly, we adopt the bandit feedback setting, which reflects such practical constraints.
A PPENDIX D N OTATION TABLE Mathematical notations that will be introduced and used multiple times in this paper are summarized in Table V.
T τ Nash-Regret(T ) α β ρkn ψ(p) M (·) b kn Φ ∇
Explanation Number of nodes in the dataflow tree Total number of available paths to the root A routing path in P Set of available paths for node n Mean success rate of path p Reward distribution of path p when k nodes select it Mean reward of path p given k nodes select it Joint path selection of all nodes Path selected by node n Number of nodes selecting path p under joint action p Reward received by node n under joint action p Mixed policy of node n over paths Pn Probability simplex over Pn Joint policy of all nodes Joint policy of all nodes except node n Expected reward (value) of node n under policy π Best-response policy of node n given π−n Total number of packets transmitted Number of packets for exploration per episode Cumulative Nash regret over T packets Mixing parameter between exploitation and exploration Step size for the Frank–Wolfe update Exploratory policy of node n at episode k Feature vector associated with path p Policy correlation matrix Estimated gradient of the potential function for node n at episode k
TABLE V: Summary of notations. A PPENDIX E N UMERICAL E XAMPLE OF A LGORITHM 1 This appendix gives a numerical example of Algorithm 1. Suppose 4 leaf nodes (l1 , l2 , l3 , l4 ) run Algorithm 1 to select the next hops for forwarding model updates, and 2 intermediate nodes (m1 , m2 ) are available for selection (Figure 20). Let α = 0.5, β = 0.5, and τ = 2. We use node l1 to walk through
24
Intermediate nodes
ଵ
ଶ
Forwarding packets Leaf nodes
ଵ
ଶ
ଷ
ସ
Fig. 20: Example of a dataflow tree. Algorithm 1. First, node l1 follows its initial policy πl11 to select the next hops and collect rewards rn1,t . Since there are two candidates for node l1 to forward its packets, initial policy πl11 should be a 2-dimensional vector with the summation of its entries being 1. For example, if πl11 = [0.5, 0.5], the chance of selecting either intermediate node is 50%. Suppose node l1 forwards two packets to two intermediate nodes m1 and m2 each once, where the first packet goes to m1 1,2 (i.e., p1,1 l1 = m1 ) and the second goes to m2 (i.e., pl1 = m2 ), 1,1 1,2 and the corresponding rewards rl1 = 0.4 and rl1 = 0.8. Since τ = 2, node l1 updates its policy after forwarding two packets. Since node l1 has two candidates for packet forwarding, Pl1 = {m1 , m2 }, and ∆(Pl1 ) is a set that includes some feasible policies derived from Pl1 . Let " # 0.6 0.5 0.3 0.1 ∆(Pl1 ) = , , , , 0.4 0.5 0.7 0.9 where [0.6, 0.4] represents a policy that has 0.6 of chance to select m1 and 0.4 of chance to select m2 . For a policy λ = [0.6, 0.4], the correlation matrix M (λ) is ⊤ ⊤ 1 1 0 0 M (λ) = 0.6 · · + 0.4 · · 0 0 1 1 0.6 0 = . 0 0.4 And its determinant det(M (λ)) = 0.6 × 0.4 = 0.24. Similarly, the determinants of other policies are 0.25, 0.21, and 0.09. By line 5, we know that ρ1l1 = [0.1, 0.9]. b 1 Φ(p), we have To estimate gradient ∇ l1
⊤ ⊤ #−1 1 1 0 0 1 −1 M (πln ) = 0.5 · · + 0.5 · · 0 0 1 1 −1 0.5 0 2 0 . = = 0 0.5 0 2 "
Next, by line 6, we have ⊤ 2 0 1 b 1 Φ(m1 ) = 1 ( 1 ∇ 0.4) l1 0 2 0 2 0 ⊤ 1 1 2 0 0 + ( 0.8) 0 2 1 2 0 = 0.4. ⊤ 2 b 1l Φ(m2 ) = 1 ( 0 ∇ 1 0 2 1
0 1 0.4) 2 0
⊤ 1 0 2 0 0 + ( 0.8) 0 2 1 2 1 = 0.8. " # b 1 Φ(m1 ) ∇ 0.4 1 l1 b ∇l1 Φ = b 1 = . 0.8 ∇l1 Φ(m2 ) Next, by line 7, the inner products of each policy in ∆(Pl1 ) b 1 Φ are 0.56, 0.60, 0.68, and 0.76, and the optimal and ∇ l1 b1 Φ policy π̃l21 should be [0.1, 0.9] as its inner product with ∇ l1 is maximum. Lastly, by line 8, we have πl21 = α πl11 + β(π̃l21 − πl11 ) + (1 − α)ρ1l1 | {z } | {z } Frank-Wolfe update
Exploration
" !# 0.5 0.1 0.5 0.1 = 0.5 + 0.5 − + 0.5 0.5 0.9 0.5 0.9 0.2 = . 0.8 In the next episode, node l1 follows policy πl21 to choose the next hops and collect rewards to update the policy. Other nodes follow the same process to update their policies in parallel. Also, if the packets intermediate nodes m1 and m2 receive have not reached their destinations, m1 and m2 follow the same process to forward the packets and update their policies in parallel. A PPENDIX F O BSERVING L OCAL C ONGESTION IN T OTORO+ Observing local congestion at the network layer indeed requires support from lower-level instrumentation or third-party mechanisms. However, Totoro+ is designed as an applicationlayer system, and therefore congestion at a node is inferred based on application-level latency, rather than network-layer indicators such as packet queues or link-level congestion metrics. Specifically, the overlay constructed by Totoro+ operates at the application layer and forms a logical topology, while actual data transmission is carried out over the underlying physical network topology. In Totoro+ , congestion at an overlay node reflects a combination of physical network congestion and application-level task congestion. From a system design perspective, these effects can be jointly captured using end-toend latency measurements, without requiring explicit knowledge of physical network congestion states. As an illustrative example, a node in Totoro+ may correspond to a drone, while another overlay node (e.g., a mobile phone) transmits application-level packets supported by Totoro+ . The congestion of interest in Totoro+ is characterized by the response latency observed at the drone when handling these applicationlevel requests, rather than by the underlying network transmission congestion itself. Therefore, although Totoro+ abstracts away low-level congestion details, this abstraction remains practically meaningful for application-layer decision making. A PPENDIX G I MPLEMENTATION D ETAILS OF A LGORITHM 1 Latency uncertainty. In our implementation, the instantaneous reward is derived from the observed end-to-end latency
& X P X O & X P X O D W L D Y W H L Y 3 H D F N H W 3 D F N H W / D W / H D W Q F \ H Q F \ V V
25
7 R W R U R α = 0.9 7 R W R U R τ = 30
7 R W R U R α = 0.5 7 R W R U R τ = 300
7 R W R U R α = 0.1 7 R W R U R τ = 3000
$ Y H U D J H 3 D F N H W / D W H Q F \ P V
& X P X O D W L Y H 3 D F N H W V 6 H Q W ×10 3
& X P X O D W L Y H 3 D F N H W / D W H Q F \ V
& X P X O D W L Y H 3 D F N H W / D W H Q F \ V
$ Y H U D J H 3 D F N H W / D W H Q F \ P V
( S L V R G H ( S L V R G H Fig. 21: Average packet laFig. 22: Average packet la α. tency with different different tency with τ. ( S L V R G H ( S L R U R V R G H τ = 300 7 R W R U R τ = 3000 7 R W R U R τ = 30 7 R W ( S L V R G H ( S L V R G H Fig. 24: Cumulative packet Fig. 23: Cumulative packet latency with different τ . sent with different τ . of packet transmission. Since ( S L V R G Hlatency is a continuous-valued
metric and may exhibit large variance across different network conditions, we normalize it into a bounded reward signal to stabilize the learning process. In addition, the end-to-end latency experienced by a packet is inherently affected by the joint routing decisions of multiple nodes: when multiple nodes simultaneously select the same next-hop node, increased contention and queuing effects can lead to higher latency. As a result, the observed latency naturally reflects both stochastic network conditions and the interaction among distributed routing decisions. Specifically, given an observed latency value l, we map it into the interval [0, 1] as r =1−
l lmax
,
where lmax denotes the maximum latency observed or a predefined upper bound within the corresponding evaluation window. Under this mapping, lower latency yields higher reward, while larger latency is penalized proportionally. This normalization ensures a consistent reward scale across episodes and prevents extreme latency values from dominating the gradient estimation. Fluctuating bandwidth. Network bandwidth conditions may vary over time due to congestion, background traffic, or dynamic network environments. Totoro+ naturally captures such dynamics through its episodic learning structure. At the beginning of each episode, rewards are re-sampled based on the current network conditions, implicitly reflecting any changes in available bandwidth. Consequently, when bandwidth fluctuates, the reward observations in subsequent episodes change accordingly, and nodes adapt their routing
policies by updating local gradient estimates and re-optimizing hop-selection probabilities. This design allows Totoro+ to operate effectively in non-stationary environments without requiring explicit bandwidth prediction or manual reconfiguration. To evaluate the robustness of Totoro+ under bandwidth fluctuations, we conduct the following experiments. Specifically, the bandwidth of each node is randomly perturbed every ten episodes, with possible increases or decreases. We examine the impact of different values of the parameters α (Figure 21) and τ (Figure 22) on the average packet latency in a routing scenario with 100 nodes. For a fair comparison, we focus exclusively on the latency observed after the sampling phase. Figure 21 shows that smaller values of α result in higher average packet latency. This is because a smaller α encourages exploration toward less familiar nodes, leading to slower convergence after environmental changes; nevertheless, the latency still gradually converges to a lower level over time. Figure 22 illustrates the effect of varying the number of sampled rewards on latency. The results indicate that an appropriate number of reward samples enables faster latency reduction, as excessive exploration or insufficient exploration can lead to overconfidence or underconfidence in path selection, respectively. Transmission overhead. Totoro+ is designed to limit the communication overhead incurred during learning. Each node performs reward sampling only at the beginning of an episode, and policy updates are based on at most τ packet transmissions within that episode. After reward sampling, each node updates its local routing policy solely based on its own observed rewards, without requiring any additional message passing or coordination with other nodes. As a result, the total number of packets generated by each node per episode is upperbounded by τ , independent of the network size or the number of available routing options. This bounded sampling strategy enables a controllable trade-off between learning accuracy and communication cost: larger τ provides more accurate gradient estimates at the cost of higher transmission overhead, while smaller τ reduces communication cost but increases estimation variance. To study how τ affects routing performance, we conduct routing experiments with 100 nodes under different values of τ . For a fair comparison, we focus exclusively on the latency observed after the sampling phase. Under the cumulative packet latency metric (Figure 23), larger values of τ clearly achieve lower overall latency, since sufficient exploration allows nodes to make more informed routing decisions. However, under the cumulative number of packets sent metric (Figure 24), overly large values of τ lead to a higher total number of transmitted packets, prolonging the sampling phase. Therefore, achieving a balance between the overhead incurred during the sampling phase and the final routing performance remains an important and nontrivial design consideration. Time complexity. The time complexity of Totoro+ is formally analyzed in Theorem 2, with the detailed proof provided in Appendix J. In Section VII-E, we further compare the empirical running time of Totoro+ against the baseline Totoro algorithm and provide a breakdown of the time spent in different stages of the algorithm to illustrate how the algorithmic
26
components introduced in Algorithm 1 contribute to the overall runtime.
A PPENDIX H P ROOF OF T HEOREM 1 Lemma 1. Suppose Algorithm 1 runs K episode. For any episode k ∈ [K], n ∈ [N ] and p ∈ Pn , we have c1 b k Φ(p)| ≤ |∇ , n (1 − α) where c1 is a constant. Proof. As πnk = α πnk + β(π̃nk+1 − πnk ) + (1 − α)ρkn , we have X M (πnk ) = πnk (p)ψ(p)ψ(p)⊤ k p∈πn
⪰ (1 − α)
X
ρkn (p)ψ(p)ψ(p)⊤ ,
p∈ρk n
for any hop p ∈ Pn , we get 1 ∥ψ(p)∥2M (ρkn )−1 (1 − α) c1 , ≤ (1 − α)
∥ψ(p)∥2M (πnk )−1 ≤
where c1 is a constant. Then for any t ∈ [τ ], since rnk,t ≤ 1, we have |rnk,t ψ(p)⊤ M (πnk )−1 ψ(pk,t i )| ≤ rik,t ∥ψ(p)∥M (πnk )−1 ∥ψ(pk,t k )−1 i )∥M (πn c1 ≤ . (1 − α)
Lemma 3. Suppose Algorithm 1 runs K episode. With probability 1 − δ, for any episode k ∈ [K], n ∈ [N ] and p ∈ Pn , we have s NK b k Φ(p) − ∇k Φ(p)| ≤ c O(log N ) log ( δ ) |∇ n n (1 − α)τ +c where c is a constant. Proof. Recall that τ X k,t b ki Φ(p) = 1 ψ(p)⊤ M (πnk )−1 ψ(pk,t ∇ n )rn , τ t=1 k,t and (pk,t n , rn ) are drawn independently at each t ∈ [τ ]. As b kn Φ(a) is we use linear regression to estimate gradients, ∇ k k b unbiased [48], [66], i.e., Ek [∇n Φ(a)] = ∇n Φ(a). In addition, k,t Lemma 1 shows that ψ(p)⊤ M (πnk )−1 ψ(pk,t n )rn is bounded by c1 /(1 − α) and Lemma 2 shows that its second moment is bounded by c2 /(1 − α). Then by Bernstein’s inequality, for a fixed k ∈ [K], n ∈ [N ], and p ∈ Pn , with probability 1 − δ, we have s 2 2 k k b Φ(p) − ∇ Φ(p)| ≤ 4c2 log ( δ ) + 4c1 log ( δ ) . (6) |∇ n n (1 − α)τ 3(1 − α)τ
Then we extend Ineq. (6) to all k ∈ [K], n ∈ [N ] and p ∈ Pn , yielding s NK b kn Φ(p) − ∇kn Φ(p)| ≤ c O(log N ) log ( δ ) |∇ (1 − α)τ +c
As a result, we have τ
1X k,t ψ(p)⊤ M (πnk )−1 ψ(pk,t n )rn τ t=1 c1 ≤ . (1 − α)
b kn Φ(p)| = |∇
Lemma 2. Suppose Algorithm 1 runs K episode. For any episode k ∈ [K], n ∈ [N ] and p ∈ Pn , we have c2 k,t 2 Ek [(ψ(p)⊤ M (πnk )−1 ψ(pk,t , n )rn ) ] ≤ (1 − α) where c2 is a constant. Proof. We first show that for any t ∈ [τ ], we have k,t 2 Ek [(ψ(p)⊤ M (πnk )−1 ψ(pk,t n )rn ) ] 2 ≤ Ek [(ψ(p)⊤ M (πnk )−1 ψ(pk,t n )) ] k,t ⊤ k −1 ≤ Ek [ψ(p)⊤ M (πnk )−1 ψ(pk,t ψ(p)⊤ ] n )ψ(pn ) M (πn )
= ψ(p)⊤ M (πnk )−1 ψ(p) c2 ≤ . (1 − α)
O(log N ) log ( NδK ) , (1 − α)τ
O(log N ) log ( NδK ) , (1 − α)τ
where c is a constant. Lemma 4. Φ(·) is N-Lipschitz and N-smooth with respect to the L1 norm ∥ · ∥1 . Proof. By [48], [120], we know that Φ(π) = Ep∼π Φ(p) and Φ(p) ∈ [0, N ], where p is the joint hop chosen by all the nodes. Φ(π) − Φ(π ′ ) = Ep∼π − Ep∼π′ X h ′ = Ep1:n−1 ∼π1:n−1 ,pn:N ∼πn:N Φ(p) n∈[N ] ′ − Ep1:n ∼π1:n ,pn+1:N ∼πn+1:N Φ(a) X ≤ ∥πn − πn′ ∥1 · ∥Φ∥∞
i
n∈[N ]
≤ N ∥π − π ′ ∥1 . In addition, ∇π Φ(pi ) = Ep−i ∼π−i Φ(pi , p−i ), yielding ∥∇π Φ − ∇π′ Φ∥∞ ≤ N ∥π − π ′ ∥1 .
Finally, we can derive the following theorem with Lemma 1, Lemma 2, Lemma 3, and Lemma 4.
27
Theorem 3. Let T = kτ and assume that each policy in ∆(Pn ) has no zero element for all n. By running Algorithm 1 b kn Φ(p) defined in line 6 and exwith gradient estimator ∇ k ploratory policy ρn defined in line 5, if k ≥ N2 , then with probability 1 − δ, we have Nash-Regret(T ) ≤ Õ(N 2 T 5/6 log N ).
Qk Proof. Set ∇k Φ = ∇Φ( ). By Lemma 4, we have Φ(π
k+1
k
k
k+1
k
) ≥ Φ(π ) + ⟨∇Φ(π ), π −π ⟩ N k+1 − ∥π − π k ∥21 2 = Φ(π k ) + αβ⟨∇Φ(π k ), π̃ k+1 − π k ⟩ + (1 − α)⟨∇k Φ, ρk − π k ⟩ N − ∥αβ(π̃ k − π k ) + (1 − α)(ρk − π k )∥21 2 ≥ Φ(π k ) + αβ⟨∇Φ(π k ), π̃ k+1 − π k ⟩ − (1 − α)∥∇k Φ∥∞ ∥ρk − π k ∥1 N − ∥αβ(π̃ k − π k ) + (1 − α)(ρk − π k )∥21 2 ≥ Φ(π k ) + αβ⟨∇Φ(π k ), π̃ k+1 − π k ⟩ − 2(1 − α)N 2 O(log N ) N − ∥αβ(π̃ k − π k ) + (1 − α)(ρk − π k )∥21 2 ≥ Φ(π k ) + αβ⟨∇Φ(π k ), π̃ k+1 − π k ⟩ 2
− 2(1 − α)N O(log N ) 3
2
Apply it to the previous bound, and we have Φ(π k+1 ) ≥ Φ(π k ) + αβG(π k ) p αβ 4N 2 O(log N )c log (N K/δ) −p (1 − α)τ αβ − 2N O(log N )c log (N K/δ) (1 − α)τ − 2(1 − α)N 2 O(log N ) − 2N 3 (α2 + β 2 ). Summing over k ∈ [K] and we have K X k=1
G(π k ) ≤
Φ(π K+1 ) − Φ(π 1 ) αβ p K +p 4N 2 O(log N )c log (N K/δ) (1 − α)τ K 2N O(log N )c log (N K/δ) + (1 − α)τ 2K(1 − α)N 2 O(log N ) + αβ 2KN 3 (α2 + β 2 ) + . αβ
1 , and τ = K 2 and notice that Set (1 − α) = N1K , β = N √ K 2 1 when K ≥ N , we have α ≥ 2 and K X
G(π k ) = Õ(N 2 K 1/2 log N ).
k=1
Let T = Kτ , we have
2
− 2N (α + β ) Define the true target policy at episode k as follows
Nash-Regret(T ) = τ
K X
G(π k ) = Õ(N 2 T 5/6 log N ).
k=1
π bnk+1 = arg max⟨πn , ∇n Φ(πnk )⟩, πn and the Frank Wolfe gap of join strategy π ′
G(π) = max ⟨π − π, ∇Φ(π)⟩ ′ π
according to [48]. Then we have ⟨∇Φ(π k ), π̃ k+1 − π k ⟩ k b = ⟨∇Φ(π ), π̃ k+1 − π k ⟩ k b + ⟨∇Φ(π k ) − ∇Φ(π ), π̃ k+1 − π k ⟩ k b ≥ ⟨∇Φ(π ), π bk+1 − π k ⟩ k b + ⟨∇Φ(π k ) − ∇Φ(π ), π̃ k+1 − π k ⟩
= ⟨∇Φ(π k ), π bk+1 − π k ⟩ k b + ⟨∇Φ(π k ) − ∇Φ(π ), π̃ k+1 − π bk+1 ⟩ ≥ G(π k ) k b − ∥∇Φ(π k ) − ∇Φ(π )∥∞ ∥π̃ k+1 − π bk+1 ∥1 k b ≥ G(π k ) − 2N ∥∇Φ(π k ) − ∇Φ(π )∥∞ s N 4N 2 O(log N )c log ( δK ) ≥ G(π k ) − (1 − α)τ
−
2N O(log N )c log ( NδK ) (1 − α)τ
A PPENDIX I P ROOF OF C OROLLARY 2 Assumption 1. Each node n maintains a local episode counter kn and performs updates at a sequence of (wall-clock) times. When node n performs its (kn + 1)-th update, it uses k,t τ only its own local history {(pk,t n , rn )}t=1 collected since its previous update and its current policy πnkn . Moreover, (i) no inter-node communication is used, and (ii) the delay between two consecutive updates of any node is bounded: there exists D ≥ 1 such that between any two updates of node n, every other node updates at most D times. Lemma 5. Suppose Assumption 1 holds. Assume further that each node’s expected reward is Lipschitz in other nodes’ mixed policies: for every node n and action p ∈ Pn , X ′ ′ E[rn | p, π−n ] − E[rn | p, π−n ] ≤L ∥πm − πm ∥1 . m̸=n
(7) new old Let η := supm supone update ∥πm − πm ∥1 be the maximum per-update policy change. Then the Nash regret of the asynchronous execution satisfies, with probability 1 − δ,
Nash-Regretasync (T ) ≤ Nash-Regretsync (T )
28
e + O(LN Dη T ).
(8)
In particular, if Dη = o(1) (e.g., via diminishing stepsizes), then the regret remains sublinear in T . Proof. Fix a node n. Consider a local block of τ packets collected by node n between two consecutive local updates. Let π−n (t) denote the mixed policies of other nodes at packet time t within this block, and let π̄−n := π−n (1) be the other nodes’ policy vector at the beginning of the block. By Assumption 1, during this block, each other node m ̸= n performs at most D updates. Since each update changes its mixed policy by at most η in ℓ1 norm, we have for all t, ∥πm (t) − π̄m ∥1 ≤ Dη, and hence X
∀m ̸= n,
∥πm (t) − π̄m ∥1 ≤ (N − 1)Dη ≤ N Dη.
(9)
(10)
m̸=n
By the Lipschitz condition (7), for any action pn (t) chosen by node n at time t, |E[rn (t) | pn (t), π−n (t)] − E[rn (t) | pn (t), π̄−n ]| X ≤L ∥πm (t) − π̄m ∥1 ≤ LN Dη. (11) m̸=n
Therefore, relative to the synchronous (frozen) environment π̄−n within the block, the gradient estimator incurs an additional bias term of order O(LN Dη). Plugging this bias bound into the regret in Appendix H yields (8). A PPENDIX J P ROOF OF T HEOREM 2 Proof. We analyze the time complexity of Algorithm 1 line by line. Whenever a node receives packets, and it is not the destination of the packets, it first runs line 3 to collect rewards. The node selects the next hop out of O(log N ) possible candidate nodes for τ packets with the time complexity being O(τ log N ). Next, the node runs line 5 to identify an exploratory matrix. Since each node has at most O(log N ) possible candidate nodes, the time complexity of calculating the policy correlation matrix M (λ) by Eq. (3) is O(log3 N ), and M (λ) is a O(log N ) by O(log N ) matrix so the time complexity of calculating the determinant of M (λ) is also O(log3 N ). The time complexity of line 5 is O(|∆(Pn )| log3 N ) as the node identifies at most |∆(Pn )| policies in ∆(Pn ) to identify the minimum. In line 6, the time complexity of calculating the inverse of the policy correlation matrix M (πnk )−1 only once is O(log3 N ), and that of the matrix multiplication 2 k,t ψ(p)⊤ M (πnk )−1 ψ(pk,t n )rn is O(log N + log N ). Since the node estimates gradients over τ rewards for at most O(log N ) candidate nodes, the time complexity of calculating gradient b kn Φ is O(τ log3 N ). estimator ∇ Identifying the optimal policy π̃nk+1 in line 7 calculates the dot product of two O(log N )-dimensional vectors at most |∆(Pn )| times, leading to O(|∆(Pn )| log N ) of time complexity. For line 8, the time complexity of the linear combination of O(log N )-dimensional vectors is O(log N ).
Finally, since each node runs Algorithm 1 in parallel, the time complexity of updating a policy in an episode is O(τ log3 N + |∆(Pn )| log3 N ).
A PPENDIX K A DAPTIVITY TO E DGE H ETEROGENEITY Heterogeneous computational capacity. We add a section discussing how Totoro+ handles heterogeneous computational capacities in Appendix G, along with additional experiments demonstrating that Totoro+ can effectively adapt to heterogeneous computational capacities in terms of both computation and communication overhead. Heterogeneous bandwidth. To address heterogeneous bandwidth conditions, Totoro+ adopts a game-theoretic routing model that enables nodes to adaptively identify suitable nexthop nodes for FL task transmission. The algorithmic details and theoretical analysis are presented in Section V-C. Asynchronous updates. Totoro+ supports two forms of asynchronous updates 1) Asynchronous model updates in FL. The model update scheme is configurable by the application owner or developer. After an application is published, the FL aggregation mode can be configured as asynchronous [41] or semi-synchronous [40] according to application requirements. In addition, when nodes subscribe to an application, their computational capacity and bandwidth characteristics can be examined before admitting them into the candidate participant pool. This configurability represents an additional customization capability of Totoro+ , beyond its scalability and adaptivity advantages. 2) Asynchronous path selection. In Algorithm 1, the update procedure is asynchronous. Each node first explores candidate paths for τ rounds and then selects subsequent paths based on the feedback obtained during these τ rounds. When multiple nodes select the same path, the reward observed in that round is reduced. Moreover, when updating the policy π, Algorithm 1 employs a linear regression model to predict the gradient direction and adjust the policy accordingly, without requiring coordination with other nodes. As a result, the proposed game-theoretic algorithm in Totoro+ inherently supports asynchronous updates and is well suited to the uncertainty and dynamics of edge networks. A PPENDIX L A DAPT TO EDGE NODES WITH HETEROGENEOUS RESOURCES . We provide the following mechanism to adapt to edge nodes with heterogeneous resources. A P2P node in Totoro+ can be seen as a logical node. We can map a physical edge node with rich resources to more P2P nodes in Totoro+ , whereas mapping resource-constrained edge nodes to fewer P2P nodes. For example, suppose three physical edge nodes with 2, 4, and 8 CPU cores, respectively. Then, the nodes with 4 and 8 CPU cores can serve as 2 and 3 logical P2P nodes in the DHT-based P2P overlay network, respectively.
29
7 R W R U R
1 X P E H U R I 0 D V W H U V
1 X P E H U R I 0 D V W H U V
8
8
& 3 8 8 W L O L ] D W L R Q
8
8 8 8 8
5 H V R X U F H 8 Q L W V
8 8 8 8 8 8 5 H V R X U F H 8 Q L W V
8
Fig. 26: Totoro+ keeps a high CPU utilization in the node with more resource units.
% D V H O L Q H L Q W H U % D V H O L Q H L Q W U D & R P P X Q L F D W L R Q 7 L P H V
& R P P X Q L F D W L R Q 7 L P H V
7 R W R U R L Q W H U 7 R W R U R L Q W U D 1 X P E H U R I ( G J H V ×
8
5 H V R X U F H 8 Q L W V
Fig. 25: Totoro+ allocates more masters to the node with more resource units.
% D V H O L Q H
8 8 8 8 8 8 8 8 8 5 H V R X U F H 8 Q L W V 5 H V R X U F H 8 Q L W V 8 more 8 intra 8 Fig. 828: Totoro 8 + reduces total intra- and Fig. 27: Totoro+ enables 8
5 H V R X U F H 8 Q L W V
and inter-node communication edges.
One can follow a similar way for different resources such as memory, network bandwidths, or GPUs. In the DHT-based P2P overlay, the node mapped to two P2P nodes is assigned two NodeIds. Although these two NodeIDs may not be numerically close, the proximity metrics (e.g., hop counts, RTT, cross-site link congestion levels) in the publish/subscribe-based forest abstraction indicate that these two P2P nodes are physically close. Moreover, since the masters are distributed evenly across the overlay due to the hash function, the nodes mapped to two P2P nodes have more chances of being masters than those mapped to a P2P node. For failure recovery, since each P2P node operates individually and autonomously, the nodes mapped to multiple P2P nodes follow the same way to recover from failures. Lastly, since P2P nodes in the overlay represent resources, a physical node mapped to several P2P nodes can manage its resources by shutting down or spawning P2P nodes at an application level. Similarly, an FL application can follow the publish/subscribebased forest abstraction to select P2P nodes that meet the resource requirements to run the tasks. To evaluate the feasibility of logical P2P nodes, we performed 10,000 runs of a simple CNN training task [39] on a heterogeneous Amazon EC2 cluster. The cluster consists of 25 nodes, including 5 t2.small instances with 1 vCPU and 2 GB RAM, 5 t2.medium instances with 2 vCPUs and 4 GB RAM, 5 t2.large instances with 2 vCPUs and 8 GB RAM, 5 t2.xlarge instances with 4 vCPUs and 16 GB RAM, and 5 t2.2xlarge instances with 8 vCPUs and 32 GB RAM. For clarity of comparison, we denote Totoro+ as the approach that employs logical P2P nodes, while Baseline represents the approach that “does not” use logical P2P nodes. In Totoro+ ,
inter-node communication times. different numbers of logical P2P nodes are mapped onto a single physical node according to its resource capacity: one logical node for t2.small, two for t2.medium, four for t2.large, eight for t2.xlarge, and sixteen for t2.2xlarge. In contrast, the Baseline treats each physical node as a single logical node. To study the effectiveness of logical P2P nodes on computation and communication overhead, we do not use the proposed game-theory algorithm to determine routing paths. Computation overhead. We first compare the computation overhead between Totoro+ and the Baseline. As shown in Figure 25, Totoro+ assigns a larger number of masters to physical nodes with higher capacity (i.e., t2.2xlarge instances, which have 8 vCPUs and 32 GB RAM), while nodes with fewer resources are assigned only a small number of masters. In contrast, the Baseline distributes masters evenly across all physical nodes. We further compare the average CPU utilization, as illustrated in Figure 26. It can be clearly observed that Totoro+ achieves significantly higher CPU utilization by placing more masters on high-capacity (40U) physical nodes. By contrast, the Baseline fails to fully exploit resourcerich nodes due to its uniform allocation strategy. These two figures demonstrate that the logical P2P node mechanism in Totoro+ effectively adapts to node heterogeneity when handling computation overhead. Communication overhead. We next compare the communication overhead of Totoro+ and the Baseline. Since communication between logical P2P nodes can occur either over intra-node edges or inter-node edges, depending on whether the communicating nodes reside on the same physical node, we first examine the distribution of intra-node and inter-node
& R P ' 0 / 7 R W R U R * R V V L S ) / 7 R W R U R & R P ' 0 / * R V V L S ) /
7 R W D O 7 U D L Q L Q J 7 L P H K R X U V
(a) Google Speech [75] with ResNet-18 [76]
& R P ' 0 / 7 R W R U R * R V V L S ) / 7 R W R U R & R P ' 0 / * R V V L S ) /
7 R W D O 7 U D L Q L Q J 7 L P H K R X U V
(b) FEMNIST [9] with ShuffleNet V2 [77]
& R P ' 0 / 7 R W R U R * R V V L S ) / 7 R W R U R & R P ' 0 / * R V V L S ) /
7 R W D O 7 U D L Q L Q J 7 L P H K R X U V
(c) CIFAR-10 [121] with MobileViT [122]
$ F F X U D F \
$ F F X U D F \
$ F F X U D F \
$ F F X U D F \
30
& R P ' 0 / 7 R W R U R * R V V L S ) / 7 R W R U R & R P ' 0 / * R V V L S ) /
7 R W D O 7 U D L Q L Q J 7 L P H K R X U V
(d) MASSIVE [123] with ALBERT [124]
Fig. 29: Time-to-Accuracy performance. Decentralized federated learning frameworks running atop Totoro+ (ComDML + Totoro+ and GossipFL + Totoro+ ) achieve faster time-to-accuracy convergence. edges for both approaches (Figure 27). For inter-node edges, we count the edges at the sender side. We observe that Totoro+ assigns a larger number of both inter-node and intra-node edges to resource-rich nodes, whereas the Baseline distributes communication more evenly, with a stronger concentration on nodes with 6U, 10U, and 20U resources. Figure 28 further shows the communication time. As expected, internode edge communication incurs longer latency than intranode edge communication due to cross–physical-node data transfers. However, Totoro+ completes communication in less time overall, as it places a larger fraction of communication workloads on resource-rich nodes. In contrast, the Baseline distributes communication uniformly without considering node heterogeneity, resulting in less efficient utilization of available resources. Together, these results demonstrate that the logical P2P node mechanism in Totoro+ effectively distributes communication overhead according to node heterogeneity. A PPENDIX M T OTORO+ V. S . D ECENTRALIZED FL S YSTEMS In this section, we discuss the key differences between Totoro+ and existing decentralized federated learning (DFL) systems, focusing on both system-level design and path orchestration strategies. System-level differences. Although decentralized federated learning (DFL) systems remove the need for centralized model aggregation and parameter servers, most existing DFL systems, still rely on a logically centralized control plane for resource management and application coordination [125]– [128]. Specifically, a central management interface is typically responsible for assigning devices to different FL applications. For example, consider a deployment scenario with three concurrent FL applications and 1, 200 available clients. The control plane partitions the client pool into three disjoint overlays, each dedicated to a single application. Clients within an overlay collaborate exclusively with peers assigned to the same task and execute the DFL protocol, i.e., performing local training and decentralized aggregation within that isolated topology. No cross-overlay interaction is allowed [125], [126]. In contrast, Totoro+ eliminates the centralized control interface entirely and adopts a fully peer-to-peer (P2P) architecture for distributed management and coordination. Device participation, topology formation, and task execution are handled in a decentralized manner without relying on a global orchestrator.
By removing the control-plane bottleneck, Totoro+ enables improved scalability and more elastic adaptation as the number of clients and concurrent applications increases. Path planning models. The path planning model of Totoro+ is grounded in a game-theoretic formulation that explicitly accounts for competition among nodes over shared network resources. In particular, Totoro+ does not assume prior knowledge of bandwidth availability or link quality. Instead, routing decisions are made under incomplete information and are progressively refined based on observed transmission outcomes (bandit feedback). In contrast, most existing decentralized federated learning (DFL) frameworks assume the existence of a logically centralized entity that can obtain real-time transmission statistics between nodes, such as available bandwidth and network congestion levels [125], [126], [128]. Under this assumption, path or pairing decisions are typically derived from global network state information. To evaluate the impact of Totoro+ ’s path planning model, we integrate it into both ComDML [125] and GossipFL [126] and compare time-toaccuracy performance with and without Totoro+ . We isolate the routing component while keeping the original training logic unchanged. This allows us to quantify whether replacing the baseline path planning model with Totoro+ , which operates without prior knowledge of bandwidth availability or link quality, improves time-to-accuracy performance. We conduct experiments on four representative datasets: Google Speech [75] for speech recognition, FEMNIST [9] for grayscale image classification, CIFAR-10 [121] for color image classification, and MASSIVE [123] for intent classification. Each dataset is paired with a representative model architecture: ResNet-18 [76] for Google Speech, ShuffleNet V2 [77] for FEMNIST, MobileViT [122] for CIFAR10, and ALBERT [124] for MASSIVE. The corresponding results are presented in Figures 29(a), 29(b), 29(c), 29(d). The results show that, across both CNN-based applications (ResNet-18 in Figure 29(a) and ShuffleNet V2 in Figure 29(b)) and transformer-based models (MobileViT in Figure 29(c) and ALBERT in Figure 29(d)), DFL systems running atop Totoro+ consistently reach the target accuracy (indicated by the red dashed line) within a shorter training time. This improvement stems from Totoro+ ’s path planning model, which explicitly accounts for competition among nodes for shared transmission resources. Moreover, Totoro+ operates without prior knowledge of bandwidth availability or link quality
31
and instead adopts a bandit-based approach to progressively identify effective relay nodes for communication. In contrast, existing frameworks such as ComDML and GossipFL rely heavily on accurate and up-to-date transmission information when making routing decisions. If the collected information is inaccurate or becomes stale, these systems may make suboptimal routing or pairing decisions, which can lead to slower time-to-accuracy performance. A PPENDIX N D ISCUSSIONS AND F UTURE W ORK A. Security of the advertise-discover tree. The advertise-discover (AD) tree enables edge nodes in the multi-ring for application advertisement and discovery. However, some adversarial edge nodes likely advertise malicious application information to other nodes. Also, adversarial edge nodes may discover and perform malicious attacks on specific FL applications. An efficient method is to rely on some trusted authorities, e.g., ICANN [129] or a certification authority like Verisign [130]. The certification authority assigns a random NodeId to the new node and signs a NodeId certificate that binds the NodeID. Suppose a node wants to locate an FL application. In that case, it first uses the AppId=hash(“advertise-discover application”) as the key to route a JOIN message that contains its NodeId certificate. The internal node in the advertisediscover tree checks with the certification authority to verify the NodeId certificate after receiving the JOIN message. If the certificate is authentic, the new node joins the advertisediscover tree and gets the AppIds of FL applications running over the DHT-based P2P overlay. Next, joining the dataflow tree of the FL application follows the same way. Likewise, if a node wants to advertise an FL application, it first contacts the certification authority to obtain an AppId certificate. The nodes that want to run the FL application first route JOIN messages using the AppId as the key, then receive the AppId certificate, check with the certification authority to verify the AppId certificate, join the dataflow tree, and run the FL application. B. Sending packets to multiple nodes simultaneously. Currently, each node follows Algorithm 1 to forward packets to a “single node”, and we have shown that Algorithm 1 achieves an ϵ-approximate Nash equilibrium (Theorem 1). However, multicast has been a communication paradigm that improves communication efficiency. Fortunately, we can extend Algorithm 1 to support multicast. We present the multicast-enabled distributed hop-by-hop routing algorithm in Algorithm 2. We follow the setup in Appendix E to illustrate the differences. In line 3, each node follows the initial policy to select multiple hops, e.g., m1 and m2 , to send packets simultaneously and receive rewards. The range of rewards may become [0, F ], where F denotes the maximum number of hops selected. Then, since each node can select multiple hops, Pl1 may contain {m1 , m2 , {m1 , m2 }}, and similarly each policy in ∆(Pl1 ) becomes a 3-dimensional vector, e.g., [0.6, 0.1, 0.3], where it represents that 60% of
Algorithm 2 Multicast-enabled distributed hop-by-hop routing algorithm Input: mixture weights α, β ∈ [0, 1]; initial policy πn1 for all n ∈ N. 1: for episode k = 1, 2, · · · do 2: for packet t = 1, · · · , τ do 3: Each node n in parallel selects multiple hops pk,t ∼ πnk to send a packet simultaneously, n observes reward rnk,t . 4: 5: 6: 7: 8:
for node n = 1, · · · , N do in parallel ρkn ← arg minλ∈∆(Pn ) det(M (λ)). b kn Φ(p) ← 1 Pτ ψ(p)⊤ M (πnk )−1 ψ(pk,t )rnk,t , ∇ n t=1 τ for all p ∈ Pn . b kn Φ⟩. π̃nk+1 ← arg maxλ∈∆(Pn ) ⟨λ, ∇ k k+1 k+1 πn ← α πn + β(π̃n − πnk ) + (1 − α)ρkn . | {z } | {z } Frank-Wolfe update
Exploration
chance selecting m1 , 10% of chance selecting m2 , and 30% of chance selecting both m1 and m2 . Subsequently, each node follows line 6 to estimate the gradients of each possible action. Overall, Algorithm 2 can fully support multicast in a distributed manner, but we leave the upper bound of Nash regret of Algorithm 2 to future work. C. Real-world deployment of Totoro+ While many existing FL systems are operated by a single organization, there also exist more open and community-driven platforms (e.g., crowdsourcing-based FL platforms [131]– [133]), where application owners publish training requests according to their data or model requirements, and participating devices are recruited through incentive mechanisms designed to encourage contribution. Totoro+ is particularly well-suited for these scenarios. First, its high scalability enables multiple FL applications and a large number of heterogeneous devices to execute training workflows in parallel in a distributed manner, without relying on a centralized server for synchronization or scheduling. Second, its adaptivity limits the impact of highly dynamic device participation on the overall FL process, which is common in open platforms or edge computing. Third, the customizability of Totoro+ allows different FL applications to flexibly incorporate diverse mechanisms (e.g., incentive strategies and client selection policies) without embedding all such logic into a centralized server. We also note that many existing P2P systems, including prior P2P-based FL designs (e.g., [125]–[128]), make similar assumptions regarding cooperative or incentive-compatible environments. Therefore, we believe it is well positioned to demonstrate the scalability, adaptivity, and customization advantages of Totoro+ in environments where P2P functionality is permitted and open development is feasible. D. Adaptivity to non-IID settings Given the high heterogeneity of edge environments (e.g., diverse devices, data ownership, and application requirements), the customization capability of Totoro+ enables application
32
owners to deploy FL workflows with different mechanisms for handling non-IID data distributions. For example, before publishing an application, developers can specify customized algorithms for data filtering [134]–[136] or client selection [34]– [36], which are executed by the master assigned by Totoro+ . During application subscription, the master can selectively admit clients based on statistical properties of their local data (e.g., Dirichlet- or Gaussian-based distributions), select clients that satisfy specific data requirements, or employ personalization schemes that allow subscribed devices to update local model parameters differently under non-IID conditions. Through these extensions, Totoro+ provides system-level support for a wide range of non-IID-aware FL algorithms.