Delay-Privacy Tradeoff in the Design of Scheduling Policies

Sachin Kadloor, Negar Kiyavash

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number7047841
Pages (from-to)2557-2573
Number of pages17
JournalIEEE Transactions on Information Theory
Issue number5
StatePublished - May 1 2015
Externally publishedYes

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Delay-Privacy Tradeoff in the Design of Scheduling Policies'. Together they form a unique fingerprint.

Cite this