Scheduling with privacy constraints

Sachin Kadloor, Negar Kiyavash, Parv Venkitasubramaniam

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


In multi-tasking systems where a finite resource is to be shared, a scheduler dictates how the resource is divided among competing processes. Examples of systems which have schedulers include, a computer where the CPU needs to be shared between the different threads running, a cloud computing infrastructure with shared computing resources, a network router serving packets from different streams etc.. In such situations, when a processor is shared by multiple users, the delays experienced by jobs from one user are a function of the arrival pattern of jobs from other users, and the scheduling policy of the server. Consequently, a scheduling system creates a timing side channel in which information about arrival pattern from one user is inadvertently leaked to another. In this work, this information leakage is studied for a two user scheduling system. We first introduce a measure of privacy and then demonstrate that no scheduler can provide maximum privacy without idling/taking vacations, and consequently no policy can simultaneously be delay and privacy optimal.

Original languageEnglish (US)
Title of host publication2012 IEEE Information Theory Workshop, ITW 2012
Number of pages5
StatePublished - Dec 1 2012
Event2012 IEEE Information Theory Workshop, ITW 2012 - Lausanne, Switzerland
Duration: Sep 3 2012Sep 7 2012

Publication series

Name2012 IEEE Information Theory Workshop, ITW 2012


Other2012 IEEE Information Theory Workshop, ITW 2012


  • Scheduling policy
  • information leakage
  • timing side channels

ASJC Scopus subject areas

  • Information Systems


Dive into the research topics of 'Scheduling with privacy constraints'. Together they form a unique fingerprint.

Cite this