TL;DR
Most Federated Learning (FL) research assumes a "monopoly" where one server rules them all. FairFedJS breaks this mold by introducing a fairness-aware scheduler for environments where multiple independent FL jobs compete for the same pool of clients. By leveraging Lyapunov optimization, it ensures that jobs requiring high-demand data types aren't left stranded, improving scheduling fairness by nearly 32% without sacrificing model accuracy.
What Problem Does This Paper Address?
In the standard Federated Learning (FL) narrative, a single server coordinates a group of clients to train a model. However, the real world is rarely a monopoly. Imagine a marketplace where multiple companies (servers) are simultaneously trying to train different models (jobs) using the same pool of mobile devices or edge sensors (clients).
This creates a "multi-job" bottleneck. Clients have finite resources and can usually only participate in one training job at a time. If several jobs all need a specific, rare data type (e.g., specialized medical images or a specific dialect of speech), some jobs might face "prolonged waiting," leading to slow convergence or total starvation. Current methods often focus on minimizing costs for the servers but ignore the fairness of how these jobs are actually scheduled. The authors aim to bridge this gap by ensuring that high-demand client datasets are allocated fairly across competing jobs.
Methods
The authors propose FairFedJS (Fairness-aware Federated Job Scheduling), which treats the scheduling problem as a dual-objective optimization: maximizing system revenue while minimizing scheduling unfairness.
Key components include:
- Virtual Queues: The system maintains a virtual queue for each data type. If the demand for a specific data type (e.g., "images") exceeds the supply of available clients, the queue grows. A longer queue signals a higher priority for jobs needing that data.
- Lyapunov Optimization: This is the mathematical "secret sauce." The researchers use a Lyapunov drift-plus-penalty framework to stabilize these virtual queues. By minimizing the "drift," the system naturally prioritizes jobs that have been waiting the longest for specific resources.
- Job Scheduling Index (JSI): To make real-time decisions, the complex optimization is boiled down to a single score for each job. The JSI considers the current queue length (demand), the job's payment bid, and the expected cost/reliability of clients. Jobs are then ranked and scheduled in ascending order of their JSI.
- Reputation & Data Fairness: When a job is finally scheduled, it selects clients based on a Beta Reputation System (how reliable has this client been?) and Data Fairness (has this client been over-sampled recently?).
Datasets
The approach was evaluated using two classic computer vision benchmarks, adapted for a multi-job, multi-client environment:
- Fashion-MNIST: Used for three concurrent jobs (MLP, CNN, and ResNet models).
- CIFAR-10: Used for another three concurrent jobs (MLP, CNN, and ResNet models).
The experimental setup involved 50 FL clients: 20 dedicated to Fashion-MNIST, 20 to CIFAR-10, and 10 "versatile" clients possessing both datasets. The authors tested both IID (Independent and Identically Distributed) and Non-IID data distributions to simulate real-world data heterogeneity.
Key Insights and Ideas
- Client Availability as a Resource: Instead of just looking at model accuracy, the paper treats "client availability" as a fluctuating resource that needs to be managed like a network buffer.
- The "Human-over-the-loop" Flexibility: By incorporating job payment bids into the JSI, the system allows server administrators to manually adjust their priority by increasing their "bids," while the Lyapunov framework ensures this doesn't completely starve lower-paying jobs that require rare data.
- Fairness vs. Convergence: The paper highlights that scheduling fairness isn't just a moral goal—it's a functional one. By preventing jobs from waiting too long for specific data types, the entire system converges more predictably.
Key Results
FairFedJS was compared against four baselines: Random scheduling, Alternating (round-robin), Utility-Based, and MJ-FL (a state-of-the-art cost-minimization approach).
- Scheduling Fairness (SF): FairFedJS outperformed the best baseline (MJ-FL) by 31.9% on average. It significantly reduced the variance in "waiting times" for different data types.
- Convergence Speed: It achieved 1.0% faster convergence on average. While 1% sounds small, in large-scale FL involving thousands of rounds, this represents significant savings in time and compute energy.
- Model Accuracy: Despite the focus on scheduling fairness, the final test accuracy remained comparable to (and sometimes better than) the baselines, proving that you don't have to trade off model quality for system fairness.
Limitations and Future Work
While FairFedJS is a significant step forward for horizontal FL (where clients share the same feature space), the authors acknowledge a few areas for growth:
- Vertical FL: The current model assumes jobs only need one type of data. Future work will explore scenarios where a single job might require a combination of multiple data types (e.g., both text and images) from different clients simultaneously.
- Federated Transfer Learning: The authors plan to adapt the scheduler for transfer learning scenarios, where the relationship between jobs is more complex than simple competition.
- Scalability: While the math holds, testing the JSI ranking in environments with thousands of concurrent jobs (rather than six) remains an open challenge.
Summary updated