Discovering valuations and enforcing truthfulness in a deadline-aware scheduler

Zhe Huang, S. Matthew Weinberg, Liang Zheng, Carlee Joe-Wong, Mung Chiang

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

8 Scopus citations


A cloud computing cluster equipped with a deadline-aware job scheduler faces fairness and efficiency challenges when greedy users falsely advertise the urgency of their jobs. Penalizing such untruthfulness without demotivating users from using the cloud service calls for advanced mechanism design techniques that work together with deadline-aware job scheduling. We propose a Bayesian incentive compatible pricing mechanism based on matching by replica-surrogate valuation functions. User valuations can be discovered by the mechanism, even when the users themselves do not fully understand their own valuations. Furthermore, users who are charged a Bayesian incentive compatible price have no reason to lie about the urgency of their jobs. The proposed mechanism achieves multiple desired truthful properties such as Bayesian incentive compatibility and ex-post individual rationality. We implement the proposed pricing mechanism. Through experiments in a Hadoop cluster with real-world datasets, we show that our prototype is capable of suppressing untruthful behavior from users.

Original languageEnglish (US)
Title of host publicationINFOCOM 2017 - IEEE Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509053360
StatePublished - Oct 2 2017
Event2017 IEEE Conference on Computer Communications, INFOCOM 2017 - Atlanta, United States
Duration: May 1 2017May 4 2017

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Other2017 IEEE Conference on Computer Communications, INFOCOM 2017
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Discovering valuations and enforcing truthfulness in a deadline-aware scheduler'. Together they form a unique fingerprint.

Cite this