TL;DR
Venn is a novel resource manager for collaborative learning (CL) that reduces average job completion time by up to 1.88×. It achieves this by intelligently resolving resource contention among concurrent jobs and using tier-based device matching to mitigate the impact of slow "straggler" devices.
What Problem Does This Paper Address?
Collaborative Learning (or Federated Learning) allows models to be trained on distributed edge devices—like smartphones and IoT sensors—without moving raw data to the cloud. While great for privacy, it's a logistical nightmare for resource management.
Edge devices are ephemeral: they only check in when they are charging and connected to WiFi. They are also heterogeneous: a high-end flagship phone trains much faster than a budget model. As more companies deploy multiple CL jobs simultaneously (e.g., one for speech recognition, another for keyboard prediction), these jobs start fighting for the same pool of available devices.
Current industry standards (from Apple, Meta, and Google) often rely on random device-to-job matching. The authors argue this is highly inefficient because it ignores resource contention, leading to massive scheduling delays—the time a job spends just waiting to acquire enough devices to start a training round.
Methods
Venn introduces a two-pronged approach to tackle the two main components of Job Completion Time (JCT): scheduling delay and response collection time.
- Intersection Resource Scheduling (IRS): The authors model resource contention as a multi-commodity flow problem. Since this is NP-hard at the scale of millions of devices, Venn uses a two-step heuristic:
- Intra-group Scheduling: Within a group of jobs requiring the same device specs, it prioritizes jobs with the smallest remaining resource demands.
- Inter-group Scheduling: It identifies "scarce" resources (devices that only a few jobs can use) and ensures they aren't wasted on jobs that could use more "abundant" resources.
- Resource-Aware Device Matching: Once a job is scheduled, Venn doesn't just pick devices at random. It partitions available devices into tiers based on hardware capability. It then matches a job to a specific tier to ensure all participants in a round have similar performance. This prevents a single slow device (a straggler) from holding up the entire round.
- Starvation Prevention: To ensure large, resource-heavy jobs aren't stuck behind a constant stream of small jobs, Venn includes a fairness knob ($\epsilon$) that adjusts job priorities based on how long they've been waiting relative to a "fair share" baseline.
Datasets
The researchers evaluated Venn using a high-fidelity simulator and a real-world testbed, utilizing:
- FedScale: A large-scale dataset containing 180 million trace items of real-world client availability (charging/WiFi status).
- AI Benchmark: Data on the CPU and memory capacities of diverse mobile devices to emulate hardware heterogeneity.
- FEMNIST: A standard image dataset used to train ResNet-18 and MobileNet-V2 models for the end-to-end performance tests.
- Real-world Job Traces: Workload characteristics derived from applications like Google’s Gboard next-word prediction and speech recognition.
Key Insights and Ideas
- Scheduling Delay is the Hidden Bottleneck: Most research focuses on making the computation faster. Venn shows that as the number of concurrent jobs grows, the time spent waiting for devices can actually dominate the total JCT.
- The Cost of Randomness: Random matching is "wasteful." If a job can run on any device, but it's randomly assigned a high-end device that a more specialized job requires, the specialized job is forced to wait, increasing the overall system delay.
- Tiering Mitigates Stragglers: By grouping devices of similar power together for a single round, Venn ensures the "tail latency" (the time the last device takes to finish) is much closer to the average latency.
Key Results
- Speedup: Venn improves average JCT by up to 1.88× compared to random matching and significantly outperforms standard scheduling policies like FIFO and Shortest Remaining Service First (SRSF).
- Scalability: The scheduling algorithm has a low time complexity ($O(m \log m)$ or $O(n^2)$), allowing it to handle thousands of jobs and millions of devices with negligible overhead (less than 1ms latency at scale).
- Accuracy: Venn speeds up the time to reach target accuracy without negatively impacting the final model performance.
Limitations and Future Work
- Fairness Trade-off: There is a clear trade-off between absolute system efficiency and job fairness. Increasing the fairness knob to ensure no job is "starved" naturally reduces the overall JCT gains.
- Profiling Reliance: The tier-based matching relies on accurate profiling of device hardware. While Venn does this adaptively, initial rounds for new device types might be less efficient.
- Synchronous Focus: While the authors mention Venn can extend to asynchronous CL, the primary evaluation and the tiering logic are most impactful for synchronous rounds where stragglers are a major issue. Future work could explore more deeply how these contention-aware heuristics benefit purely asynchronous environments.
Summary updated