Optimal scheduling for disconnected cooperation

We consider a distributed environment consisting of n processors that need to perform t tasks. We assume that communication is initially unavailable and that processors begin work in isolation. At some unknown point of time an unknown collection of processors may establish communication. Before processors begin communication they execute tasks in the order given by their schedules. Our goal is to schedule work of isolated processors so that when communication is established for the first time, the number of redundantly executed tasks is controlled. We quantify worst case redundancy as a function of processor advancements through their schedules. In this work we refine and simplify an extant deterministic construction for schedules with n < t, and we develop a new analysis of its waste. The new analysis shows that for any pair of schedules, the number of redundant tasks can be controlled for the entire range of t tasks. Our new result is asymptotically optimal: the tails of these schedules are within a 1 + O(n^-1/4) factor of the lower bound. We also present two new deterministic constructions one for t ≥ n, and the other for t ≥ n^3/2, which substantially improve pairwise waste for all prefixes of length t/√n, and offer near optimal waste for the tails of the schedules. Finally, we present bounds for waste of any collection of k ≥ 2 processors for both deterministic and randomized constructions.