Simple and efficient local codes for distributed stable network construction

Michail, Othon; Spirakis, Paul G.
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. Copyright is held by the owner/author(s). Publication rights licensed to ACM.
Research areas:
Year:
2016
Type of Publication:
Article
Keywords:
Distributed network construction; Distributed protocol; Fairness; Homogeneous population; Interacting automata; Random schedule; Self-organization; Stabilization; Structure formation
Journal:
Distributed Computing
Volume:
29
Number:
3
Pages:
207-237
ISSN:
0178-2770
DOI:
10.1007/s00446-015-0257-4
Hits: 1303

We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy.

  I accept cookies from this site.
EU Cookie Directive Module Information