Name
Abstract | ||
|---|---|---|
We work on an extension of the Population Protocol model of Angluin et al. that allows edges of the communication graph, G, to have states that belong to a constant size set. In this extension, the so called Mediated Population Protocol model (MPP), both uniformity and anonymity are preserved. We study here a simplified version of MPP in order to capture MPP's ability to stably compute graph properties. To understand properties of the communication graph is an important step in almost any distributed system. We prove that any graph property is not computable if we allow disconnected communication graphs. As a result, we focus on studying (at least) weakly connected communication graphs only and give several examples of computable properties in this case. To do so, we also prove that the class of computable properties is closed under complement, union and intersection operations. Node and edge parity, bounded out-degree by a constant, existence of a node with more incoming than outgoing neighbors, and existence of some directed path of length at least k = O(1) are some examples of properties whose computability is proven. Finally, we prove the existence of symmetry in two specific communication graphs and, by exploiting this, we prove that there exists no protocol, whose states eventually stabilize, to determine whether G contains some directed cycle of length 2. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-16023-3_21 | SSS |
Keywords | Field | DocType |
communication graph,weakly connected communication graph,stably decidable graph language,constant size set,graph property,computable property,edge parity,important step,specific communication graph,population protocol model,mediated population protocol,bounded out-degree,distributed system | Discrete mathematics,Comparability graph,Line graph,Graph property,Forbidden graph characterization,Computer science,Algorithm,Directed graph,Null graph,Pathwidth,Complement graph | Conference |
Volume | ISSN | ISBN |
6366 | 0302-9743 | 3-642-16022-0 |
Citations | PageRank | References |
7 | 0.53 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ioannis Chatzigiannakis | 1 | 1238 | 121.01 |
| Othon Michail | 2 | 197 | 18.27 |
| Paul G. Spirakis | 3 | 2222 | 299.05 |