Query scheduling and site selection algorithms for a cube-connected multicomputer system

Query scheduling and site selection algorithms for read-only queries on a cube-connected multicomputer are presented. An architecture model for the system is provided, and a site-selection algorithm that determines where to execute the upcoming operation sequence is developed. The query trees of queries entering the system are converted into operation sequence trees. Operation sequences belonging to a query are queued until the query is initiated. Two query selection policies are presented. A simulation comparing the two policies is described, and the simulation results are discussed. Scheduling restrictions that guarantee the avoidance of deadlock in both algorithms are presented