In distributed computer networks where resources are under decentralized control, selfish users will generally not work towards one common goal, such as maximizing the overall value provided by the system, but will instead try to strategically maximize their individual benefit. This shifts the scheduling policy in such systems – the decision about which user may access what resource – from being a purely algorithmic challenge to the domain of mechanism design.

In this paper we will showcase the benefit of allowing preemption in such economic online settings regarding the performance of market mechanisms by extending the Decentralized Local Greedy Mechanism of Heydenreich et al. [11]. This mechanism was shown to be 3.281-competitive with respect to total weighted completion time if the players act rationally. We show that the preemptive version of this mechanism is 2-competitive. As a by-product, preemption allows to relax the assumptions on jobs upon which this competitiveness relies. In addition to this worst case analysis, we provide an in-depth empirical analysis of the average case performance of the original mechanism and its preemptive extension based on real workload traces. Our empirical findings indicate that introducing preemption improves both the utility and the slowdown of the jobs. Furthermore, this improvement does not come at the expense of low-priority jobs.