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.
Let us repeat that an algorithm does not specify how the nodes synchronize, how they select each other to perform a common computation step. From the abstraction level of local computations, this underlying synchronization is seen as an implementation choice (dedicated procedures were designed to fit the various models, e.g. local elections @cite_14 and local rendezvous @cite_6 for starwise and pairwise interactions, respectively). A direct consequence is that the execution of an algorithm at this level may not be deterministic. Another consequence is that the characterization of conditions on the dynamics will additionally require assumptions on the synchronization -- we suggest later a generic progression hypothesis that serves this purpose. Note that the three algorithms provided in this paper rely on pairwise interactions, but the concepts and methodology involved apply to local computations in general.
@cite_14 @cite_6
2118991742 2088310932
Given a set of sensor nodes V where each node wants to broadcast a message to all its neighbors that are within a certain broadcasting range, the local broadcasting problem is to schedule all these requests in as few timeslots as possible. In this paper, assuming the more realistic physical interference model and no knowledge of the topology, we present three distributed local broadcasting algorithms where the first one is for the asynchronized model and the other two are for the synchronized model. Under the asynchronized model, nodes may join the execution of the protocol at any time and do not have access to a global clock, for which we give a distributed randomized algorithm with approximation ratio O(log2 n). This improves the state-of-the-art result given in [14] by a logarithmic factor. For the synchronized model where communications among nodes are synchronous and nodes can perform physical carrier sensing, we propose two distributed deterministic local broadcasting algorithms for synchronous and asynchronous node wakeups, respectively. Both algorithms have approximation ratio O(log n). Mobile agent computing is being used in fields as diverse as artificial intelligence, computational economics and robotics. Agents' ability to adapt dynamically and execute asynchronously and autonomously brings potential advantages in terms of fault-tolerance, flexibility and simplicity. This monograph focuses on studying mobile agents as modelled in distributed systems research and in particular within the framework of research performed in the distributed algorithms community. It studies the fundamental question of how to achieve rendezvous , the gathering of two or more agents at the same node of a network. Like leader election, such an operation is a useful subroutine in more general computations that may require the agents to synchronize, share information, divide up chores, etc. The work provides an introduction to the algorithmic issues raised by the rendezvous problem in the distributed computing setting. For the most part our investigation concentrates on the simplest case of two agents attempting to rendezvous on a ring network. Other situations including multiple agents, faulty nodes and other topologies are also examined. An extensive bibliography provides many pointers to related work not covered in the text. The presentation has a distinctly algorithmic, rigorous, distributed computing flavor and most results should be easily accessible to advanced undergraduate and graduate students in computer science and mathematics departments. Table of Contents: Models for Mobile Agent Computing Deterministic Rendezvous in a Ring Multiple Agent Rendezvous in a Ring Randomized Rendezvous in a Ring Other Models Other Topologies