Skip to main content

Discovering valuations and enforcing truthfulness in a deadline-aware scheduler

Author(s): Huang, Zhe; Weinberg, S Matthew; Zheng, Liang; Joe-Wong, Carlee; Chiang, Mung

To refer to this page use:
Abstract: 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.
Publication Date: 2017
Citation: Huang, Zhe, S. Matthew Weinberg, Liang Zheng, Carlee Joe-Wong, and Mung Chiang. "Discovering valuations and enforcing truthfulness in a deadline-aware scheduler." In IEEE INFOCOM 2017-IEEE Conference on Computer Communications (2017): pp. 1-9. doi:10.1109/INFOCOM.2017.8056975
DOI: 10.1109/INFOCOM.2017.8056975
Pages: 1 - 9
Type of Material: Conference Article
Journal/Proceeding Title: IEEE INFOCOM 2017-IEEE Conference on Computer Communications
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.