Distributed Job Scheduling in Linear Networks

This paper aims at an existing distributed computing theoretical model, in which processors generate unit jobs independently and there is no global control and the communications of processors should spend time The job scheduling problem in linear networks is studied The balances of job processing and communications of processors are considered and a distributed algorithm is proposed without any global information and complicated operation, which has a performance ratio no more than 5 88 The lower bound is also studied It shows that there is no distributed algorithm whose approximation ratio is less than 1 16