Distributed scheduling for disconnected cooperation

Ability to cooperate on common tasks in a distributed setting is key to solving a broad range of computation problems ranging from distributed search such as SETI to distributed simulation and multi-agent collaboration. In such settings there exists a trade-off between computation and communication: both resources must be managed to decrease redundant computation and to ensure efficient computational progress. This paper deals with scheduling issues for distributed collaboration. Specifically, we examine the extreme situation where initially collaboration must occur without communication. That is, we consider the extent to which efficient collaboration is possible if all resources are directed to computation at the expense of communication. The results summarized here precisely characterize the ability of distributed agents to collaborate on a known collection of independent tasks by means of local scheduling decisions that require no communication and that achieve low redundancy in task executions. Such scheduling solutions exhibit an interesting connection between the distributed collaboration problem and the design theory. The lower bounds presented here along with the randomized and deterministic schedule constructions show the limitations on such low-redundancy cooperation and show that schedules with near-optimal redundancy can be efficiently constructed by processors working in isolation. The work of G. Malewicz was done when he was a Ph.D. student at the University of Connecticut, and in part during a visit to the Specification and Algorithm Research Department, AT&T Shannon Lab, and the Supercomputing Technologies Group, Massachusetts Institute of Technology. Parts of this article appeared in a preliminary form in the Proceedings of the 14th International Symposium on Distributed Computing 24], Springer LNCS Vol. 1914, pp. 119–133, in the Proceedings of the 8th International Colloquium on Structural Information and Communication Complexity 23], and the doctoral thesis of the first author.