Distributed cooperation during the absence of communication

This paper presents a study of a distributed cooperation problem under the assumption that processors may not be able to communicate for a prolonged time. The problem for n processors is defined in terms of t tasks that need to be performed efficiently and that are known to all processors. The results of this study characterize the ability of the processors to schedule their work so that when some processors establish communication, the wasted (redundant) work these processors have collectively performed prior to that time is controlled. The lower bound for wasted work presented here shows that for any set of schedules there are two processors such that when they complete t₁ and t₂ tasks respectively the number of redundant tasks is Ω(t₁t₂/t). For n = t and for schedules longer than √n, the number of redundant tasks for two or more processors must be at least 2. The upper bound on pairwise waste for schedules of length √n is shown to be 1. Our efficient deterministic schedule construction is motivated by design theory. To obtain linear length schedules, a novel deterministic and efficient construction is given. This construction has the property that pairwise wasted work increases gracefully as processors progress through their schedules. Finally our analysis of a random scheduling solution shows that with high probability pairwise waste is well behaved at all times: specifically, two processors having completed t₁ and t₂ tasks, respectively, are guaranteed to have no more than t₁t₂/t + A redundant tasks, where (formula presented).