|
|
|
| Abstract Title:
|
| Incentive-Centered Design for Scheduling Divisible Loads in Distributed Computing Systems
|
| Graduate Student Presenter:
|
Thomas E. Carroll
|
| Name of the Author(s) and Affiliation(s):
|
Thomas E. Carroll, Dept. of Computer Science, Wayne State University; Daniel Grosu, Dept. of Computer Science, Wayne State University
|
|
Many scientific computing problems require processing large data sets which are first partitioned into fractions and then assigned and processed by several processors in a distributed computing system. Divisible load theory (DLT) studies the scheduling of such loads in a distributed computing system. Standard DLT assumes that the processors are obedient and that they follow the system designer's specification. But in the real world, the processors can be owned and operated by autonomous organizations that are self-interested, welfare-maximizing, and have no a priori motivation for cooperation. If incentives exist, the organizations will manipulate the scheduling algorithms, resulting in inefficiencies and overall suboptimal performance. The system and the algorithms must be specifically designed to provide incentives to the participants to follow the algorithm and report their true parameters to the scheduler. Designing such systems is the focus of Incentive-Centered Design (ICD), the science of designing systems that align participants' incentives with the system's objectives. In this work we use ICD methods to design a mechanism that schedules divisible loads in a distributed system comprising processors interconnected by a bus network. Each processor reports its speed to the mechanism, which then computes the schedule and payments. The mechanism pays the processors for the work performed on its behalf. The schedule and payments are constructed such that the processors truthfully report their speeds to the mechanism. Since the processors truthfully disclose their speeds, the mechanism can determine an optimal schedule which guarantees the efficient execution of the application.
|
|
|
