Delay optimal policies offer very little privacy

Sachin Kadloor, Negar Kiyavash

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 learnt by another as a consequence of sharing the scheduler. In [1], 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 (FCFS) offers very little privacy to its users. We also proposed a parametric non-work-conserving policy which traded off delay for improved privacy. In this work, we ask the question, is a trade-off between delay and privacy fundamental to the design to scheduling policies? In particular, is there a work-conserving, possibly randomized, 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 (a deterministic policy) is privacy optimal within the class of work-conserving policies.

Original languageEnglish (US)
Title of host publication2013 Proceedings IEEE INFOCOM 2013
Number of pages9
StatePublished - 2013
Event32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013 - Turin, Italy
Duration: Apr 14 2013Apr 19 2013

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Other32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Delay optimal policies offer very little privacy'. Together they form a unique fingerprint.

Cite this