Resource scheduling for local computer systems with a multiaccess network

Abstract

A study of resource scheduling based on a distributed state-dependent discipline for a system of processors connected by a local multiaccess network is made. The scheduling problem is reduced to the identification of the extremum from a set of physically dispersed random numbers. The authors propose an efficient method of utilizing the primitive operations of collision detection and broadcast in multiaccess networks to efficiently distribute status information and to identify the extremum. The optimal performance of extremum identification is found to be constant and on the average independent of the number of contending processors. The protocol can be implemented either by minor hardware modification of existing multiaccess-network interfaces or in software.