Classical list scheduling is a very popular and efficient technique for scheduling jobs in parallel and distributed platforms. It is inherently centralized. However, with the increasing number of processors in new parallel platforms the cost for managing a single centralized list becomes too prohibitive. The overhead for distributing the work to the processors can not be ignored anymore. In such systems, each processor has only a local view of the work to execute.

The objective of this work is to study the extra cost that must be paid for distributing the computational load using list scheduling. More precisely, we prove that the time for scheduling a global workload composed of W unit tasks on m processors is equal to W/m with an additional factor in O(log W). The proof is based on the analysis of an adequate potential function which represents the load unbalance between the local works. We finally provide some experiments using a simulator that assess the tightness of the previous bound and give a helpful insight of the behaviour of the distributed list algorithm.