Besides the complexity in time or in number of messages, a common approach for analyzing distributed algorithms is to look at the assumptions they make on the underlying network. We investigate this question from the perspective of network dynamics. In particular, we ask how a given property on the evolution of the network can be rigorously proven as necessary or sufficient for a given algorithm. The main contribution of this paper is to propose the combination of two existing tools in this direction: local computations by means of graph relabelings, and evolving graphs. Such a combination makes it possible to express fine-grained properties on the network dynamics, then examine what impact those properties have on the execution at a precise, intertwined, level. We illustrate the use of this framework through the analysis of three simple algorithms, then discuss general implications of this work, which include (i) the possibility to compare distributed algorithms on the basis of their topological requirements, (ii) a formal hierarchy of dynamic networks based on these requirements, and (iii) the potential for mechanization induced by our framework, which we believe opens a door towards automated analysis and decision support in dynamic networks.
Distributed algorithms can be expressed using a variety of communication models ( message passing, mailboxes, shared memory). Although a vast majority of algorithms is designed in one of these models -- predominantly the message passing model --, the very fact that one of them is chosen implies that the obtained results ( positive or negative characterizations and associated proofs) are limited to the scope of this model. This problem of diversity among formalisms and results, already pointed out twenty years ago in @cite_17 , led researchers to consider higher abstractions when studying fundamental properties of distributed systems.
@cite_17
2084316739
Emulators that translate algorithms from the shared-memory model to two different message-passing models are presented. Both are achieved by implementing a wait-free, atomic, single-writer multi-reader register in unreliable, asynchronous networks. The two message-passing models considered are a complete network with processor failures and an arbitrary network with dynamic link failures. These results make it possible to view the shared-memory model as a higher-level language for designing algorithms in asynchronous distributed systems. Any wait-free algorithm based on atomic, single-writer multi-reader registers can be automatically emulated in message-passing systems, provided that at least a majority of the processors are not faulty and remain connected. The overhead introduced by these emulations is polynomial in the number of processors in the system. Immediate new results are obtained by applying the emulators to known shared-memory algorithms. These include, among others, protocols to solve the following problems in the message-passing model in the presence of processor or link failures: multi-writer multi-reader registers, concurrent time-stamp systems, l -exclusion, atomic snapshots, randomized consensus, and implementation of data structures.