The scheduler is shared state

Why does a single scheduler become a ceiling when tasks get short?

Before workload management, there is a piece that fits neither when nor where. The scheduler is itself a shared mutable data structure. It holds the state of the cluster (which machine has which free slots), and many requests read and change that state at the same time.

Every scheduler ever built has picked one of the concurrency-control options from databases to protect that state. That is the whole taxonomy, and seeing it collapses a large literature into one table. Three short definitions first:

• Pessimistic locking: take a lock before touching the state, so others wait. Safe, but waiting.
• Optimistic concurrency (MVCC with compare-and-swap, "CAS"): work on a snapshot without locking, then try to commit. If someone else changed the same state meanwhile, the commit fails and you retry. Fast when conflicts are rare.
• No coordination: each actor decides alone, on partial information.

Why the single scheduler becomes a ceiling

Cluster state is read-modify-write: read the free slots, choose, write the new allocation. One scheduler with a global view is a serialized critical section. It makes the best decisions, and its throughput is decisions per second. That becomes the ceiling when tasks are short.

This is exactly Lena's problem.