Strategyproof Mechanisms for Scheduling Divisible Loads in Bus-Networked Distributed Systems

摘要

The scheduling of arbitrarily divisible loads on a distributed system is studied by Divisible Load Theory (DLT). DLT has the underlying assumption that the processors will not cheat. In the real world this assumption is unrealistic as the processors are owned and operated by autonomous, rational organizations that have no textit{a priori} motivation for cooperation. Consequently, they will manipulate the algorithms if it benefits them to do so. In this work we propose strategyproof mechanisms for scheduling divisible loads on three types of bus connected distributed systems. These mechanisms provide incentives to the processors to obey the prescribed algorithms and to truthfully report their parameters, leading to an efficient load allocation and execution.