Distributed Scheduling Taxonomy with Extended Computability Level Criteria

Dari PaloDozen

Bibliography: Budi, Eko M, Hermawan K. Dipojono, Distributed Scheduling Taxonomy with Extended Computability Level Criteria, International Seminar on Rural Information Technology, ITB, 2007


Resource sharing is one key issue in the rural next generation computing (r-NGC). In this system, a number of computational jobs submitted by many clients, should be distributed efficiently to the right servers that provide the computing resources. This requires a scheduling algorithm that carefully assigns the job to many servers (space-sharing) as well as assign the jobs to the time slots of a particular server (time-sharing). In recent years, many distributed scheduling algorithms have been developed. This paper presents a general taxonomy (classification) to support systematic selection of scheduling algorithms that would be applicable in the r-NGC environment.

The taxonomy of distributed scheduling based on the state-estimation and decision-making processes has been proposed (Rotithor 1994). The criterias of state-estimation include state estimator, information scope, dissemination strategy and dissemination instant. Meanwhile, the criteria of decision-making process are: decision-maker, initiator, and state transformation. This paper further extends the taxonomy by incorporating the computability level (Chomsky 1956) as the fourth criteria of the decicion-making process. This criteria clearly defines four classes of scheduling, namely:

  • Immediate Scheduling
  • Feasible Scheduling
  • Optimal Scheduling
  • Adaptive Scheduling

To clarify the idea, several known scheduling algorithms is reviewed and classified according to the extended taxonomy.

Keywords: distributed scheduling taxonomy, distributed scheduling algorithms, computability level

Makalah: Berkas:RICT2007-Distributed Scheduling Taxonomy.pdf

Kontributor: Mursito