Publications of Othon Michail

This is a compressed list with links to abstracts and pdfs. Also available as a BibTex file.

All papers on this site may be downloaded for research or personal use only. The copyright for each paper is owned either by the publisher of the journal or conference proceedings in which the paper is published, or by the authors of the paper.

Monographs

• New Models for Population Protocols,
  with Ioannis Chatzigiannakis and Paul Spirakis.
  Synthesis Lectures on Distributed Computing Theory,
  Nancy Lynch edt., Morgan & Claypool Publishers, 2011.
  [bib]

  @Book{ MCS11,
  	title = "New Models for Population Protocols",
  	booktitle = "New Models for Population Protocols",
  	author = "Othon Michail and Ioannis Chatzigiannakis and Paul G. Spirakis",
  	publisher = "Morgan \& Claypool",
  	series = "N. A. Lynch (Ed), Synthesis Lectures on Distributed Computing Theory",
  	year = "2011",
  	editor = "Nancy A. Lynch",
  }
     

Book Chapters

• Connectivity Preserving Network Transformers,
  with Paul Spirakis.
  In Emergent Computation,
  Edited by A. Adamatzky, pages 337-359, Springer, 2016.
  [PDF] [bib] [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 \emph{fundamental inability to terminate}. In this work, we investigate the minimal strengthenings of the latter model that could overcome this inability. Our main conclusion is that \emph{initial connectivity of the communication topology} combined with the ability of the protocol to \emph{transform the communication topology} and the ability of a node to \emph{detect when its degree is equal to a small constant}, plus either a \emph{unique leader} or the ability of \emph{detecting common neighbors}, are sufficient to guarantee not only \emph{termination} but also the \emph{maximum computational power that one can hope for in this family of models}. In particular, the model, under these minimal assumptions, \emph{computes with termination any symmetric predicate computable by a Turing Machine of space $\Theta(n^2)$.

  @InBook{ MS16e,
  	title = "Emergent Computation",
  	author = "Othon Michail and Paul G. Spirakis",
  	editor = "A. Adamatzky",
  	publisher = "Springer",
  	chapter = "Connectivity Preserving Network Transformers",
      pages = "337--359",
  	year = "2016"
  }
     

• Computing in Dynamic Networks,
  with Ioannis Chatzigiannakis and Paul Spirakis.
  In Computational Network Theory: Theoretical Foundations and Applications,
  First Edition, Edited by M. Dehmer, F. Emmert-Streib, and S. Pickl, pages 173-218,
  Wiley-VCH Verlag GmbH & Co. KGaA, 2015.
  [PDF] [bib] [Abstract]

  In this chapter, our focus is on computational network analysis from a theoretical point of view. In particular, we study the \emph{propagation of influence and computation in dynamic distributed computing systems}. We focus on a \emph{synchronous message passing} communication model with bidirectional links. Our network dynamicity assumption is a \emph{worst-case dynamicity} controlled by an adversary scheduler, which has received much attention recently. We first study the fundamental \emph{naming} and \emph{counting} problems (and some variations) in networks that are \emph{anonymous}, \emph{unknown}, and possibly dynamic. Network dynamicity is modeled here by the \emph{1-interval connectivity model}, in which communication is synchronous and a (worst-case) adversary chooses the edges of every round subject to the condition that each instance is connected. We then replace this quite strong assumption by minimal \emph{temporal connectivity} conditions. These conditions only require that \emph{another causal influence occurs within every time-window of some given length}. Based on this basic idea we define several novel metrics for capturing the speed of information spreading in a dynamic network. We present several results that correlate these metrics. Moreover, we investigate \emph{termination criteria} in networks in which an upper bound on any of these metrics is known. We exploit these termination criteria to provide efficient (and optimal in some cases) protocols that solve the fundamental \emph{counting} and \emph{all-to-all token dissemination} (or \emph{gossip}) problems. Finally, we propose another model of worst-case temporal connectivity, called \emph{local communication windows}, that assumes a fixed underlying communication network and restricts the adversary to allow communication between local neighborhoods in every time-window of some fixed length. We prove some basic properties and provide a protocol for counting in this model.

  @InBook{ MCS15,
  	title = "Computational Network Theory: Theoretical Foundations and Applications, First Edition",
  	author = "Othon Michail and Ioannis Chatzigiannakis and Paul G. Spirakis",
  	editor = "M. Dehmer and F. Emmert-Streib and S. Pickl",
  	publisher = "Wiley-VCH Verlag GmbH \& Co. KGaA",
  	chapter = "Computing in Dynamic Networks",
          pages = "173--218",
  	year = "2015"
  }
     

• Population Protocols and Related Models,
  with Ioannis Chatzigiannakis and Paul Spirakis.
  In Theoretical Aspects of Distributed Computing in Sensor Networks,
  S. Nikoletseas and J. Rolim edt., Springer-Verlag, 2010.
  Remark: The editors decided to include only P. Spirakis in the author index.
  My name and the name of I. Chatzigiannakis appear in the abstract.
  [PDF] [bib] [Abstract]

  This is a joint work with Ioannis Chatzigiannakis and Othon Michail. We discuss here the population protocol model and most of its well-known extensions. The population protocol model aims to represent sensor networks consisting of tiny computational devices with sensing capabilities that follow some unpredictable and uncontrollable mobility pattern. It adopts a minimalistic approach and, thus, naturally computes a quite restricted class of predicates and exhibits almost no fault tolerance. Most recent approaches make extra realistic and implementable assumptions, in order to gain more computational power and/or speedup the time to convergence and/or improve fault tolerance. In particular, the mediated population protocol model, the community protocol model, and the PALOMA model, which are all extensions of the population protocol model, are thoroughly discussed. Finally, the inherent difficulty of verifying the correctness of population protocols that run on complete communication graphs is revealed, but a promising algorithmic solution is presented.

  @InBook{ CMS10-2,
  	title = "Theoretical Aspects of Distributed Computing in Sensor Networks",
  	author = "Paul G. Spirakis",
  	editor = "S. Nikoletseas and J. Rolim",
  	publisher = "Springer-Verlag",
  	chapter = "Population Protocols and Related Models",
  	year = "2010"
  }
     

Journals and Conferences

• Centralised Connectivity-Preserving Transformations by Rotation: 3 Musketeers for All Orthogonal Convex Shapes,
  with Matthew Connor.
  In 18th International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS),
  pages 60-76, Potsdam, Germany, September 2022.
  [ALGOSENSORS] [Presentation] [Arxiv] [bib] [Abstract]

  We study a model of programmable matter systems consisting of $n$ devices lying on the cells of a 2-dimensional square grid, which are able to perform the minimal mechanical operation of rotating around each other. The goal is to transform an initial shape of devices A into a target shape B. We are interested in characterising the class of shapes which can be transformed into each other in such a scenario, under the additional constraint of maintaining global connectivity at all times. This was one of the main problems left open by $[$Michail \emph{et al.}, JCSS'19$]$. Note that the considered question is about structural feasibility of transformations, which we exclusively deal with via centralised constructive proofs. Distributed solutions are left for future work and form an interesting research direction. Past work made some progress for the special class of colour-consistent \emph{nice} shapes. We here consider the class of \emph{orthogonal convex shapes}, where for any two nodes $u, v$ in a horizontal or vertical line on the grid, there is no empty cell between $u$ and $v$. We develop a generic centralised transformation and prove that, for any pair $A$, $B$ of colour-consistent orthogonal convex shapes, it can transform $A$ into $B$. In light of the existence of \emph{blocked} shapes in the considered class, we use a minimal 3-node \emph{seed} (additional nodes placed at the start) to trigger the transformation. The running time of our transformation is an optimal $O(n^2)$ sequential moves, where $n=|A|=|B|$. We leave as an open problem the existence of a universal connectivity-preserving transformation with a small seed. Our belief is that the techniques developed in this paper might prove useful to answer this.

  @inproceedings{CM22,
    title = {Centralised Connectivity-Preserving Transformations by Rotation: 3 Musketeers for All Orthogonal Convex Shapes},
    author = {Connor, Matthew and Michail, Othon},
    booktitle = {18th International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS)},
    pages = {60--76},
    year = {2022},
    url = {https://link.springer.com/chapter/10.1007/978-3-031-22050-0_5},
    doi = {https://doi.org/10.1007/978-3-031-22050-0_5},
    publisher = {Springer}
  }
     

• The Complexity of Growing a Graph,
  with George Mertzios, George Skretas, Paul Spirakis, and Michail Theofilatos.
  In 18th International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS),
  pages 123-137, Potsdam, Germany, September 2022.
  [ALGOSENSORS] [Presentation] [Arxiv] [bib] [Abstract]

  We study a new algorithmic process of graph growth. The process starts from a single initial vertex $u_0$ and operates in discrete time-steps, called \emph{slots}. In every slot $t\geq 1$, the process updates the current graph instance to generate the next graph instance $G_t$. The process first sets $G_t = G_{t-1}$. Then, for every $u\in V(G_{t-1})$, it adds at most one new vertex $u^\prime$ to $V(G_{t})$ and adds the edge $uu^\prime$ to $E(G_{t})$ alongside any subset of the edges $\{vu^\prime\;|\; v\in V(G_{t-1})$ is at distance at most $d-1$ from $u$ in $G_{t-1}\}$, for some integer $d\geq 1$ fixed in advance. The process completes slot $t$ after removing any (possibly empty) subset of edges from $E(G_{t})$. Removed edges are called \emph{excess edges}. $G_t$ is the graph \emph{grown} by the process after $t$ slots. The goal of this paper is to investigate the algorithmic and structural properties of this process of graph growth. \noindent\textbf{Graph Growth Problem:} Given a graph family $F$, we are asked to design a \emph{centralized} algorithm that on any input \emph{target graph} $G\in F$, will output such a process growing $G$, called a \emph{growth schedule} for $G$. Additionally, the algorithm should try to minimize the total number of slots $k$ and of excess edges $\ell$ used by the process. We show that the most interesting case is when $d = 2$ and that there is a natural trade-off between $k$ and $\ell$. We begin by investigating growth schedules of $\ell=0$ excess edges. On the positive side, we provide polyno\-mial-time algorithms that decide whether a graph has growth schedules of $k=\log n$ or $k=n-1$ slots. Along the way, interesting connections to cop-win graphs are being revealed. On the negative side, we establish strong hardness results for the problem of determining the minimum number of slots required to grow a graph with zero excess edges. In particular, we show that the problem (i) is NP-complete and (ii) for any $\varepsilon>0$, cannot be approximated within $n^{\frac{1}{3}-\varepsilon}$, unless P~=~NP. We then move our focus to the other extreme of the $(k,\ell)$-spectrum, to investigate growth schedules of (poly)logarithmic slots. We show that trees can be grown in a polylogarithmic number of slots using linearly many excess edges, while planar graphs can be grown in a logarithmic number of slots using $O(n\log n)$ excess edges. We also give lower bounds on the number of excess edges, when the number of slots is fixed to $\log n$.

  @inproceedings{MMSST22,
    title = {The Complexity of Growing a Graph},
    author = {Mertzios, George B. and Michail, Othon and Skretas, George and Spirakis, Paul G. and Theofilatos, Michail},
    booktitle = {18th International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS)},
    pages = {123--137},
    year = {2022},
    url = {https://link.springer.com/chapter/10.1007/978-3-031-22050-0_9},
    doi = {https://doi.org/10.1007/978-3-031-22050-0_9},
    publisher = {Springer}
  }
     

• On Geometric Shape Construction via Growth Operations,
  with Nada Almalki.
  In 18th International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS),
  pages 1-17, Potsdam, Germany, September 2022.
  [ALGOSENSORS] [Presentation] [Arxiv] [bib] [Abstract]

  In this work, we investigate novel algorithmic growth processes. In particular, we propose three growth operations, \emph{full doubling}, \emph{RC doubling} and \emph{doubling}, and explore the algorithmic and structural properties of their resulting processes under a geometric setting. In terms of modeling, our system runs on a 2-dimensional grid and operates in discrete time-steps. The process begins with an initial shape $S_I=S_0$ and, in every time-step $t \geq 1$, by applying (in parallel) one or more growth operations of a specific type to the current shape-instance $S_{t-1}$, generates the next instance $S_t$, always satisfying $|S_t| > |S_{t-1}|$. Our goal is to characterize the classes of shapes that can be constructed in $O(\log n)$ or polylog $n$ time-steps and determine whether a final shape $S_F$ can be constructed from an initial shape $S_I$ using a finite sequence of growth operations of a given type, called a \emph{constructor of $S_F$}. For \emph{full doubling}, in which, in every time-step, every node generates a new node in a given direction, we completely characterize the structure of the class of shapes that can be constructed from a given initial shape. For \emph{RC doubling}, in which complete columns or rows double, our main contribution is a linear-time centralized algorithm that for any pair of shapes $S_I$, $S_F$ decides if $S_F$ can be constructed from $S_I$ and, if the answer is yes, returns an $O(\log n)$-time-step constructor of $S_F$ from $S_I$. For the most general \emph{doubling} operation, where up to individual nodes can double, we show that some shapes cannot be constructed in sub linear time-steps and give two universal constructors of any $S_F$ from a singleton $S_I$, which are efficient (i.e., up to polylogarithmic time-steps) for large classes of shapes. Both constructors can be computed by polynomial-time centralized algorithms for any shape $S_F$.

  @inproceedings{AM22,
    title = {On Geometric Shape Construction via Growth Operations},
    author = {Almalki, Nada and Michail, Othon},
    booktitle = {18th International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS)},
    pages = {1--17},
    year = {2022},
    url = {https://link.springer.com/chapter/10.1007/978-3-031-22050-0_1},
    doi = {https://doi.org/10.1007/978-3-031-22050-0_1},
    publisher = {Springer}
  }
     

• Centralised Connectivity-Preserving Transformations for Programmable Matter: A Minimal Seed Approach,
  with Matthew Connor and Igor Potapov.
  Theoretical Computer Science, Special Issue on ALGOSENSORS'21, 936, 77-91, Elsevier, 2022.
  doi: 10.1016/j.tcs.2022.09.016, Open Access
  A previous version appeared in 17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks
  (ALGOSENSORS), pages 45-60, September 2021.
  [TCS] [ALGOSENSORS] [Presentation] [Arxiv] [bib] [Abstract]

  We study a model of programmable matter systems consisting of $n$ devices lying on a 2-dimensional square grid which are able to perform the minimal mechanical operation of rotating around each other. The goal is to transform an initial shape $A$ into a target shape $B$. We investigate the class of shapes which can be constructed in such a scenario under the additional constraint of maintaining global connectivity at all times. We focus on the scenario of transforming \emph{nice shapes}, a class of shapes consisting of a central line $L$ where for all nodes $u$ in $S$ either $u \in L$ or $u$ is connected to $L$ by a line of nodes perpendicular to $L$. We prove that by introducing a minimal 3-node seed it is possible for the canonical shape of a line of $n$ nodes to be transformed into a nice shape of $n-1$ nodes. We use this to show that a 4-node seed enables the transformation of nice shapes of size $n$ into any other nice shape of size $n$ in $O(n^2)$ time. We leave as an open problem the expansion of the class of shapes which can be constructed using such a seed to include those derived from nice shapes.

  @article{CMP22,
    author = {Connor, Matthew and Michail, Othon and Potapov, Igor},
    title = {Centralised Connectivity-Preserving Transformations for Programmable Matter: A Minimal Seed Approach},
    journal = {Theoretical Computer Science},
    volume = {936},
    pages = {77--91},
    year = {2022},
    issn = {0304-3975},
    doi = {https://doi.org/10.1016/j.tcs.2022.09.016},
    url = {https://www.sciencedirect.com/science/article/pii/S0304397522005527},
    publisher = {Elsevier}
  }   
     
  @inproceedings{CMP21,
    title = {Centralised Connectivity-Preserving Transformations for Programmable Matter: A Minimal Seed Approach},
    author = {Connor, Matthew and Michail, Othon and Potapov, Igor},
    booktitle = {17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS)},
    pages = {45--60},
    year = {2021},
    url = {https://link.springer.com/chapter/10.1007/978-3-030-89240-1_4},
    doi = {https://doi.org/10.1007/978-3-030-89240-1_4},
    publisher = {Springer}
  }
     

• Distributed Transformations of Hamiltonian Shapes based on Line Moves,
  with Abdullah Almethen and Igor Potapov.
  Theoretical Computer Science, Special Issue on ALGOSENSORS'21, 942, 142-168, Elsevier, 2023.
  doi: 10.1016/j.tcs.2022.11.029, Open Access
  A previous version appeared in 17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks
  (ALGOSENSORS), pages 1-16, September 2021.
  [TCS] [ALGOSENSORS] [Presentation] [Arxiv] [bib] [Abstract]

  We consider a discrete system of $n$ simple indistinguishable devices, called \emph{agents}, forming a \emph{connected} shape $S_I$ on a two-dimensional square grid. Agents are equipped with a linear-strength mechanism, called a \emph{line move}, by which an agent can push a whole line of consecutive agents in one of the four cardinal directions in a single time-step. We study the problem of transforming an initial shape $S_I$ into a given target shape $S_F$ via a finite sequence of line moves in a distributed model, where each agent can observe the states of nearby agents in a Moore neighbourhood. We develop the first distributed connectivity-preserving transformation that exploits line moves. The transformation solves the \emph{line formation problem}. That is, starting from any shape $S_I$ whose \emph{associated graph} contains a Hamiltonian path known to them, the agents can form a final straight line $S_L$. The complexity of the transformation is $O(n \log_2 n)$ moves, which is asymptotically equivalent to that of the best-known centralised transformations.

  @article{AMP23,
    author = {Almethen, Abdullah and Michail, Othon and Potapov, Igor},
    title = {Distributed Transformations of Hamiltonian Shapes based on Line Moves},
    journal = {Theoretical Computer Science},
    volume = {942},
    pages = {142--168},
    year = {2023},
    issn = {0304-3975},
    doi = {https://doi.org/10.1016/j.tcs.2022.11.029},
    url = {https://www.sciencedirect.com/science/article/pii/S0304397522007058},
    publisher = {Elsevier}
  }   
     
  @inproceedings{AMP21,
    title = {Distributed Transformations of Hamiltonian Shapes based on Line Moves},
    author = {Almethen, Abdullah and Michail, Othon and Potapov, Igor},
    booktitle = {17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS)},
    pages = {1--16},
    year = {2021},
    url = {https://link.springer.com/chapter/10.1007/978-3-030-89240-1_1},
    doi = {https://doi.org/10.1007/978-3-030-89240-1_1},
    publisher = {Springer}
  }
     

• Beyond Rings: Gathering in 1-Interval Connected Graphs,
  with Paul Spirakis and Michail Theofilatos.
  Parallel Processing Letters, 31(4), 2150020:1-2150020:31, World Scientific, 2021.
  doi: 10.1142/S0129626421500201
  [PPL] [Arxiv] [bib] [Abstract]

  We examine the problem of gathering k >= 2 agents (or multi-agent rendezvous) in dynamic graphs which may change in every round. We consider a variant of the 1-interval connectivity model in which all instances (snapshots) are always connected spanning subgraphs of an underlying graph, not necessarily a clique. The agents are identical and not equipped with explicit communication capabilities, and are initially arbitrarily positioned on the graph. The problem is for the agents to gather at the same node, not fixed in advance. We first show that the problem becomes impossible to solve if the underlying graph has a cycle. In light of this, we study a relaxed version of this problem, called weak gathering, where the agents are allowed to gather either at the same node, or at two adjacent nodes. Our goal is to characterize the class of 1-interval connected graphs and initial configurations in which the problem is solvable, both with and without homebases. On the negative side we show that when the underlying graph contains a spanning bicyclic subgraph and satisfies an additional connectivity property, weak gathering is unsolvable, thus we concentrate mainly on unicyclic graphs. As we show, in most instances of initial agent configurations, the agents must meet on the cycle. This adds an additional difficulty to the problem, as they need to explore the graph and recognize the nodes that form the cycle. We provide a deterministic algorithm for the solvable cases of this problem that runs in O(n^2 + nk) number of rounds.

  @article{MST21b,
    title = {Beyond Rings: Gathering in 1-Interval Connected Graphs},
    author = {Michail, Othon and Spirakis, Paul and Theofilatos, Michail},
    journal = {Parallel Processing Letters},
    volume = {31},
    number = {4},
    pages = {2150020:1--2150020:31},
    year = {2021},
    url = {https://www.worldscientific.com/doi/10.1142/S0129626421500201},
    doi = {10.1142/S0129626421500201},
    publisher = {World Scientific}
  }
     

• On the Distributed Construction of Stable Networks in Polylogarithmic Parallel Time,
  with Matthew Connor and Paul Spirakis.
  Information, Special Issue on Distributed Systems and Mobile Computing, 12(6), 254, MDPI, June 2021.
  doi: 10.3390/info12060254, Open Access.
  [INFORMATION] [Arxiv] [bib] [Abstract]

  We study the class of networks, which can be created in polylogarithmic parallel time by network constructors: groups of anonymous agents that interact randomly under a uniform random scheduler with the ability to form connections between each other. Starting from an empty network, the goal is to construct a stable network that belongs to a given family. We prove that the class of trees where each node has any k \geq 2 children can be constructed in O(log n) parallel time with high probability. We show that constructing networks that are k-regular is \Omega(n) time, but a minimal relaxation to (l,k)-regular networks, where l = k − 1, can be constructed in polylogarithmic parallel time for any fixed k, where k > 2. We further demonstrate that when the finite-state assumption is relaxed and k is allowed to grow with n, then k = log log n acts as a threshold above which network construction is, again, polynomial time. We use this to provide a partial characterisation of the class of polylogarithmic time network constructors.

  @article{CMS21,
    title = {On the Distributed Construction of Stable Networks in Polylogarithmic Parallel Time},
    author = {Connor, Matthew and Michail, Othon and Spirakis, Paul},
    journal = {Information},
    volume = {12},
    number = {6},
    article-number = {254},
    year = {2021},
    url = {https://www.mdpi.com/2078-2489/12/6/254},
    doi = {10.3390/info12060254},
    publisher = {MDPI}
  }
     

• Distributed Computation and Reconfiguration in Actively Dynamic Networks,
  with George Skretas and Paul Spirakis.
  Distributed Computing, 35(2), 185-206, Springer, April 2022.
  doi: 10.1007/s00446-021-00415-5, Open Access.
  A previous version appeared in 39th ACM Symposium on Principles of Distributed Computing (PODC),
  pages 448-457, August 2020.
  [DC] [PODC] [Video-Presentation] [Slides] [Arxiv] [bib] [Abstract]

  We study here systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network reconfiguration to carry out a given task. Also, the distributed task itself may now require a global reconfiguration from a given initial network $G_s$ to a target network $G_f$ from a desirable family of networks. To formally capture costs associated with creating and maintaining connections, we define three edge-complexity measures: the total edge activations, the maximum activated edges per round, and the maximum activated degree of a node. We give (poly)log($n$) time algorithms for the task of transforming any $G_s$ into a $G_f$ of diameter (poly)log($n$), while minimizing the edge-complexity. Our main lower bound shows that $\Omega(n)$ total edge activations and $\Omega(n/\log n)$ activations per round must be paid by any algorithm (even centralized) that achieves an optimum of $\Theta(\log n)$ rounds. We give three distributed algorithms for our general task. The first runs in $O(\log n)$ time, with at most $2n$ active edges per round, a total of $O(n\log n)$ edge activations, a maximum degree $n-1$, and a target network of diameter 2. The second achieves bounded degree by paying an additional logarithmic factor in time and in total edge activations. It gives a target network of diameter $O(\log n)$ and uses $O(n)$ active edges per round. Our third algorithm shows that if we slightly increase the maximum degree to polylog($n$) then we can achieve $o(\log^2 n)$ running time.

  @article{MSS22,
    author = {Michail, Othon and Skretas, George and Spirakis, Paul G},
    title = {Distributed Computation and Reconfiguration in Actively Dynamic Networks},
    journal = {Distrib. Comput.},
    volume = {35},
    number = {2},
    pages = {185--206},
    year = {2022},
    issn = {1432-0452},
    doi = {https://doi.org/10.1007/s00446-021-00415-5},
    url = {https://link.springer.com/article/10.1007/s00446-021-00415-5},
    publisher = {Springer Nature}
  }   
     
  @inproceedings{MSS20,
    title = {Distributed Computation and Reconfiguration in Actively Dynamic Networks},
    author = {Michail, Othon and Skretas, George and Spirakis, Paul G},
    booktitle = {39th ACM Symposium on Principles of Distributed Computing (PODC)},
    pages = {448--457},
    year = {2020},
    url = {https://dl.acm.org/doi/10.1145/3382734.3405744},
    doi = {10.1145/3382734.3405744},
    publisher = {ACM}
  }
     

• On Efficient Connectivity-Preserving Transformations in a Grid,
  with Abdullah Almethen and Igor Potapov.
  Theoretical Computer Science, 898, 132-148, Elsevier, 2022.
  doi: 10.1016/j.tcs.2021.11.004
  A previous version appeared in 16th International Symposium on Algorithms and Experiments
  for Wireless Sensor Networks (ALGOSENSORS), pages 76-91, September 2020.
  [TCS] [ALGOSENSORS] [Presentation] [Arxiv] [bib] [Abstract]

  We consider a discrete system of $n$ devices lying on a 2-dimensional square grid and forming an initial connected shape $S_I$. Each device is equipped with a linear-strength mechanism which enables it to move a whole line of consecutive devices in a single time-step. We study the problem of transforming $S_I$ into a given connected target shape $S_F$ of the same number of devices, via a finite sequence of \emph{line moves}. Our focus is on designing \emph{centralised} transformations aiming at \emph{minimising the total number of moves} subject to the constraint of \emph{preserving connectivity} of the shape throughout the course of the transformation. We first give very fast connectivity-preserving transformations for the case in which the \emph{associated graphs} of $ S_I $ and $ S_F $ are isomorphic to a Hamiltonian line. In particular, our transformations make $ O(n \log n $) moves, which is asymptotically equal to the best known running time of connectivity-breaking transformations. Our most general result is then a connectivity-preserving \emph{universal transformation} that can transform any initial connected shape $ S_I $ into any target connected shape $ S_F $, through a sequence of $O(n\sqrt{n})$ moves.

  @article{AMP22,
    author = {Almethen, Abdullah and Michail, Othon and Potapov, Igor},
    title = {On Efficient Connectivity-Preserving Transformations in a Grid},
    journal = {Theoretical Computer Science},
    volume = {898},
    pages = {132--148},
    year = {2022},
    issn = {0304-3975},
    doi = {https://doi.org/10.1016/j.tcs.2021.11.004},
    url = {https://www.sciencedirect.com/science/article/abs/pii/S0304397521006514},
    publisher = {Elsevier}
  }
    
  @inproceedings{AMP20b,
    title = {On Efficient Connectivity-Preserving Transformations in a Grid},
    author = {Almethen, Abdullah and Michail, Othon and Potapov, Igor},
    booktitle = {16th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS)},
    pages = {76-91},
    year = {2020},
    url = {https://link.springer.com/chapter/10.1007%2F978-3-030-62401-9_6},
    doi = {https://doi.org/10.1007/978-3-030-62401-9_6},
    publisher = {Springer}
  }
     

• Fault Tolerant Network Constructors,
  with Paul Spirakis and Michail Theofilatos.
  In 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS),
  pages 243-255, Pisa, Italy, October 2019.
  [SSS] [Presentation] [Arxiv] [bib] [Abstract]

  In this work, we consider adversarial crash faults of nodes in the network constructors model $[$Michail and Spirakis, 2016$]$. We first show that, without further assumptions, the class of graph languages that can be (stably) constructed under crash faults is non-empty but small. In particular, if an unbounded number of crash faults may occur, we prove that (i) the only constructible graph language is that of spanning cliques and (ii) a strong impossibility result holds even if the size of the graphs that the protocol outputs in populations of size $n$ need only grow with $n$ (the remaining nodes being \emph{waste}). When there is a finite upper bound $f$ on the number of faults, we show that it is impossible to construct any \emph{non-hereditary} graph language and leave as an interesting open problem the \emph{hereditary case}. On the positive side, by relaxing our requirements we prove that: (i) permitting linear waste enables to construct on $n/(2f)-f$ nodes, any graph language that is constructible in the fault-free case, (ii) \emph{partial constructibility} (i.e., not having to generate all graphs in the language) allows the construction of a large class of graph languages. We then extend the original model with a minimal form of \emph{fault notifications}. Our main result here is a \emph{fault tolerant universal constructor}: We develop a fault-tolerant protocol for \emph{spanning line} and use it to simulate a linear-space Turing Machine $M$. This allows a fault-tolerant construction of any graph accepted by $M$ in linear space, with waste $min\{n/2 + f(n), \; n\}$, where $f(n)$ is the number of faults in the execution. We then prove that increasing the permissible waste to $min {2n/3 + f(n), \; n\}$ allows the construction of graphs accepted by an $O(n^2)$ space Turing Machine, which is asymptotically the maximum simulation space that we can hope for in this model. Finally, we show that logarithmic local memories can be exploited for a no-waste fault-tolerant simulation of any such protocol.

  @inproceedings{MST19,
    title = {Fault Tolerant Network Constructors},
    author = {Michail, Othon and Spirakis, Paul G and Theofilatos, Michail},
    booktitle = {21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)},
    pages = {243--255},
    year = {2019},
    url = {https://link.springer.com/chapter/10.1007/978-3-030-34992-9_19},
    doi = {10.1007/978-3-030-34992-9_19},,
    publisher = {Springer International Publishing}
  }
     

• Pushing Lines Helps: Efficient Universal Centralised Transformations for Programmable Matter,
  with Abdullah Almethen and Igor Potapov.
  Theoretical Computer Science, 830-831, 43-59, Elsevier, August 2020.
  doi: 10.1016/j.tcs.2020.04.026
  A previous version appeared in 15th International Symposium on Algorithms and Experiments
  for Wireless Sensor Networks (ALGOSENSORS), pages 41-59, Munich, Germany, September 2019.
  [TCS] [ALGOSENSORS] [Presentation] [Arxiv] [bib] [Abstract]

  In this paper, we study a discrete system of entities residing on a two-dimensional square grid. Each entity is modelled as a node occupying a distinct cell of the grid. The set of all $n$ nodes forms initially a connected shape $A$. Entities are equipped with a linear-strength pushing mechanism that can push a whole line of entities, from 1 to $n$, in parallel in a single time-step. A target connected shape $B$ is also provided and the goal is to \emph{transform} $A$ into $B$ via a sequence of line movements. Existing models based on local movement of individual nodes, such as rotating or sliding a single node, can be shown to be special cases of the present model, therefore their (inefficient, $\Theta(n^2)$) \emph{universal transformations} carry over. Our main goal is to investigate whether the parallelism inherent in this new type of movement can be exploited for efficient, i.e., sub-quadratic worst-case, transformations. As a first step towards this, we restrict attention solely to centralised transformations and leave the distributed case as a direction for future research. Our results are positive. By focusing on the apparently hard instance of transforming a diagonal $A$ into a straight line $B$, we first obtain transformations of time $O(n\sqrt{n})$ without and with preserving the connectivity of the shape throughout the transformation. Then, we further improve by providing two $O(n\log n)$-time transformations for this problem. By building upon these ideas, we first manage to develop an $O(n\sqrt{n})$-time universal transformation. Our main result is then an $ O(n \log n) $-time universal transformation. We leave as an interesting open problem a suspected $\Omega(n\log n)$-time lower bound.

  @article{AMP20,
    title = {Pushing Lines Helps: Efficient Universal Centralised Transformations for Programmable Matter},
    author = {Almethen, Abdullah and Michail, Othon and Potapov, Igor},
    journal = {Theoretical Computer Science},
    volume = {830--831},
    pages = {43--59},
    year = {2020},
    url = {https://www.sciencedirect.com/science/article/pii/S0304397520302437},
    doi = {10.1016/j.tcs.2020.04.026},
    publisher = {Elsevier}
  }
     

• Brief Announcement: Exact Size Counting in Uniform Population Protocols in Nearly Logarithmic Time,
  with David Doty, Mahsa Eftekhari, Paul Spirakis and Michail Theofilatos.
  In 32nd International Symposium on Distributed Computing (DISC),
  pages 46:1-46:3, New Orleans, Louisiana, USA, October 2018.
  [DISC] [Arxiv] [bib] [Abstract]

  We study population protocols: networks of anonymous agents whose pairwise interactions are chosen uniformly at random. The size counting problem is that of calculating the exact number n of agents in the population, assuming no leader (each agent starts in the same state). We give the first protocol that solves this problem in sublinear time. The protocol converges in O(log n log log n) time and uses O(n^60) states (O(1) + 60 log n bits of memory per agent) with probability 1-O((log log n)/n). The time to converge is also O(log n log log n) in expectation. Crucially, unlike most published protocols with omega(1) states, our protocol is uniform: it uses the same transition algorithm for any population size, so does not need an estimate of the population size to be embedded into the algorithm.

  @inproceedings{DEMST18,
    title = {Brief Announcement: Exact Size Counting in Uniform Population Protocols in Nearly Logarithmic Time},
    author = {Doty, David and Eftekhari, Mahsa and Michail, Othon and Spirakis, Paul G and Theofilatos, Michail},
    booktitle = {32nd International Symposium on Distributed Computing (DISC)},
    pages = {46:1--46:3},
    year = {2018},
    url = {http://drops.dagstuhl.de/opus/volltexte/2018/9835/},
    doi = {10.4230/LIPIcs.DISC.2018.46},
    publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}
  }
  
     

• Simple and Fast Approximate Counting and Leader Election in Populations,
  with Paul Spirakis and Michail Theofilatos.
  Information and Computation, SSS 2018 special issue, 285, 104698, Elsevier, May 2022.
  doi: 10.1016/j.ic.2021.104698
  A previous version appeared in 20th International Symposium on Stabilization, Safety, and Security of
  Distributed Systems (SSS), pages 154-169, Tokyo, Japan, November 2018.
  Also as: Brief Announcement: Fast Approximate Counting and Leader Election in Populations,
  in 25th International Colloquium on Structural Information and Communication Complexity
  (SIROCCO), pages 38-42, Ma'ale HaHamisha, Israel, June 2018.
  [IC] [SSS] [Presentation] [SIROCCO] [Arxiv] [bib] [Abstract]

  We study the problems of leader election and population size counting for \emph{population protocols}: networks of finite-state anonymous agents that interact randomly under a uniform random scheduler. We provide simple protocols for approximate counting of the size of the population and for leader election. We show a protocol for leader election that terminates in $O(\frac{\log^2{n}}{\log{m}})$ parallel time, where $1 \leq m \leq n$ is a parameter, using $O(\max\{m,\log n\})$ states. By adjusting the parameter $m$ between a constant and $n$, we obtain a single leader election protocol whose time and space can be smoothly traded off between $O(\log^2 n)$ to $O(\log n)$ time and $O(\log n)$ to $O(n)$ states. We also give a protocol which provides an upper bound $\hat{n}$ of the size $n$ of the population, where $\hat{n}$ is at most $n^a$ for some constant $a>1$. This protocol assumes the existence of a unique leader in the population and stabilizes in $\Theta{(\log{n})}$ parallel time, using constant number of states in every node, except from the unique leader which is required to use $\Theta{(\log^2{n})}$ states.

  @article{MST21,
    author = {Michail, Othon and Spirakis, Paul G and Theofilatos, Michail},
    title = {Simple and Fast Approximate Counting and Leader Election in Populations},
    journal = {Information and Computation},
    volume = {285},
    pages = {104698},
    year = {2022},
    issn = {0890-5401},
    doi = {10.1016/j.ic.2021.104698},
    url = {https://www.sciencedirect.com/science/article/abs/pii/S0890540121000134},
    publisher = {Elsevier}
  }   
     
  @inproceedings{MST18,
    title = {Simple and Fast Approximate Counting and Leader Election in Populations},
    author = {Michail, Othon and Spirakis, Paul G and Theofilatos, Michail},
    booktitle = {20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)},
    pages = {154--169},
    year = {2018},
    url = {https://link.springer.com/chapter/10.1007%2F978-3-030-03232-6_11},
    doi = {10.1007/978-3-030-03232-6_11},
    publisher = {Springer International Publishing}
  
     

• Elements of the Theory of Dynamic Networks,
  with Paul Spirakis.
  Communications of the ACM, 61(2), pages 72-81, ACM, 2018. doi: 10.1145/3156693
  [CACM definitive] [CACM author-accepted] [bib] [Abstract]

  Elements of the Theory of Dynamic Networks: The challenge of computing in a highly dynamic environment. A dynamic network is a network that changes with time. Nature, society, and the modern communications landscape abound with examples. Molecular interactions, chemical reactions, social relationships and interactions in human and animal populations, transportation networks, mobile wireless devices, and robot collectives form only a small subset of the systems whose dynamics can be naturally modeled and analyzed by some sort of dynamic network. Though many of these systems have always existed, it was not until recently the need for a formal treatment that would consider time as an integral part of the network has been identified. Computer science is leading this major shift, mainly driven by the advent of low-cost wireless communication devices and the development of efficient wireless communication protocols.

  @article{MS18,
    title = {Elements of the Theory of Dynamic Networks},
    author = {Michail, Othon and Spirakis, Paul G},
    journal = {Communications of the ACM},
    volume = {61},
    number = {2},
    pages = {72--81},
    year = {2018},
    publisher = {ACM}
  }
     

  
  
  
  
  
• On the Transformation Capability of Feasible Mechanisms for Programmable Matter,
  with George Skretas and Paul Spirakis.
  Journal of Computer and System Sciences, 102, 18-39, Elsevier, June 2019.
  doi: 10.1016/j.jcss.2018.12.001
  A previous version appeared in 44th International Colloquium on Automata, Languages and
  Programming (ICALP), pages 136:1-136:15, Warsaw, Poland, July 2017.
  [JCSS] [ICALP] [Presentation] [Arxiv] [bib] [Abstract]

  In this work, we study theoretical models of \emph{programmable matter} systems. The systems under consideration consist of spherical modules, that are kept together by magnetic or electrostatic forces and are able to perform two minimal mechanical operations (or movements): \emph{rotate} around a neighbor and \emph{slide} over a line. In terms of modeling, there are $n$ nodes arranged in a 2-dimensional grid that form some initial \emph{shape}. The goal is for the initial shape $A$ to \emph{transform} to some target shape $B$ by a sequence of movements. Most of the paper focuses on \emph{transformability} questions, meaning whether it is in principle feasible to transform a given shape to another. We first consider the case in which only rotation is available to the nodes. Our main result is that deciding whether two given shapes $A$ and $B$ can be transformed to each other, is in $\rem{P}$. We then insist on rotation only and impose the restriction that the nodes must maintain global connectivity throughout the transformation. We prove that the corresponding transformability question is in $\rem{PSPACE}$ and study the problem of determining the minimum \emph{seeds} that can make feasible, otherwise infeasible transformations. Next we allow both rotations and slidings and prove universality: any two connected shapes $A,B$ of the same number of nodes can be transformed to each other without breaking connectivity. The worst-case number of movements of the generic strategy is $\Theta(n^2)$. We improve this to $O(n)$ parallel time by a pipelining strategy, and prove optimality of both by matching lower bounds. We next turn our attention to distributed transformations. The nodes are now distributed processes able to perform communicate-compute-move rounds. We provide distributed algorithms for a general type of transformation.

  @article{MSS18,
    author = {Michail, Othon and Skretas, George and Spirakis, Paul G},
    title = {On the Transformation Capability of Feasible Mechanisms for Programmable Matter},
    journal = {Journal of Computer and System Sciences},
    volume = {102},
    pages = {18--39},
    year = {2018},
    issn = {0022-0000},
    doi = {10.1016/j.jcss.2018.12.001},
    url = {http://www.sciencedirect.com/science/article/pii/S0022000018300436},
    publisher = {Elsevier}
  }
     
  @inproceedings{MSS17,
    title={On the Transformation Capability of Feasible Mechanisms for Programmable Matter},
    author={Michail, Othon and Skretas, George and Spirakis, Paul G},
    booktitle={44th International Colloquium on Automata, Languages and Programming (ICALP)},
    pages={136:1--136:15},
    year={2017},
    url={https://doi.org/10.4230/LIPIcs.ICALP.2017.136},
    doi={10.4230/LIPIcs.ICALP.2017.136},
    publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}
  }
     

• Network Constructors: A Model for Programmable Matter,
  with Paul Spirakis.
  In 43rd International Conference on Current Trends in Theory and Practice of Computer Science
  (SOFSEM), pages 15-34, Lero-Limerick, Ireland, January 2017.
  [SOFSEM] [Presentation] [bib] [Abstract]

  We discuss recent theoretical models for programmable matter operating in a dynamic environment. In the basic \emph{Network Constructors} model, all devices are finite automata, begin from the same initial state, execute the same protocol, and can only interact in pairs. The interactions are scheduled by a \emph{fair} (or uniform random) scheduler, in the spirit of \emph{Population Protocols}. When two devices interact, the protocol takes as input their states and the state of the connection between them (\emph{on}/\emph{off}) and updates all of them. Initially all connections are \emph{off}. The goal of such protocols is to eventually construct a desired stable network, induced by the edges that are \emph{on}. We present protocols and lower bounds for several basic network construction problems and also universality results. We next highlight minimal strengthenings of the model, that can be exploited by appropriate network-transformation protocols in order to achieve \emph{termination} and the \emph{maximum computational power} that one can hope for in this family of models. Finally, we discuss a more applied version of these abstract models, enriched with geometric constraints, aiming at capturing some first physical restrictions in potential future programmable matter systems operating in dynamic environments.

  @inproceedings{MS17b,
    title = {Network Constructors: A Model for Programmable Matter},
    author = {Michail, Othon and Spirakis, Paul G},
    booktitle = {Proceedings of the 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)},
    year = {2017},
    location = {Lero-Limerick, Ireland},
    isbn = {978-3-319-51963-0},
    pages = {15--34},
    url = {http://link.springer.com/chapter/10.1007/978-3-319-51963-0_3},
    doi = {10.1007/978-3-319-51963-0_3},
    publisher = {Springer International Publishing}
  }
     

• How Many Cooks Spoil the Soup?,
  with Paul Spirakis.
  Distributed Computing, 31(6), 455-469, Springer, November 2018.
  doi: 10.1007/s00446-017-0317-z, Open Access.
  A previous version appeared in
  23rd International Colloquium on Structural Information and Communication Complexity
  (SIROCCO), pages 3-18, Helsinki, Finland, July 2016.
  [DC] [SIROCCO] [Presentation] [Arxiv] [bib] [Abstract]

  In this work, we study the following basic question: \emph{``How much parallelism does a distributed task permit?''} Our definition of \emph{parallelism} (or \emph{symmetry}) here is not in terms of speed, but in terms of identical \emph{roles} that processes have at the same time in the execution. For example, we may ask: \emph{``Can a given task be solved by a protocol that always has at least two processes in the same role at the same time?''} (i.e., by a protocol that never elects a \emph{unique leader}). We choose to initiate this study in population protocols, a very simple model that not only allows for a straightforward definition of what a role is, but also encloses the challenge of isolating the properties that are due to the protocol from those that are due to the \emph{adversary scheduler}, who controls the interactions between the processes. In particular, we define the role of a process at a given time to be equivalent to the \emph{state} of the process at that time. Moreover, we isolate the symmetry that is due to the protocol (\emph{inherent symmetry}) by focusing on those schedules that maximize symmetry for that protocol and observing how much symmetry breaking the protocol is forced to achieve in order to solve the problem. To allow for such \emph{symmetry maximizing} schedules we consider \emph{parallel schedulers} that in every step may select a whole collection of pairs of nodes (up to a perfect matching) to interact and not just a single pair. Based on these definitions of symmetric computation, we (i) give a \emph{partial characterization} of the set of predicates on input assignments that can be \emph{stably computed with maximum symmetry}, i.e., $\Theta(N_{min})$, where $N_{min}$ is the minimum multiplicity of a state in the initial configuration, and (ii) we turn our attention to the remaining predicates (that have some essentially different properties) and prove a \emph{strong impossibility result} for the \emph{parity} predicate: the inherent symmetry of any protocol that stably computes it is \emph{upper bounded by a constant that depends on the size of the protocol}. The latter immediately generalizes to a subset of the predicates that are \emph{not closed under doubling}.

  @article{MS17d,
   author = {Michail, Othon and Spirakis, Paul G}, 
   title = {How Many Cooks Spoil the Soup?},
   journal = {Distributed Computing},
   volume = {31},
   number = {6},
   pages = {455--469},
   year = {2018},
   issn = {0178-2770},
   doi = {https://doi.org/10.1007/s00446-017-0317-z},
   url = {https://link.springer.com/article/10.1007/s00446-017-0317-z},
   publisher = {Springer Berlin Heidelberg}
  }
  
     

• Connectivity Preserving Network Transformers,
  with Paul Spirakis.
  Theoretical Computer Science (TCS), Special Issue on the Theory of Self-Assembly, 671, 36-55,
  Elsevier, 2017. doi: 10.1016/j.tcs.2016.02.040
  [TCS] [Arxiv] [bib] [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 \emph{fundamental inability to terminate}. In this work, we investigate the minimal strengthenings of the latter model that could overcome this inability. Our main conclusion is that \emph{initial connectivity of the communication topology} combined with the ability of the protocol to \emph{transform the communication topology} and the ability of a node to \emph{detect when its degree is equal to a small constant}, plus either a \emph{unique leader} or the ability of \emph{detecting common neighbors}, are sufficient to guarantee not only \emph{termination} but also the \emph{maximum computational power that one can hope for in this family of models}. The technique of our protocols is to transform any initial connected topology to a \emph{less symmetric} (that can serve as a large ordered memory) and \emph{detectable} (that the protocol can determine its successful construction) topology \emph{without ever breaking its connectivity} during the transformation. The target topology of all of our transformers is the \emph{spanning line} and we call \emph{Terminating Line Transformation} the corresponding problem. We first study the case in which there is a pre-elected \emph{unique leader} and give a \emph{time-optimal protocol for Terminating Line Transformation}. We then prove that dropping the leader without additional assumptions leads to a \emph{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 \emph{very efficient protocol} that solves Terminating Line Transformation when all nodes are initially identical. The latter implies the aforementioned strong characterization: \emph{the model, under a few minimal assumptions, computes with termination any symmetric predicate computable by a Turing Machine of space $\Theta(n^2)$.}

  @article{MS17a,
    title={Connectivity Preserving Network Transformers},
    author={Michail, Othon and Spirakis, Paul G},
    journal={Theoretical Computer Science},
    volume={671},
    pages={36--55},
    year={2017},
    issn={0304-3975},
    doi={http://dx.doi.org/10.1016/j.tcs.2016.02.040},
    url={http://www.sciencedirect.com/science/article/pii/S0304397516002024},
    publisher={Elsevier}
  }
     

• An Introduction to Temporal Graphs: An Algorithmic Perspective.
  Internet Mathematics, 12(4), 239-280, Taylor & Francis, June 2016.
  A previous version appeared in
  Algorithms, Probability, Networks, and Games - Scientific Papers and Essays Dedicated to
  Paul G. Spirakis on the Occasion of His 60th Birthday, pages 308-343, LNCS, Springer, 2015.
  [IM] [APNG] [bib] [Abstract]

  A \emph{temporal graph} is, informally speaking, a graph that changes with time. When time is discrete and only the relationships between the participating entities may change and not the entities themselves, a temporal graph may be viewed as a sequence $G_1,G_2\ldots,G_l$ of static graphs over the same (static) set of nodes $V$. Though static graphs have been extensively studied, for their temporal generalization we are still far from having a concrete set of structural and algorithmic principles. Recent research shows that many graph properties and problems become radically different and usually substantially more difficult when an extra time dimension is added to them. Moreover, there is already a rich and rapidly growing set of modern systems and applications that can be naturally modeled and studied via temporal graphs. This, further motivates the need for the development of a temporal extension of graph theory. We survey here recent results on temporal graphs and temporal graph problems that have appeared in the Computer Science community.

  @article{Mi16,
   author = {Michail, Othon},
   title = {An Introduction to Temporal Graphs: An Algorithmic Perspective},
   journal = {Internet Mathematics},
   volume = {12},
   number = {4},
   pages = {239--280},
   year = {2016},
   issn = {1542-7951},
   doi = {http://dx.doi.org/10.1080/15427951.2016.1177801},
   url = {http://www.tandfonline.com/doi/full/10.1080/15427951.2016.1177801},
   publisher = {Taylor \& Francis}
  }
     

• Terminating Distributed Construction of Shapes and Patterns in a Fair Solution of Automata.
  Distributed Computing, 31(5), 343-365, Springer, October 2018.
  doi: 10.1007/s00446-017-0309-z, Open Access.
  A previous version appeared in
  34th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC),
  pages 37-46, Donostia-San Sebastián, Spain, July 2015.
  [DC] [PODC] [Presentation] [Arxiv] [bib] [Abstract]

  In this work, we consider a \emph{solution of automata} (or \emph{nodes}) that move passively in a well-mixed solution without being capable of controlling their movement. Nodes can \emph{cooperate} by interacting in pairs and every such interaction may result in an update of their local states. Additionally, the nodes may also choose to connect to each other in order to start forming some required structure. Such nodes can be thought of as \emph{small programmable pieces of matter}, like tiny nanorobots or programmable molecules. The model that we introduce here is a more applied version of Network Constructors, imposing \emph{physical} (or \emph{geometric}) \emph{constraints} on the connections that the nodes are allowed to form. Each node can connect to other nodes only via a very limited number of \emph{local ports}. Connections are always made at \emph{unit distance} and are \emph{perpendicular to connections of neighboring ports}, which makes the model capable of forming \emph{2D or 3D shapes}. We provide direct constructors for some basic shape construction problems, like \emph{spanning line}, \emph{spanning square}, and \emph{self-replication}. We then develop \emph{new techniques} for determining the computational and constructive capabilities of our model. One of the main novelties of our approach is that of exploiting the assumptions that the system is well-mixed and has a unique leader, in order to \emph{give terminating protocols that are correct with high probability}. This allows us to develop terminating subroutines that can be \emph{sequentially composed} to form larger \emph{modular protocols}. One of our main results is a \emph{terminating protocol counting the size $n$ of the system} with high probability. We then use this protocol as a subroutine in order to develop our \emph{universal constructors}, establishing that \emph{it is possible for the nodes to become self-organized with high probability into arbitrarily complex shapes while still detecting termination of the construction}.

  @article{Mi18,
   author = {Michail, Othon}, 
   title = {Terminating distributed construction of shapes and patterns in a fair solution of automata},
   journal = {Distributed Computing},
   volume = {31},
   number = {5},
   pages = {343--365},
   year = {2018},
   issn = {0178-2770},
   doi = {http://dx.doi.org/10.1007/s00446-017-0309-z},
   url = {http://link.springer.com/article/10.1007/s00446-017-0309-z},
   publisher = {Springer Berlin Heidelberg}
  }
  
     

• Traveling Salesman Problems in Temporal Graphs,
  with Paul Spirakis.
  Theoretical Computer Science (TCS), 634, 1-23, Elsevier, June 2016.
  A previous version appeared in
  39th International Symposium on Mathematical Foundations of Computer Science (MFCS),
  pages 553-564, Budapest, Hungary, August 2014.
  [TCS] [MFCS] [Presentation] [bib] [Abstract]

  In this work, we introduce the notion of time to some well-known combinatorial optimization problems. In particular, we study problems defined on \emph{temporal graphs}. A temporal graph $D=(V,A)$ may be viewed as a time-sequence $G_1,G_2,\ldots,G_l$ of static graphs over the same (static) set of nodes $V$. Each $G_t=D(t)=(V,A(t))$ is called the \emph{instance of $D$ at time $t$} and $l$ is called the \emph{lifetime of $D$}. Our main focus is on analogues of \emph{traveling salesman problems} in temporal graphs. A sequence of time-labeled edges (e.g. a tour) is called \emph{temporal} if its labels are strictly increasing. We begin by considering the problem of exploring the nodes of a temporal graph as soon as possible. In contrast to the positive results known for the static case, we prove that, it cannot be approximated within $cn$, for some constant $c>0$, in a special case of temporal graphs and within $(2-\varepsilon)$, for every constant $\varepsilon>0$, in another special case in which $D(t)$ is strongly connected for all $1\leq t\leq l$, both unless $\rem{P}=\rem{NP}$. We then study the temporal analogue of TSP(1,2), abbreviated TTSP(1,2), where, for all $1\leq t\leq l$, $D(t)$ is a complete weighted graph with edge-costs from $\{1,2\}$ and the cost of an edge may vary from instance to instance. The goal is to find a minimum cost temporal TSP tour. We give several \emph{polynomial-time approximation algorithms} for TTSP(1,2). Our best approximation is $(1.7+\varepsilon)$ for the generic TTSP(1,2) and $(13/8+\varepsilon)$ for its interesting special case in which the lifetime of the temporal graph is restricted to $n$. In the way, we also introduce temporal versions of other fundamental combinatorial optimization problems, for which we obtain polynomial-time approximation algorithms and hardness results.

  @article{MS16b,
   author = {Michail, Othon and Spirakis, Paul G.},
   title = {Traveling Salesman Problems in Temporal Graphs},
   journal = {Theoretical Computer Science},
   volume = {634},
   pages = {1--23},
   year = {2016},
   issn = {0304-3975},
   doi = {http://dx.doi.org/10.1016/j.tcs.2016.04.006},
   url = {http://www.sciencedirect.com/science/article/pii/S0304397516300342},
   publisher = {Elsevier}
  }
     

• Simple and Efficient Local Codes for Distributed Stable Network Construction,
  with Paul Spirakis.
  Distributed Computing, 29(3), 207-237, Springer, June 2016.
  A previous version appeared in
  33rd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC),
  pages 76-85, Paris, France, July 2014.
  [DC] [PODC] [Presentation] [bib] [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 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.

  @article{MS16a,
   author = {Michail, Othon and Spirakis, Paul G.},
   title = {Simple and efficient local codes for distributed stable network construction},
   journal = {Distributed Computing},
   volume = {29},
   number = {3},
   pages = {207--237},
   year = {2016},
   issn = {0178-2770},
   doi = {http://dx.doi.org/10.1007/s00446-015-0257-4},
   url = {https://link.springer.com/article/10.1007/s00446-015-0257-4},
   publisher = {Springer Berlin Heidelberg}
  }
     

• Naming and Counting in Anonymous Unknown Dynamic Networks,
  with Ioannis Chatzigiannakis and Paul Spirakis.
  In 5th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS),
  pages 281-295, Osaka, Japan, November 2013.
  Also as brief announcement in 26th International Symposium on DIStributed Computing (DISC),
  pages 437-438, Salvador, Brazil, October 2012.
  [SSS] [Presentation] [DISC] [Arxiv] [bib] [Abstract]

  In this work, we study the fundamental naming and counting problems (and some variations) in networks that are anonymous, unknown, and possibly dynamic. In counting, nodes must determine the size of the network n and in naming they must end up with unique identities. By anonymous we mean that all nodes begin from identical states apart possibly from a unique leader node and by unknown that nodes have no a priori knowledge of the network (apart from some minimal knowledge when necessary) including ignorance of n. Network dynamicity is modeled by the 1-interval connectivity model [KLO10], in which communication is synchronous and a (worst-case) adversary chooses the edges of every round subject to the condition that each instance is connected. We first focus on static networks with broadcast where we prove that, without a leader, counting is impossible to solve and that naming is impossible to solve even with a leader and even if nodes know n. These impossibilities carry over to dynamic networks as well. We also show that a unique leader suffices in order to solve counting in linear time. Then we focus on dynamic networks with broadcast. We conjecture that dynamicity renders nontrivial computation impossible. In view of this, we let the nodes know an upper bound on the maximum degree that will ever appear and show that in this case the nodes can obtain an upper bound on n. Finally, we replace broadcast with one-to-each, in which a node may send a different message to each of its neighbors. Interestingly, this natural variation is proved to be computationally equivalent to a full-knowledge model, in which unique names exist and the size of the network is known.

  @inproceedings{MCS13b,
    title={Naming and counting in anonymous unknown dynamic networks},
    author={Michail, Othon and Chatzigiannakis, Ioannis and Spirakis, Paul G},
    booktitle={15th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)},
    pages={281--295},
    year={2013},
    publisher={Springer}
  }
     

• Temporal Network Optimization Subject to Connectivity Constraints,
  with George Mertzios and Paul Spirakis.
  Algorithmica, 81(4), 1416-1449, Springer, April 2019.
  doi: 10.1007/s00453-018-0478-6, Open Access.
  A previous version (also with I. Chatzigiannakis) appeared in
  40th International Colloquium on Automata, Languages and Programming (ICALP),
  pages 657-668, Riga, Latvia, July 2013.
  [ALGORITHMICA] [ICALP] [Presentation] [Arxiv] [bib] [Abstract]

  In this work we consider \emph{temporal networks}, i.e.~networks defined by a \emph{labeling} $\lambda$ assigning to each edge of an \emph{underlying graph} $G$ a set of \emph{discrete} time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at which the edge is available. We focus on \emph{path problems} of temporal networks. In particular, we consider \emph{time-respecting} paths, i.e.~paths whose edges are assigned by $\lambda$ a strictly increasing sequence of labels. We begin by giving two efficient algorithms for computing shortest time-respecting paths on a temporal network. We then prove that there is a \emph{natural analogue of Menger's theorem} holding for arbitrary temporal networks. Finally, we propose two \emph{cost minimization parameters} for temporal network design. One is the \emph{temporality} of $G$, in which the goal is to minimize the maximum number of labels of an edge, and the other is the \emph{temporal cost} of $G$, in which the goal is to minimize the total number of labels used. Optimization of these parameters is performed subject to some \emph{connectivity constraint}. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graph families such as rings, directed acyclic graphs, and trees.

  @article{MMS19,
   author = {Mertzios, George B and Michail, Othon and Spirakis, Paul G}, 
   title = {Temporal Network Optimization Subject to Connectivity Constraints},
   journal = {Algorithmica},
   volume = {81},
   number = {4},
   pages = {1416--1449},
   year = {2019},
   issn = {0178-4617},
   doi = {http://dx.doi.org/10.1007/s00453-018-0478-6},
   url = {http://link.springer.com/article/10.1007/s00453-018-0478-6},
   publisher = {Springer Nature}
  }
     
  @inproceedings{MMCS13,
    title={Temporal Network Optimization Subject to Connectivity Constraints},
    author={Mertzios, George B and Michail, Othon and Chatzigiannakis, Ioannis and Spirakis, Paul G},
    booktitle={40th International Colloquium on Automata, Languages and Programming (ICALP)},
    pages={663--674},
    year={2013},
    volume={7966},
    number={Part 2},
    series={Lecture Notes in Computer Science},
    month={July},
    publisher={Springer}
  }
     

• Causality, Influence, and Computation in Possibly Disconnected Synchronous Dynamic Networks,
  with Ioannis Chatzigiannakis and Paul Spirakis.
  Journal of Parallel and Distributed Computing (JPDC), 74(1), 2016-2026, Elsevier, January 2014.
  A previous version appeared in
  16th International Conference On Principles Of DIstributed Systems (OPODIS),
  pages 269-283, Rome, Italy, December 2012.
  [JPDC] [OPODIS] [Presentation] [bib] [Abstract]

  In this work, we study the propagation of influence and computation in dynamic distributed computing systems that are possibly disconnected at every instant. We focus on a synchronous message-passing communication model with broadcast and bidirectional links. Our network dynamicity assumption is a worst-case dynamicity controlled by an adversary scheduler, which has received much attention recently. We replace the usual (in worst-case dynamic networks) assumption that the network is connected at every instant by minimal temporal connectivity conditions. Our conditions only require that another causal influence occurs within every time window of some given length. Based on this basic idea, we define several novel metrics for capturing the speed of information spreading in a dynamic network. We present several results that correlate these metrics. Moreover, we investigate termination criteria in networks in which an upper bound on any of these metrics is known. We exploit our termination criteria to provide efficient (and optimal in some cases) protocols that solve the fundamental counting and all-to-all token dissemination (or gossip) problems.

  @article{MCS14,
    title={Causality, influence, and computation in possibly disconnected synchronous dynamic networks},
    author={Michail, Othon and Chatzigiannakis, Ioannis and Spirakis, Paul G},
    journal={Journal of Parallel and Distributed Computing},
    volume={74},
    number={1},
    pages={2016--2026},
    year={2014},
    publisher={Elsevier}
  }
     

• Myriads of data, myriads of devices: self-awareness of the Ad-hoc,
  with Ioannis Chatzigiannakis, Georgios Mylonas, and Paul Spirakis.
  Awareness: Self-Awareness in Autonomic Systems, November 2012.
  [PDF] [bib]

  @article{CMMS12,
    title={Myriads of data, myriads of devices: self-awareness of the Ad-hoc},
    author={Chatzigiannakis, Ioannis and Michail, Othon and Mylonas, Georgios and Spirakis, Paul},
    journal={Awareness: Self-Awareness in Autonomic Systems},
    year={2012}
  }
  
     

• Terminating Population Protocols via some Minimal Global Knowledge Assumptions,
  with Paul Spirakis.
  Journal of Parallel and Distributed Computing (JPDC), 81-82, 1-10, Elsevier, July 2015.
  A previous version (also with I. Chatzigiannakis) appeared in
  14th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS),
  pages 77-89, Toronto, Canada, October 1-4, 2012.
  [JPDC] [SSS] [Presentation] [bib] [Abstract]

  We extend the population protocol model with a cover-time service that informs a walking state every time it covers the whole network. This represents a known upper bound on the cover time of a random walk. The cover-time service allows us to introduce termination into population protocols, a capability that is crucial for any distributed system. By reduction to an oracle-model we arrive at a very satisfactory lower bound on the computational power of the model: we prove that it is at least as strong as a Turing Machine of space log n with input commutativity, where n is the number of nodes in the network. We also give a log n-space, but nondeterministic this time, upper bound. Finally, we prove interesting similarities of this model to linear bounded automata.

  @article{MS15,
    title={Terminating population protocols via some minimal global knowledge assumptions},
    author={Michail, Othon and Spirakis, Paul G},
    journal={Journal of Parallel and Distributed Computing},
    volume={81},
    pages={1--10},
    year={2015},
    publisher={Elsevier}
  }
     

• The Computational Power of Simple Protocols for Self-Awareness on Graphs,
  with Ioannis Chatzigiannakis, Stavros Nikolaou, and Paul Spirakis.
  Theoretical Computer Science (TCS),
  Special Issue on Stabilization, Safety, and Security of Distributed Systems 2011 (SSS),
  512, 98-118, Elsevier, November 2013.
  A previous version appeared in
  13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS),
  pages 135-147, Grenoble, France, October 10-12, 2011.
  [TCS] [SSS] [Presentation] [bib] [Abstract]

  We explore the capability of a network of extremely limited computational entities to decide properties about itself or any of its subnetworks. We consider that the underlying network of the interacting entities (devices, agents, processes etc.) is modeled by an interaction graph that reflects the network’s connectivity. We examine the following two cases: First, we consider the case where the input graph is the whole interaction graph and second where it is some subgraph of the interaction graph given by some preprocessing on the network. In each case, we devise simple graph protocols that can decide properties of the input graph. The computational entities, that are called agents, are modeled as finite-state automata and run the same global graph protocol. Each protocol is a fixed size grammar, that is, its description is independent of the size (number of agents) of the network. This size is not known by the agents. We present two simple models (one for each case), the Graph Decision Mediated Population Protocol (GDMPP) and the Mediated Graph Protocol (MGP) models, similar to the Population Protocol model of Angluin et al., where each network link (edge of the interaction graph) is characterized by a state taken from a finite set. This state can be used and updated during each interaction between the corresponding agents. We provide some example protocols and some interesting properties for the two models concerning the computability of graph languages in various settings (disconnected input graphs, stabilizing input graphs). We show that the computational power within the family of all (at least) weakly-connected input graphs is fairly restricted. Finally, we give an exact characterization of the class of graph languages decidable by the MGP model in the case of complete interaction graphs: it is equal to the class of graph languages decidable by a nondeterministic Turing Machine of linear space that receives its input graph by its adjacency matrix representation.

  @article{CMNS13,
    title={The computational power of simple protocols for self-awareness on graphs},
    author={Chatzigiannakis, Ioannis and Michail, Othon and Nikolaou, Stavros and Spirakis, Paul G},
    journal={Theoretical Computer Science},
    volume={512},
    pages={98--118},
    year={2013},
    publisher={Elsevier}
  }
     

• Passively Mobile Communicating Machines that Use Restricted Space,
  with Ioannis Chatzigiannakis, Stavros Nikolaou, Andreas Pavlogiannis, and Paul Spirakis.
  Theoretical Computer Science (TCS), 412(46), 6469-6483, Elsevier, 2011.
  A previous version appeared in
  7th ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing (FOMC),
  San Jose, California, USA, June 9, 2011.
  [TCS] [FOMC] [Presentation] [bib] [Abstract]

  We propose a new theoretical model for passively mobile Wireless Sensor Networks, called PM, standing for Passively mobile Machines. The main modification w.r.t. the Population Protocol model [Angluin et al. 2006] is that agents now, instead of being automata, are Turing Machines. We provide general definitions for unbounded memories, but we are mainly interested in computations upper-bounded by plausible space limitations. However, we prove that our results hold for more general cases. We focus on \emphcomplete interaction graphs and define the complexity classes PMSPACE(f(n)) parametrically, consisting of all predicates that are stably computable by some PM protocol that uses O(f(n)) memory in each agent. We provide a protocol that generates unique identifiers from scratch only by using O(log n) memory, and use it to provide an exact characterization of the classes PMSPACE(f(n)) when f(n) = Ω(log n): they are precisely the classes of all symmetric predicates in NSPACE(nf(n)). As a consequence, we obtain a space hierarchy of the PM model when the memory bounds are Ω(log n). We next explore the computability of the PM model when the protocols use o(loglog n) space per machine and prove that SEM = PMSPACE(f(n)) when f(n) = o(loglog n), where SEM denotes the class of the semilinear predicates. Finally, we establish that the minimal space requirement for the computation of non-semilinear predicates is O(log log n).

  @article{CMNPS11,
    author    = {Ioannis Chatzigiannakis and
                 Othon Michail and
                 Stavros Nikolaou and
                 Andreas Pavlogiannis and
                 Paul G. Spirakis},
    title     = {Passively mobile communicating machines that use restricted
                 space},
    journal   = {Theoretical Computer Science},
    volume    = {412},
    number    = {46},
    year      = {2011},
    pages     = {6469-6483},
    month     = {October},
    ee        = {http://dx.doi.org/10.1016/j.tcs.2011.07.001}
  }
     

• Algorithmic Verification of Population Protocols,
  with Ioannis Chatzigiannakis, and Paul Spirakis.
  In 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS),
  pages 221-235, New York City, USA, September 20-22, 2010.
  [SSS] [Presentation] [bib] [Abstract]

  In this work, we study the Population Protocol model of Angluin et al. from the perspective of protocol verification. In particular, we are interested in algorithmically solving the problem of determining whether a given population protocol conforms to its specifications. Since this is the first work on verification of population protocols, we redefine most notions of population protocols in order to make them suitable for algorithmic verification. Moreover, we formally define the general verification problem and some interesting special cases. All these problems are shown to be NP-hard. We next propose some first algorithmic solutions for a natural special case. Finally, we conduct experiments and algorithmic engineering in order to improve our verifiers’ running times.

  @InProceedings{ CMS10,
  	author = "Ioannis Chatzigiannakis and Othon Michail and Paul G. Spirakis",
  	title = "Algorithmic verification of population protocols",
  	booktitle = "12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)",
  	year = "2010",
  	volume = "6366",
  	series = "Lecture Notes in Computer Science",
  	pages = "221--235",
  	month = "September",
  	publisher = "Springer-Verlag",
  	location = "New York City, USA"
  }
     

• Stably Decidable Graph Languages by Mediated Population Protocols,
  with Ioannis Chatzigiannakis, and Paul Spirakis.
  In 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS),
  pages 252-266, New York City, USA, September 20-22, 2010.
  Also as: Brief Announcement: Decidable Graph Languages by Mediated Population Protocols,
  in 23rd International Symposium on DIStributed Computing (DISC),
  pages 239-240, Elche, Spain, Sept. 2009.
  [SSS] [Presentation] [DISC] [bib] [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 TeX 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.

  @InProceedings{ CMS10-3-1,
  	author = "Ioannis Chatzigiannakis and Othon Michail and Paul G. Spirakis",
  	title = "Stably Decidable Graph Languages by Mediated Population Protocols",
  	booktitle = "12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)",
  	year = "2010",
  	volume = "6366",
  	series = "Lecture Notes in Computer Science",
  	pages = "252--266",
  	month = "September",
  	publisher = "Springer-Verlag",
  	location = "New York City, USA"
  }
     

• Computational Models for Wireless Sensor Networks: A Survey,
  with Apostolos Filippas, Stavros Nikolaou, Andreas Pavlogiannis, Ioannis Chatzigiannakis, and Paul Spirakis.
  In 1st International Conference for Undergraduate and Postgraduate Students in Computer Engineering,
  Informatics, related Technologies and Applications (EUREKA!),
  Ancient Olympia, Greece, 14-16 October, 2010.
  [PDF] [bib] [Abstract]

  Here we survey various computational models for Wireless Sensor Networks (WSNs). The population protocol model (PP) considers networks of tiny mobile finite-state artifacts that can sense the environment and communicate in pairs to perform a computation. The mediated population protocol model (MPP) enhances the previous model by allowing the communication links to have a constant size buffer, providing more computational power. The graph decision MPP model (GDM) is a special case of MPP that focuses on the MPP’s ability to decide graph properties of the network. Another direction towards enhancing the PP is followed by the PALOMA model in which the artifacts are no longer finite-state automata but Turing Machines of logarithmic memory in the population size. A different approach to modeling WSNs is the static synchronous sensor field model (SSSF) which describes devices communicating through a fixed communication graph and interacting with their environment via input and output data streams. In this survey, we present the computational capabilities of each model and provide directions for further research.

  @InProceedings{ FNPMCS10,
  	author = "Apostolos Filippas and Stavros Nikolaou and Andreas Pavlogiannis and Othon Michail and Ioannis Chatzigiannakis and Paul G. Spirakis",
  	title = "Computational Models for Wireless Sensor Networks: A Survey",
  	booktitle = "1st International Conference for Undergraduate and Postgraduate Students in Computer Engineering, Informatics, related Technologies and Applications (EUREKA!)",
  	year = "2010",
  	note = "Also FRONTS Technical Report, FRONTS-TR-2010-18, \url{http://fronts.cti.gr/aigaion/?TR=156}",
  	location = "Ancient Olympia, Greece"
  }
     

• All Symmetric Predicates in NSPACE(n^2) are Stably Computable by the Mediated Population Protocol Model,
  with Ioannis Chatzigiannakis, Stavros Nikolaou, Andreas Pavlogiannis, and Paul Spirakis.
  In 35th International Symposium on Mathematical Foundations of Computer Science (MFCS),
  pages 270-281, Brno, Czech Republic, August 23-27, 2010.
  [MFCS] [Presentation] [bib] [Abstract]

  This work focuses on the computational power of the Mediated Population Protocol model on complete communication graphs and initially identical edges (SMPP). In particular, we investigate the class MPS of all predicates that are stably computable by the SMPP model. It is already known that MPS is in the symmetric subclass of NSPACE(n^2). Here we prove that this inclusion holds with equality, thus, providing the following exact characterization for MPS: A predicate is in MPS iff it is symmetric and is in NSPACE(n^2).

  @InProceedings{ CMNPS10-2,
  	author = "Ioannis Chatzigiannakis and Othon Michail and Stavros Nikolaou and Andreas Pavlogiannis and Paul G. Spirakis",
  	title = "All symmetric predicates in ${NSPACE}(n^2)$ are stably computable by the mediated population protocol model",
  	booktitle = "35th International Symposium on Mathematical Foundations of Computer Science (MFCS)",
  	year = "2010",
  	volume = "6281",
  	series = "Lecture Notes in Computer Science",
  	pages = "270--281",
  	month = "August 23--27",
  	publisher = "Springer-Verlag",
  	location = "Brno, Czech Republic"
  }
     

• Computational Models for Networks of Tiny Artifacts: a Survey,
  with Carme Alvarez, Ioannis Chatzigiannakis, Amalia Duch, Joaquim Gabbaro, Maria Serna, and Paul Spirakis.
  Computer Science Review (CSR), 5(1), 7-25, Elsevier, May 2010.
  [CSR] [bib] [Abstract]

  We survey here some recent computational models for networks of tiny artifacts. In particular, we focus on networks consisting of artifacts with sensing capabilities. We first imagine the artifacts moving passively, that is, being mobile but unable to control their own movement. This leads us to the population protocol model of [Angluin et al. 2004]. We survey this model and some of its recent enhancements. In particular, we also present the mediated population protocol model in which the interaction links are capable of storing states and the passively mobile machines model in which the finite state nature of the agents is relaxed and the agents become multitape Turing machines that use a restricted space. We next survey the sensor field model, a general model capturing some identifying characteristics of many sensor network's settings. A sensor field is composed of kinds of devices that can communicate one to the other and also to the environment through input/output data streams. We, finally, present simulation results between sensor fields and population protocols and analyze the capability of their variants to decide graph properties.

  @Article{ ACMSS10,
  	author = "Carme {\`A}lvarez and Ioannis Chatzigiannakis and Amalia Duch and Joaquim Gabarr{\'o} and Othon Michail and Serna Maria and Paul G. Spirakis",
  	title = "Computational Models for Networks of Tiny Artifacts: A Survey",
  	journal = "Computer Science Review",
  	year = "2011",
  	volume = "5",
  	number = "1",
  	month = "January",
  	doi = "doi:10.1016/j.cosrev.2010.09.001"
  }
     

• On the Fairness of Probabilistic Schedulers for Population Protocols,
  with Ioannis Chatzigiannakis, Shlomi Dolev, Sandor Fekete, and Paul Spirakis.
  In Algorithmic Methods for Distributed Cooperative Systems,
  Dagstuhl Seminar Proceedings, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2010.
  [PDF] [Presentation] [bib] [Abstract]

  We propose a novel, generic definition of emph{probabilistic schedulers} for population protocols. We design two new schedulers, the emph{State Scheduler} and the emph{Transition Function Scheduler}. Both possess the significant capability of being emph{protocol-aware}, i.e. they can assign transition probabilities based on information concerning the underlying protocol. We prove that the proposed schedulers, and also the emph{Random Scheduler} that was defined by Angluin et al. [2004], are all fair with probability $1$. We also define and study emph{equivalence} between schedulers w.r.t. emph{performance} and emph{correctness} and prove that there exist fair probabilistic schedulers that are not equivalent w.r.t. to performance and others that are not equivalent w.r.t. correctness. We implement our schedulers using a new tool for simulating population protocols and evaluate their performance from the viewpoint of experimental analysis and verification. We study three representative protocols to verify stability, and compare the experimental time to convergence with the known complexity bounds. We run our experiments from very small to extremely large populations (of up to $10^{8}$ agents). We get very promising results both of theoretical and practical interest.

  @InProceedings{CDFMS10,
    author =	{Ioannis Chatzigiannakis and Shlomi Dolev and S{\'a}ndor Fekete and Othon Michail and Paul Spirakis},
    title =	{On the Fairness of Probabilistic Schedulers for Population Protocols},
    booktitle =	{Algorithmic Methods for Distributed Cooperative Systems},
    year =	{2010},
    editor =	{S{\'a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash},
    number =	{09371},
    series =	{Dagstuhl Seminar Proceedings},
    ISSN =	{1862-4405},
    publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
    address =	{Dagstuhl, Germany},
    URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2428},
    annote =	{Keywords: Population Protocols, Fairness, Probabilistic Schedulers, Communicating Automata, Sensor Networks, Experimental Evaluation}
  }
     

• Not All Fair Probabilistic Schedulers are Equivalent,
  with Ioannis Chatzigiannakis, Shlomi Dolev, Sandor Fekete, and Paul Spirakis.
  In 13th International Conference On Principles Of DIstributed Systems (OPODIS),
  pages 33-47, Nimes, France, December 15-18, 2009.
  [OPODIS] [Presentation] [bib] [Abstract]

  We propose a novel, generic definition of probabilistic schedulers for population protocols. We then identify the consistent probabilistic schedulers, and prove that any consistent scheduler that assigns a non-zero probability to any transition i -> j, where i and j are configurations satisfying i \neq j, is fair with probability 1. This is a new theoretical framework that aims to simplify proving specific probabilistic schedulers fair. In this paper we propose two new schedulers, the State Scheduler and the Transition Function Scheduler. Both possess the significant capability of being protocol-aware, i.e. they can assign transition probabilities based on information concerning the underlying protocol. By using our framework we prove that the proposed schedulers, and also the Random Scheduler that was defined by Angluin et al. [2], are all fair with probability 1. Finally, we define and study equivalence between schedulers w.r.t. performance and correctness and prove that there exist fair probabilistic schedulers that are not equivalent w.r.t. to performance and others that are not equivalent w.r.t. correctness.

  @InProceedings{ CDFMS09,
  	author = "Ioannis Chatzigiannakis and Shlomi Dolev and S{\'a}ndor P. Fekete and Othon Michail and Paul G. Spirakis",
  	title = "Not All Fair Probabilistic Schedulers Are Equivalent",
  	booktitle = "13th International Conference on Principles of Distributed Systems (OPODIS)",
  	year = "2009",
  	volume = "5923",
  	series = "Lecture Notes in Computer Science",
  	pages = "33--47",
  	publisher = "Springer-Verlag",
  	doi = "http://dx.doi.org/10.1007/978-3-642-10877-8\\\\\\\\\\_5",
  	isbn = "978-3-642-10876-1",
  	location = "N\^{\i}mes, France"
  }
     

• Recent Advances in Population Protocols,
  with Ioannis Chatzigiannakis and Paul Spirakis.
  In 34th International Symposium on Mathematical Foundations of Computer Science (MFCS),
  invited talk of Paul Spirakis, pages 56-76, Novy Smokovec, High Tatras, Slovak Republic, 2009 .
  [MFCS] [Presentation] [bib] [Abstract]

  The population protocol model (PP) proposed by Angluin et al. [2] describes sensor networks consisting of passively mobile finite-state agents. The agents sense their environment and communicate in pairs to carry out some computation on the sensed values. The mediated population protocol model (MPP) [13] extended the PP model by communication links equipped with a constant size buffer. The MPP model was proved in [13] to be stronger than the PP model. However, its most important contribution is that it provides us with the ability to devise optimizing protocols, approximation protocols and protocols that decide properties of the communication graph on which they run. The latter case, suggests a simplified model, the GDM model, that was formally defined and studied in [11]. GDM is a special case of MPP that captures MPP’s ability to decide properties of the communication graph. Here we survey recent advances in the area initiated by the proposal of the PP model and at the same time we provide new protocols, novel ideas and results.

  @InProceedings{ CMS09-2,
  	author = "Ioannis Chatzigiannakis and Othon Michail and Paul G. Spirakis",
  	title = "Recent Advances in Population Protocols",
  	booktitle = "34th International Symposium on Mathematical Foundations of Computer Science (MFCS)",
  	year = "2009",
  	volume = "5734",
  	series = "Lecture Notes in Computer Science",
  	pages = "56--76",
  	address = "Berlin, Heidelberg",
  	publisher = "Springer-Verlag",
  	doi = "http://dx.doi.org/10.1007/978-3-642-03816-7\\\\\\\\\\_6",
  	isbn = "978-3-642-03815-0",
  	location = "Novy Smokovec, High Tatras, Slovakia"
  }
     

• Mediated Population Protocols,
  with Ioannis Chatzigiannakis and Paul Spirakis.
  Theoretical Computer Science (TCS), 412(22), 2434-2450, Elsevier, February 2011.
  Based on two previous versions:
  (i) In 36th International Colloquium on Automata, Languages and Programming (ICALP),
  pages 363-374, Rhodes, Greece, July, 2009.
  (ii) see MFCS 2010 above.
  [TCS] [ICALP] [Presentation] [bib] [Abstract]

  We extend here the Population Protocol (PP) model of Angluin et al. (2004, 2006) [2,4] in order to model more powerful networks of resource-limited agents that are possibly mobile. The main feature of our extended model, called the Mediated Population Protocol (MPP) model, is to allow the edges of the interaction graph to have states that belong to a constant-size set. We then allow the protocol rules for pairwise interactions to modify the corresponding edge state. The descriptions of our protocols preserve both the uniformity and anonymity properties of PPs, that is, they do not depend on the size of the population and do not use unique identifiers. We focus on the computational power of the MPP model on complete interaction graphs and initially identical edges. We provide the following exact characterization of the class MPS of stably computable predicates: a predicate is in MPS iff it is symmetric and is in NSPACE(n^2).

  @Article{ MCS11-2,
  	author = "Othon Michail and Ioannis Chatzigiannakis and Paul G. Spirakis",
  	title = "Mediated population protocols",
  	journal = "Theoretical Computer Science",
  	issue_date = "May, 2011",
  	volume = "412",
  	number = "22",
  	month = "May",
  	year = "2011",
  	issn = "0304-3975",
  	pages = "2434--2450",
  	numpages = "17",
  	url = "http://dx.doi.org/10.1016/j.tcs.2011.02.003",
  	doi = "http://dx.doi.org/10.1016/j.tcs.2011.02.003",
  	acmid = "1967853",
  	publisher = "Elsevier Science Publishers Ltd.",
  	address = "Essex, UK",
  	keywords = "Diffuse computation, Finite-state agent, Intermittent communication, Passive mobility, Population protocol, Stable computation"
  }
     

• Improving the Integration of Neuro-Symbolic Rules with Case-Based Reasoning,
  with Jim Prentzas and Ioannis Hatzilygeroudis.
  In 5th Hellenic conference on Artificial Intelligence: Theories, Models and Applications (SETN),
  pages 377-382, 2008.
  [bib] [Abstract]

  In this paper, we present an improved approach integrating rules, neural networks and cases, compared to a previous one. The main approach integrates neurules and cases. Neurules are a kind of integrated rules that combine a symbolic (production rules) and a connectionist (adaline unit) representation. Each neurule is represented as an adaline unit. The main characteristics of neurules are that they improve the performance of symbolic rules and, in contrast to other hybrid neuro-symbolic approaches, they retain the modularity of production rules and their naturalness in a large degree. In the improved approach, various types of indices are assigned to cases according to different roles they play in neurule-based reasoning, instead of one. Thus, an enhanced knowledge representation scheme is derived resulting in accuracy improvement. Experimental results demonstrate its effectiveness.

  @InProceedings{ PHM08,
  year={2008},
  isbn={978-3-540-87880-3},
  booktitle={Artificial Intelligence: Theories, Models and Applications},
  volume={5138},
  series={Lecture Notes in Computer Science},
  editor={Darzentas, John and Vouros, GeorgeA. and Vosinakis, Spyros and Arnellos, Argyris},
  doi={10.1007/978-3-540-87881-0_36},
  title={Improving the Integration of Neuro-Symbolic Rules with Case-Based Reasoning},
  url={http://dx.doi.org/10.1007/978-3-540-87881-0_36},
  publisher={Springer Berlin Heidelberg},
  author={Prentzas, Jim and Hatzilygeroudis, Ioannis and Michail, Othon},
  pages={377-382},
  language={English}
  }