Michail, Othon 
ORCID: 0000-0002-6234-3960 and Spirakis, Paul G ORCID: 0000-0001-5396-3749
(2017)
Connectivity preserving network transformers.
THEORETICAL COMPUTER SCIENCE, 671.
pp. 36-55.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
Transformers-main.pdf - Unspecified Download (1MB) |
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/application_atom+xml.png) |
Atom XML (admin)
2017-05-12T11:12:23Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T12:12:10Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T13:12:05Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T14:12:06Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T15:12:07Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T16:12:07Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T17:12:01Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T18:12:07Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T19:12:05Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T20:12:07Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T21:12:04Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T22:12:08Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T23:16:05Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T00:12:46Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T01:12:17Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T02:12:07Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T03:12:09Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T04:17:04Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T05:12:04Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T06:12:08Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T07:12:10Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T08:12:10Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T09:12:11Z.atom - Unspecified Download (0B) |
Abstract
The Population Protocol model is a distributed model that concerns systems of very weak computational entities that cannot control the way they interact. The model of Network Constructors is a variant of Population Protocols capable of (algorithmically) constructing abstract networks. Both models are characterized by a fundamental inability to terminate. In this work, we investigate the minimal strengthenings of the latter that could overcome this inability. Our main conclusion is that initial connectivity of the communication topology combined with the ability of the protocol to transform the communication topology plus a few other local and realistic assumptions are sufficient to guarantee not only termination but also the maximum computational power that one can hope for in this family of models. The technique is to transform any initial connected topology to a less symmetric and detectable topology without ever breaking its connectivity during the transformation. The target topology of all of our transformers is the spanning line and we call Terminating Line Transformation the corresponding problem. We first study the case in which there is a pre-elected unique leader and give a time-optimal protocol for Terminating Line Transformation. We then prove that dropping the leader without additional assumptions leads to a strong impossibility result. In an attempt to overcome this, we equip the nodes with the ability to tell, during their pairwise interactions, whether they have at least one neighbor in common. Interestingly, it turns out that this local and realistic mechanism is sufficient to make the problem solvable. In particular, we give a very efficient protocol that solves Terminating Line Transformation when all nodes are initially identical. The latter implies that the model computes with termination any symmetric predicate computable by a Turing Machine of space $\Theta(n^2)$.
| Item Type: | Article |
|---|---|
| Additional Information: | publisher: Elsevier articletitle: Connectivity preserving network transformers journaltitle: Theoretical Computer Science articlelink: http://dx.doi.org/10.1016/j.tcs.2016.02.040 content_type: article copyright: © 2016 Elsevier B.V. All rights reserved. |
| Uncontrolled Keywords: | Population protocol, Network construction, Network transformation, Dynamic topology, Termination, Continuous connectivity, Random scheduler, Turing Machine simulation |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 11 Apr 2016 09:45 |
| Last Modified: | 16 Dec 2022 01:53 |
| DOI: | 10.1016/j.tcs.2016.02.040 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3000149 |
Dimensions
Dimensions
