research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleSimple and Efficient Local Codes for Distributed Stable Network Construction
Bibtex cite IDRACTI-RU1-2015-9
Journal Distributed Computing
Year published 2015
Month October
Pages 1-31
ISSN 0178-2770
Note Appeared Online
DOI 10.1007/s00446-015-0257-4
Keywords Distributed network construction,Stabilization,Homogeneous population,Distributed protocol,Interacting automata,Fairness,Random schedule,Structure formation,Self-organization
In this work, we study protocols so that populations of distributed processes can construct networks. In order to highlight the basic principles of distributed network construction, we keep the model minimal in all respects. In particular, we assume finite-state processes that all begin from the same initial state and all execute the same protocol. Moreover, we assume pairwise interactions between the processes that are scheduled by a fair adversary. In order to allow processes to construct networks, we let them activate and deactivate their pairwise connections. When two processes interact, the protocol takes as input the states of the processes and the state of their connection and updates all of them. Initially all connections are inactive and the goal is for the processes, after interacting and activating/deactivating connections for a while, to end up with a desired stable network. We give protocols (optimal in some cases) and lower bounds for several basic network construction problems such as spanning line, spanning ring, spanning star, and regular network. The expected time to convergence of our protocols is analyzed under a uniform random scheduler. Finally, we prove several universality results by presenting generic protocols that are capable of simulating a Turing Machine (TM) and exploiting it in order to construct a large class of networks. We additionally show how to partition the population into k supernodes, each being a line of log k nodes, for the largest such k. This amount of local memory is sufficient for the supernodes to obtain unique names and exploit their names and their memory to realize nontrivial constructions.
Michail, Othon
Spirakis, Paul
MS15-DC.pdf (main file)
Publication ID1082