Dissecting Distributed Coordination

. This paper derives necessary and sufficient communication for distributed applications that perform certain actions uniformly in asynchronous systems. We show there is an essential structure of information flow in any solution to Uniform Coordination, suggesting message-minimal solutions. We show it is necessary for processes to conspire against each other to make progress, and we show this conspiracy requires processes to stop communicating with each other. This, we show, renders Uniform Coordination insensitive to channel delivery guarantees. We introduce the notion of exempting processes from coordinating. We show that `primary partition' behavior (Isis) arises from the desire to make exempt an process indistinguishable from a crashed process. Defining weaker exemptions for distributed coordination problems gives rise to many problems solvable in asynchronous systems as well as in systems that partition. Keywords: Agreement, asynchronous, exemption, failures, uniformity. 1 Introdu..