Temporal Fairness of Round Robin

Fairness is an important criterion considered in scheduling together with overall job latency. Round Robin is a popular scheduling policy that distributes resources to jobs equally at any point in time guaranteeing instantaneous fairness of jobs. In this paper we give the first analysis of Round Robin for the L_2-norm of flow time and show that it is O(1)-speed O(1)-competitive on multiple machines. The L_2-norm is a popular scheduling objective that makes a natural balance between temporal fairness and jobs latency. Prior to our work, Round Robin has not been analyzed for the L_2-norm even in the single machine setting. Our result establishes that Round Robin is fair not only instantaneously but also temporarily.