Towards a Unified Approach to (In)Decision: Routing, Games, Circuits, Consensus, and Beyond

Full textClick to download.
AuthorsAaron D. Jaggard
Michael Schapira
Rebecca N. Wright


In this paper, we explore a unified treatment of the difficulty of reaching a decision in constrained distributed computing environments in which there is a lack of global coordination or knowledge. We show a general impossibility result for a broad class of decision protocols. Importantly, our impossibility result holds, in particular, for "asynchronous, distributed, historyless computation", in which each computational node's selection of actions only depends on the current actions of other nodes, even under the assumption that no node can be faulty. We consider implications of our impossibility result across a wide variety of interesting and timely applications in which historyless computation arises: Internet interdomain routing protocols, congestion-control protocols, diffusion of technologies in social networks, dynamics in games, and asynchronous circuits. We also show that Fischer, Lynch, and Paterson's classical result showing the impossibility of consensus in the presence of faults can be easily derived from our general result. The power and generality of our approach suggest that it may be useful for further unifying the constraints imposed by local knowledge, leading to a deeper understanding of the boundary of what is and is not possible in a range of computing environments.

Back to publications
Back to previous page