Venn: Resource Management for Collaborative Learning Jobs

Jiachen Liu, Fan Lai, Ding Ding, Yiwen Zhang, Mosharaf Chowdhury

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.

Figure 1. Composition of the completion time of one round of a CL job.

Methods

Venn introduces a two-pronged approach to tackle the two main components of Job Completion Time (JCT): scheduling delay and response collection time.

  1. 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:
  2. Intra-group Scheduling: Within a group of jobs requiring the same device specs, it prioritizes jobs with the smallest remaining resource demands.
  3. 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.
  4. 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.
  5. 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.
Figure 6. Venn system overview.

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.
Figure 3. Toy example showing how optimal scheduling avoids wasting scarce resources.

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

Abstract

In recent years, collaborative learning (CL) has emerged as a promising approach for machine learning (ML) and data science across distributed edge devices. As the deployment of CL jobs increases, they inevitably contend for limited resources. However, efficient resource scheduling in this context is challenging because of the ephemeral nature and resource heterogeneity of devices, coupled with the overlapping resource requirements of diverse CL jobs. Existing resource managers often assign devices to CL jobs randomly for simplicity and scalability, but this approach compromises job efficiency. In this paper, we present Venn, a CL resource manager that efficiently schedules ephemeral, heterogeneous devices among multiple CL jobs to reduce the average job completion time (JCT). Venn formulates the Intersection Resource Scheduling (IRS) problem to identify complex resource contention among multiple CL jobs. It then proposes a contention-aware scheduling heuristic to minimize the average scheduling delay. Furthermore, it proposes a resource-aware device-to-job matching heuristic to optimize response collection time by mitigating stragglers. Our evaluation shows that, compared to the state-of-the-art CL resource managers, Venn improves the average JCT by up to 1.88x. The code is available at https://github.com/SymbioticLab/Venn.
BibTeX
@misc{liu2023venn,
  author = {Jiachen Liu and Fan Lai and Ding Ding and Yiwen Zhang and Mosharaf Chowdhury},
  title = {{Venn: Resource Management for Collaborative Learning Jobs}},
  year = {2023},
  eprint = {2312.08298},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2312.08298},
}
Figure