Mechanisms with Monitoring for Truthful RAM Allocation
Annamária Kovács, Ulrich Meyer, Carmine Ventre · Lecture notes in computer science · 2015
Novel algorithmic ideas for big data have not been accompanied by advances in the way central memory is allocated to concurrently running programs. Commonly, RAM is poorly managed since the programs’ trade offs between speed of execution and RAM consumption are ignored. This trade off is, however, well known to the programmers. We adopt mechanism design tools to truthfully elicit this (multidimensional) information with the aim of designing more clever RAM allocation algorithms. We introduce a novel paradigm wherein programs are bound to overbidding declarations of their running times. We show the limitations of this paradigm in the absence of transfers and prove how to leverage waiting times, as a currency, to obtain optimal money burning mechanisms for the makespan. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.