An incentive-based distributed mechanism for scheduling divisible loads in tree networks |
| |
Authors: | T.E. Carroll D. Grosu |
| |
Affiliation: | 1. Pacific Northwest National Laboratory, P.O Box 999 MSIN J4-45, 902 Battelle Boulevard, Richland, WA 99352, USA;2. Department of Computer Science, Wayne State University, 5057 Woodward Avenue, Detroit, MI 48202, USA |
| |
Abstract: | The underlying assumption of Divisible Load Scheduling (DLS) theory is that the processors composing the network are obedient, i.e., they do not “cheat” the scheduling algorithm. This assumption is unrealistic if the processors are owned by autonomous, self-interested organizations that have no a priori motivation for cooperation and they will manipulate the algorithm if it is beneficial to do so. In this paper, we address this issue by designing a distributed mechanism for scheduling divisible loads in tree networks, called DLS-T, which provides incentives to processors for reporting their true processing capacity and executing their assigned load at full processing capacity. We prove that the DLS-T mechanism computes the optimal allocation in an ex post Nash equilibrium. Finally, we simulate and study the mechanism under various network structures and processor parameters. |
| |
Keywords: | Divisible load scheduling Distributed systems Mechanism design Game theory |
本文献已被 ScienceDirect 等数据库收录! |
|