loading...
A Strategyproof Mechanism for Scheduling Divisible Loads in Distributed Systems
Universit? of Lille 1, France July 04-July 06
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPDC.2005.9The 4th International Symposium on Pa ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Daniel Grosu, Wayne State University
Thomas E. Carroll, Wayne State University
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 in recent years 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.
Citation:
Daniel Grosu, Thomas E. Carroll, "A Strategyproof Mechanism for Scheduling Divisible Loads in Distributed Systems," ispdc, pp.83-90, The 4th International Symposium on Parallel and Distributed Computing (ISPDC'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.