Decentralized Scheduling for Large Scale Distributed Systems

25 concepts30 papers1 proposal

In large-scale distributed computing, scheduling has traditionally relied on a bird's-eye view. A centralized controller monitors the state of all available resources, receives incoming tasks, and computes an optimal assignment to balance loads, minimize latency, or reduce energy consumption.

However, as systems scale to thousands of nodes across edge networks, serverless clusters, and geo-distributed data centers, this centralized model hits a fundamental physical limit: the cost of maintaining global knowledge.

The Cost of Global Knowledge

To make a perfect scheduling decision, a central coordinator must constantly synchronize state information with every worker node in the network. As noted by Carli, Thomas et al. in A packing problem approach to energy-aware load distribution in Clouds, maintaining this global state creates massive communication overhead and latency issues in geographically distributed environments. When the network grows, the time spent transmitting state updates can easily exceed the execution time of the tasks themselves.

This bottleneck becomes acute when workloads are highly dynamic or ephemeral. For example, in deep learning clusters where jobs frequently launch and pre-empt, Saurabh Agarwal et al. demonstrated in Blox: A Modular Toolkit for Deep Learning Schedulers that centralized cluster controllers face severe communication bottlenecks that limit responsiveness. A similar vulnerability was highlighted by Jashwant Raj Gunasekaran et al. in Fifer: Tackling Resource Underutilization in the Serverless Era, showing that centralized state management introduces critical performance bottlenecks during multi-thousand-node serverless deployments.

Centralized:  [Workers] ---> (State Updates) ---> [Central Controller] ---> (Task Assignments) ---> [Workers]
Decentralized: [Worker A] <--- (Local Negotiation / Shared Heuristics) ---> [Worker B]

Whether managing edge clouds (Lei Yang et al. in QoS Guaranteed Resource Allocation for Live Virtual Machine Migration in Edge Clouds), multi-job federated learning (Chendi Zhou et al. in Efficient Device Scheduling with Multi-Job Federated Learning), or massive web crawlers (Weizhe Zhang et al. in Scale-Adaptable Recrawl Strategies for DHT-Based Distributed Web Crawling System), relying on a single coordinator introduces a single point of failure and a severe computational constraint. To scale further, systems must shift from global coordination to local execution.

Shifting Control to the Workers

The core intuition behind decentralized scheduling is simple: if a central coordinator cannot process task assignments fast enough, the scheduling logic must be pushed down to the execution units themselves.

Consider the serverless parallel computing framework designed by Benjamin Carver et al. in Wukong: A Scalable and Locality-Enhanced Framework for Serverless Parallel Computing. Instead of routing thousands of concurrent tasks through a central master, the authors shifted scheduling decisions directly to the workers. By making the workers decentralized and locality-aware, they execute complex parallel jobs without waiting on a central bottleneck.

Another classic mechanism for worker-led scheduling is work stealing. Instead of a central broker pushing tasks down to idle nodes, idle processors actively "steal" tasks from their busy neighbors. Nicolas Gast et al. analyzed this using mean field theory in A mean field model of work stealing in large-scale systems, proving that as systems scale to massive proportions, a decentralized strategy where idle nodes steal half of a victim's tasks optimizes throughput far better than a central broker prone to congestion.

Coordinating via Local Experience and Learning

If there is no central authority, how do independent nodes avoid chaotic behavior, such as herd mentality where every worker offloads tasks to the exact same neighbor? The solution lies in multi-agent learning, where nodes learn to cooperate using only local observations.

Early foundational work by Andrea Schaerf et al. in Adaptive Load Balancing: A Study in Multi-Agent Learning demonstrated that distributed systems can achieve efficient load balancing purely through decentralized reinforcement learning based on local experience. Crucially, the authors found that naive communication between agents could sometimes degrade performance, emphasizing that well-tuned, independent local learning can be highly effective on its own.

Modern frameworks build on this by using Multi-Agent Reinforcement Learning (MARL) to handle highly volatile environments:

Mathematical Guarantees and Limits

While decentralization solves the scalability problem, it introduces a new question: does sacrificing global knowledge mean sacrificing too much efficiency? Can local decisions ever match the global optimum?

The answer is often yes, provided the algorithm leverages structured local interactions. Nikos Tziritas et al. proved this in An Optimal Fully Distributed Algorithm to Minimize the Resource Consumption of Cloud Applications. Their distributed resource allocation algorithm (DRA) relies exclusively on local information exchange between neighboring nodes but is mathematically guaranteed to converge to the globally optimal workload layout in hierarchical networks. Similarly, Monika Henzinger et al. in Efficient Distributed Workload (Re-)Embedding developed a near-optimal distributed algorithm that tracks communication patterns locally to re-embed workloads, achieving a competitive ratio close to the theoretical lower bound without global coordination.

However, decentralization is not a silver bullet. Schedulers must account for physical constraints like task switching overhead or routing inefficiencies. Ping-Chun Hsieh et al. in Delay-Optimal Scheduling for Queueing Systems with Switching Overhead noted that while centralized scheduling handles task-switching penalties well, extending these guarantees to fully distributed multi-server environments remains an open challenge.

Furthermore, Rahul Vaze et al. in Multiple Server SRPT with speed scaling is competitive demonstrated a fundamental trade-off: naive decentralized greedy routing policies (where jobs simply choose the least-loaded server) see their competitive ratios degrade as the number of servers grows. This highlights that pure, uncoordinated local greed can be less efficient than centralized scheduling with migration, underscoring the need for the sophisticated local learning and structured distributed algorithms explored across this field.

Key Foundational Work

Distributed Algorithm for Service Replication in Service Overlay Network (2004) — contributed 1 concept elements to this direction.
Adaptive Load Balancing: A Study in Multi-Agent Learning (1995) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_centralized_scheduling_bottleneck_e96efb7a,
  title = {centralized scheduling bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/centralized-scheduling-bottleneck/rdr_e96efb7aae89438f85b872d7f291b98e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_centralized_scheduling_bottleneck_e96efb7a_v1,
  title = {centralized scheduling bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/centralized-scheduling-bottleneck/rdr_e96efb7aae89438f85b872d7f291b98e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake