Scheduling with privacy constraints

Sachin Kadloor, Negar Kiyavash, Parv Venkitasubramaniam

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

Abstract

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
Pages40-44
Number of pages5
DOIs
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

Other

Other2012 IEEE Information Theory Workshop, ITW 2012
CountrySwitzerland
CityLausanne
Period9/3/129/7/12

Keywords

  • Scheduling policy
  • information leakage
  • timing side channels

ASJC Scopus subject areas

  • Information Systems

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

Cite this