William B. Day
The Consensus Scheduling Model (CSM) is introduced as a way to accommodate negotiation in over-constrained, distributed scheduling problems. The CSM is appropriate for negotiation among a group of peers and is also applicable to a manager that must balan ce conflicting views of its workers. The distributed scheduling algorithm that is used selects a candidate from the priority list of resource requests and inserts that candidate into the evolving timetable. Two protocols are required. The minimax proto col assures equitable power among the peers. The bumping protocol allows reactive scheduling by using a request’s total worth to dictate when a new request can seize a previously assigned resource. A request’s total worth is the sum of its priority valu e, its ordering value, and any bonus points received by previous negotiations. Three styles of negotiation are examined: unilateral, verbose, and periodic.