DocumentCode :
3455168
Title :
A Strategyproof Mechanism for Scheduling Divisible Loads in Distributed Systems
Author :
Grosu, Daniel ; Carroll, Thomas E.
Author_Institution :
Dept. of Comput. Sci., Wayne State Univ., Detroit, MI
fYear :
2005
fDate :
4-6 July 2005
Firstpage :
83
Lastpage :
90
Abstract :
An important scheduling problem is the one in which there are no dependencies between tasks and the tasks can be of arbitrary size. This is known as the divisible load scheduling problem and was studied extensively resulting in a cohesive theory called divisible load theory (DLT). In this paper, we augment the existing divisible load theory with incentives. We develop a strategyproof mechanism for scheduling divisible loads in distributed systems assuming a bus type interconnection and a linear cost model for the processors. The mechanism provides incentives to processors such that it is beneficial for them to report their true processing power and process the assigned load using their full processing capacity. We define the strategyproof mechanism and prove its properties. We simulate and study the implementation of the mechanism on systems characterized by different parameters
Keywords :
processor scheduling; bus type interconnection; distributed systems; divisible load scheduling; divisible load theory; Computational modeling; Computer science; Concurrent computing; Cost accounting; Distributed computing; Power system interconnection; Power system modeling; Processor scheduling; Protocols; Scheduling algorithm;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Computing, 2005. ISPDC 2005. The 4th International Symposium on
Conference_Location :
Lille
Print_ISBN :
0-7695-2434-6
Type :
conf
DOI :
10.1109/ISPDC.2005.9
Filename :
1609957
Link To Document :
بازگشت