Scheduling of differential privacy

Last updated on Jul 14, 2021
PDF Code

In this project, we enabled Kubernetes/Kubeflow to manage differential privacy (DP) budget among jobs in ML workloads. In particular, our contributions are

  1. Characterize the privacy resource as dynamically-arriving, non-replenishable private blocks,
  2. Develop a new scheduling algorithm of DPF (Dominant Private block Fairness),
  3. Study game-theoretical properties of DPF.

My contributions are

  • Reframed the problem and enabled to decouple privacy scheduling from compute resource scheduling, proposed the original DPF algorithm, gave initial rigorous proofs of its game theoretical properties.
  • Derived a weaker condition for envy-freeness property, proposed alternative DP scheduling algorithms.
  • Proposed the key technique to adapt DPF algorithm to Rényi DP. Namely, RDP allocation curve only need to be partially bounded by unlocked RDP budget curve during scheduling.
  • Designed, implemented and fine-tuned a discrete-event simulator.
  • Algorithm prototyping and microbenchmarking - evaluated various scheduling algorithms via simulation experiment, investigated their tradeoffs.
Systems Security Current
Tao Luo
Tao Luo
CS PhD Student

My interests lie in performance and security aspects in distributed systems/networking.

Related

Publications

Privacy Budget Scheduling
For workloads operating on sensitive user data, privacy loss should be carefully orchestrated to enforce a global bound on personal data leakage. This paper presented PrivateKube, an extension to the Kubernetes workload orchestrator that adds differential privacy budget as a new native resource to be managed alongside traditional compute resources. PrivateKube incorporates a novel scheduling algorithm, DPF, the first one suitable for the unique characteristics of the privacy resource, including its all-or-nothing utility and non-replenishable nature. We show that DPF has desirable theoretical properties, outperforms baseline scheduling algorithms, and that native integration of privacy into Kubernetes can facilitate reuse of existing tools to better manage this scarce resource.
Tao Luo, Mingen Pan, Pierre Tholoniat, Asaf Cidon, Roxana Geambasu, Mathias Lecuyer
PDF Code Project Video