TY - GEN
T1 - Scheduling with privacy constraints
AU - Kadloor, Sachin
AU - Kiyavash, Negar
AU - Venkitasubramaniam, Parv
PY - 2012/12/1
Y1 - 2012/12/1
N2 - 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.
AB - 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.
KW - Scheduling policy
KW - information leakage
KW - timing side channels
UR - http://www.scopus.com/inward/record.url?scp=84873142358&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84873142358&partnerID=8YFLogxK
U2 - 10.1109/ITW.2012.6404704
DO - 10.1109/ITW.2012.6404704
M3 - Conference contribution
AN - SCOPUS:84873142358
SN - 9781467302234
T3 - 2012 IEEE Information Theory Workshop, ITW 2012
SP - 40
EP - 44
BT - 2012 IEEE Information Theory Workshop, ITW 2012
T2 - 2012 IEEE Information Theory Workshop, ITW 2012
Y2 - 3 September 2012 through 7 September 2012
ER -