Simple and efficient local codes for distributed stable network construction

Michail, O ORCID: 0000-0002-6234-3960 and Spirakis, PG ORCID: 0000-0001-5396-3749 (2016) Simple and efficient local codes for distributed stable network construction. Distributed Computing, 29 (3). pp. 207-237.

This is the latest version of this item.

	Text dc16.pdf - Author Accepted Manuscript Available under License : See the attached licence file. Download (530kB)
	Text dc16.pdf - Submitted version Available under License : See the attached licence file. Download (530kB)

Official URL: https://link.springer.com/article/10.1007%2Fs00446...

Abstract

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 logk 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.

Item Type:	Article
Uncontrolled Keywords:	Distributed network construction, Stabilization, Homogeneous population, Distributed protocol, Interacting automata, Fairness, Random schedule, Structure formation, Self-organization
Depositing User:	Symplectic Admin
Date Deposited:	09 Oct 2020 12:37
Last Modified:	18 Jan 2023 23:52
DOI:	10.1007/s00446-015-0257-4
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3086399