We introduce the notion of a task for in nitely many processors and investigate necessary and su cient conditions for such a task to be wait{free solvable. A protocol that solves such a task must be uniform: Processors must produce a valid output even when there is no upper bound on the cardinality of the participating set. We extend the Asynchronous Computability Theorem of Herlihy and Shavit to uniform protocols. This entails a completely di erent approach to deal with complexes of in nite dimensions. Our characterization directly implies that the Immediate Snapshot task admits a uniform protocol. We match this result by providing a particular uniform protocol for Immediate Snapshot, and consequently for Renaming. We also describe a speci c task that is not uniformly solvable although every subtask for nitely many processors is solvable.
Wait-free solvability of tasks when there is no upper bound on the number of participating processes has also been investigated REF (see also [Gafni2002] ).
On Uniform Protocols