Unifying synchronous and asynchronous message-passing models

We take a signi cant step toward unifying the synchronous, semi-synchronous, and asynchronous message-passing models of distributed computation. The key idea is the concept of a pseudosphere, anew combinatorial structure in which each process from a set of processes is independently assigned a value from a set of values. Pseudospheres have anumber of nice combinatorial properties, but their principal interest lies in the observation that the behavior of protocols in the three models can be characterized as simple unions of pseudospheres, where the exact structure of these unions is determined by the timing properties of the model. We use this pseudosphere construction to derive new and remarkably succinct proofs of bounds on consensus and k-set agreement in the asynchronous and synchronous models, as well as the rst lower bound on wait-free k-set agreement in the semi-synchronous model.