Can anyone shed light on how that's possible? I was under the impression that global state in distributed systems was not possible?
Basically, there's a server that holds state for the cluster. When a scheduler attempts to load a job into the cluster, it grabs state from the aforementioned server, performs its job placement calculations, and then tries to submit its answer to the master state. Since there are many such schedulers, and the amount of time it takes to place a job is non-trivial, its possible that during the processing time to calculate placement, another scheduler might've consumed the requested resources. In this case, the first scheduler will provision whichever services are not in conflict for placement location, and perform a new calculation with the new state to place the remaining conflicted servers.
The general idea is that most services don't have such a high affinity that the components need to be started all at the same time (a MapReduce job on 10,000 nodes can still run with 5,000 nodes while the second 5k are provisioning). The tradeoff here is that you have to manage conflicts, but the hope is that there are few enough that your optimism is rewarded.
Does that make sense?
In most scheduling systems, two 10,000-node jobs that each would saturate a cluster on their own will time-share if submitted together, with each job acting in practice more like 10,000 single-node jobs. The result is usually each job getting a probabilistic 50% share of the cluster while they're both running, and then whichever one runs longer saturating the cluster once the other ends.
This scheduling system, meanwhile, would seem to just hand the 10,000 nodes over to job A, and then sleep job B until job A is done.
Admittedly, in the case where the jobs aren't submitted at the same time, and job A has already grabbed and saturated the cluster, the two cases collapse together: job B must wait (unless you want to schedule processes rather than containers; then you just degrade the cluster's performance.) But for batch-processing applications, you'd usually schedule everything to start at once, precisely so that the scheduler could interleave the jobs.
FWIW, Omega seems like the answer if the overhead for resolving inconsistencies becomes low enough such that the benefits of optimistic scheduling outweigh the costs.
[0]http://www.slideshare.net/sameertiwari33/scheduling-on-large... See slide 6.
One note on priorities a la Borg (what I think people are actually using at Google today, but I don't know to what extent Omega was merged with it after the Omega paper or if Borg currently runs as an Omega scheduler or what), is that it sometimes causes annoyance for people at Google, as the optimal priority is not always assigned to certain workloads, leading to starvation or overpreemption of things that were not given a healthy number. I believe that Mesos' work on oversubscription took concerns around this issue into consideration.
It's really fascinating to compare the architecture of Nomad vs K8s, because both claim heavy descendence from Omega + Borg. If I squint, it seems like Nomad is more of a direct implementation based on those papers. K8s more explicitly modularizes more components, which I think is why a lot of companies are jumping behind it, as they can mold it in the ways they want.