Wait-Free Implementations in Message-Passing Systems

We study the round complexity of problems in a synchronous, messagepassing system with crash failures. We show that if processors start in order-equivalent states, then a logarithmic number of rounds is both necessary and sufficient for them to reach order-inequivalent states. These upper and lower bounds are significant because they establish a complexity threshold below which no nontrivial problem can be solved, but at which certain nontrivial problems do have solutions. This logarithmic lower bound implies a matching lower bound for a variety of decision tasks and concurrent object implementations. In particular, we examine two nontrivial problems for which this lower bound is tight: the strong renaming task, and a wait-free increment register implementation. For each problem, we present anontrivial algorithm that halts in O(log c) rounds, where c is the number of participating processors