A simple algorithmic characterization of uniform solvability

The Herlihy-Shavit (HS) conditions characterizing the solvability of asynchronous tasks over n processors have been a milestone in the development of the theory of distributed computing. Yet, they were of no help when researcher sought algorithms that do not depend on n. To help in this pursuit we investigate the uniform solvability of an infinite uniform sequence of tasks T₀, T₁, T₂,..., where T_i is a task over processors p₀, p₁,...,p_i, and T_i extends T_i-1. We say that such a sequence is uniformly solvable if there exit protocols to solve each T_i and the protocol for T_i extends the protocol for T_i-1. This paper establishes that although each T_i may be solvable, the uniform sequence is not necessarily uniformly solvable. We show this by proposing a novel uniform sequence of solvable tasks and proving that the sequence is not amenable to a uniform solution. We then extend the HS conditions for a task over n processors, to uniform solvability in a natural way. The technique we use to accomplish this is to generalize the alternative algorithmic proof, by Borowsky and Gafni, of the HS conditions, by showing that the infinite uniform sequence of task of Immediate Snapshots is uniformly solvable. A side benefit of the technique is a widely applicable methodology for the development of uniform protocols.