Delay-Privacy Tradeoff in the Design of Scheduling Policies

Traditionally, scheduling policies have been optimized to perform well on metrics, such as throughput, delay, and fairness. In the context of shared event schedulers, where a common processor is shared among multiple users, one also has to consider the privacy offered by the scheduling policy. The privacy offered by a scheduling policy measures how much information about the usage pattern of one user of the system can be learned by another as a consequence of sharing the scheduler. We introduced an estimation error-based metric to quantify this privacy. We showed that the most commonly deployed scheduling policy, the first-come-first-served offers very little privacy to its users. We also proposed a parametric nonwork conserving policy, which traded off delay for improved privacy. In this paper, we ask the question, is a tradeoff between delay and privacy fundamental to the design to scheduling policies? In particular, is there a work conserving, possibly randomized, and scheduling policy that scores high on the privacy metric? Answering the first question, we show that there does exist a fundamental limit on the privacy performance of a work-conserving scheduling policy. We quantify this limit. Furthermore, answering the second question, we demonstrate that the round-robin scheduling policy (deterministic policy) is privacy optimal within the class of work-conserving policies.