Abstract
To an increasing extent, large-scale information processing is a distributed phenomenon. As the trend in computing moves further towards distributed networks of powerful workstations and information servers, we see the growing importance of solutions to dynamic distributed scheduling problems. In these domains, resource providers are distributed both geographically and bureaucratically, so that no central authority can dictate a global schedule. Resource consumers are also distributed: tasks arrive at different locations according to arrival functions that are at best stochastically predictable. In this paper, we describe a distributed constraint-based scheduling system that adjusts task distribution and execution times through the negotiation of contracts, using a refinement of the Contract Net protocol. By combining the minimal-commitment capabilities of constraint-based scheduling with the distributed coordination features of contracting, this system responds flexibly to dynamic variations in load balance and unpredictable task arrivals. Large-scale simulations show significant performance benefits to using powerful scheduling methods in the determination of contract negotiation bids. These results can be used to improve the performance of distributed computing systems cooperating to process large-scale shareable tasks.