Files in this item



application/pdfSachin_Kadloor.pdf (2MB)
(no description provided)PDF


Title:Scheduling with privacy constraints
Author(s):Kadloor, Sachin
Director of Research:Kiyavash, Negar
Doctoral Committee Chair(s):Kiyavash, Negar
Doctoral Committee Member(s):Hajek, Bruce; Srikant, Rayadurgam; Borisov, Nikita
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
timing channel
side channel
Abstract: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 associated privacy which is a measure of the information about the usage pattern of one user of the system that can be learned by another as a consequence of sharing the scheduler. Consider two processes, one of them an innocuous process (referred to as Alice) and the other a malicious one (referred to as Bob), using a common scheduler to process their jobs. Based on when his jobs get processed, Bob wishes to learn about the pattern (size and timing) of jobs of Alice. Depending on the context, knowledge of this pattern could have serious implications on Alice's privacy and security. For instance, shared routers can reveal traffic patterns, shared memory access can reveal cloud usage patterns, and so on. We present a formal framework to study the information leakage in shared resource schedulers. The first-come-first-serve (FCFS) scheduling policy and time-division-multiple-access (TDMA) are identified as two extreme policies on the privacy metric, FCFS has the least, and TDMA has the highest. However, on performance based metrics, such as throughput and delay, it is well known that FCFS significantly outperforms TDMA. This raises the question: \emph{Is a tradeoff between delay and privacy fundamental to the design to scheduling policies? In particular, is there a work-conserving (a class of policies that offer minimal delay), 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. We then derive two parametrized policies, accumulate and serve, and proportional TDMA, which take two different approaches to offer a tunable tradeoff between privacy and performance.
Issue Date:2014-01-16
Rights Information:Copyright 2013 Sachin Kadloor
Date Available in IDEALS:2014-01-16
Date Deposited:2013-12

This item appears in the following Collection(s)

Item Statistics