Scheduling with privacy constraints

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.