which the labels are chosen according
to some probability distribution. 1
Do we really know how to compute in
highly dynamic environments, how to
represent and measure their core properties, or even how to efficiently solve
centralized computational problems
concerning them? Despite the considerable recent progress that we discussed
in this article, the answer is: not yet. We
are on the road to a unified theory of dynamic networks, but not yet there.
Though it is still quite early to anticipate the full range of potential applications, there is already strong evidence
that there is room for the development
of a rich theory. As is always the case,
the groundwork will be laid by our ability to identify and formulate radically
new problems and not just by studying
adjusted versions of existing ones. Real
dynamic systems are the natural place
to look for such problems. Still, the existing literature has already identified
some first challenging research directions and technical problems whose
further investigation has the potential
to push forward the area.
First, is there a general rule underlying the complexity increase of a
network problem when that problem
is extended in time? Moreover, most
natural applications require an algorithm to operate on a dynamic network
without knowing or being able to accurately predict the future evolution of
the network. It might be the case that
the right treatment of such settings
is via online algorithms and analysis,
however little effort has been devoted
to this. We saw that there is a natural
reformulation of Menger’s theorem for
temporal graphs. It would be very valuable to check the validity of many other
fundamental results of graph theory,
like Kuratowski’s planarity theorem or
Mantel’s beautiful theorem on the existence of triangles.
Another critical issue has to do with
a long-standing problem in distributed
computing theory: there is practically
a different model for each setting and
usually slight modifications of a model
result in totally different formal properties. This multiplicity is expected to
be even more intense in dynamic networks, due to the almost inexhaustible
variety of different dynamicity patterns.
Therefore, if possible, a unification of
models for distributed computing in
dynamic networks would be more than
valuable. There is also a great need for
progress in programming and verification of programmable matter protocols,
probably the only sub-area of dynamic
networks in which theory has grown
faster than systems. We need many
more real collectives of tiny devices, in
order to identify, which assumptions actually make sense and are worth studying and which would never show up in a
real system and have to be abandoned.
Finally, we should seriously take into account the recent advances in learning
and statistical learning in particular,
as a rich source of powerful methods
for a system to learn and, thus, be able
to predict to some extent the pattern of
the dynamic network and to adapt its algorithms in order to cope with the new
conditions more effectively.
1. Akrida, E. C., Gasieniec, L. G , Mertzios, G.B. and
Spirakis, P. G. Ephemeral networks with random
availability of links: The case of fast networks. J.
Parallel Distrib. Comput. 87 (2016), 109–120.
2. Alistarh, D. and Gelashvili, R. Polylogarithmic-time
leader election in population protocols. In Proceedings
of ICALP, 2015, 479–491.
3. Angluin, D. Local and global properties in networks of
processors. In Proceedings of STOC, 1980, 82–93.
4. Angluin, D., Aspnes, J. , Diamadi, Z., Fischer, M. J. and
Peralta, R. Computation in networks of passively
mobile finite-state sensors. In Proceedings of PODC,
2004, 290–299. Also in Distributed Computing, 2006.
5. Angluin, D., Aspnes, J. and Eisenstat, D. Fast
computation by population protocols with a leader.
Distributed Computing 21, 3 (2008), 183–199.
6. Angluin, D., Aspnes, J., Eisenstat, D. and Ruppert, E.
The computational power of population protocols.
Distributed Computing 20, 4 (2007), 279–304.
7. Aspnes, J. and Ruppert, E. An introduction to
population protocols. In Middleware for Network
Eccentric and Mobile Applications, 2009, 97–120.
8. Avin, C., Koucký, M. and Lotker, Z. How to explore a
fast-changing world (cover time of a simple random
walk on evolving graphs). In Proceedings of ICALP,
9. Berman, K.A. Vulnerability of scheduled networks and
a generalization of Menger’s theorem. Networks 28, 3
10. Cardelli, L. Morphisms of reaction networks that
couple structure to function. BMC Systems Biology 8,
1 (2014), 84.
11. Casteigts. A., Flocchini, P., Quattrociocchi, W. and
Santoro, N. Time-varying graphs and dynamic
networks. IJPEDS 27, 5 (2012), 387–4082.
12. Chatzigiannakis, I., Michail, O., Nikolaou, S.,
Pavlogiannis, A. and Spirakis, P.G. Passively mobile
communicating machines that use restricted space.
Theor. Comput. Sci. 412, 46 (2011), 6469–6483.
13. Chen, H.-L., Cummings, R., Doty, D. and Soloveichik,
D. Speed faults in computation by chemical reaction
networks. In Proceedings of DISC, 2014, 16–30. Also
in Distributed Computing, 2015.
14. Clementi, A. E., Macci, C., Monti, A., Pasquale, F. and
Silvestri, R. Flooding time in edge-markovian dynamic
graphs. In Proceedings of PODC, 2008, 213–222.
15. Czyzowicz, J. et al. On convergence and threshold
properties of discrete lotka-volterra population
protocols. In Proceedings of ICALP, 2015, 393–405.
16. Doty, D. Theory of algorithmic self-assembly.
Commun. ACM 55, 12 (Dec. 2012), 88.
17. Doty, D. Timing in chemical reaction networks. In
Proceedings of SODA, 2014, 772–784.
18. Doty, D. and Soloveichik, D. Stable leader election
in population protocols requires linear time. In
Proceedings of DISC, 2015, 602–616.
19. Dutta, C., Pandurangan, G., Rajaraman, R., Sun, Z. and
Viola, E. On the complexity of information spreading
in dynamic networks. In Proceedings of SODA, 2013,
20. Erlebach, T., Hoffmann, M. and Kammer, F. On
temporal graph exploration. In Proceedings of ICALP,
21. Fischer, M.J., Lynch, N.A. and Paterson, M.S.
Impossibility of distributed consensus with one faulty
process. J. ACM 32, 2 (1985) 374–382.
22. Flocchini, P., Mans, B. and Santoro, N. On the
exploration of time-varying networks. Theoretical
Computer Science 469 (2013), 53–68.
23. Guerraoui, R. and Ruppert, E. Names trump malice:
Tiny mobile agents can tolerate byzantine failures. In
Proceedings of ICALP, 2009, 484–495.
24. Kempe, D., Kleinberg, J. and Kumar, A. Connectivity
and inference problems for temporal networks. In
Proceedings of STOC, 2000, 504–513.
25. Kuhn, F., Lynch, N. and Oshman, R. Distributed
computation in dynamic networks. In Proceedings of
STOC, 2010, 513–522.
26. Kuhn, F. and Oshman, R. Dynamic networks: models
and algorithms. SIGACT News, 2011, 42: 82–96.
27. Lamport, L. Time, clocks, and the ordering of events in
a distributed system. Commun. ACM 21, 7 (July 1978),
28. Mertzios, G.B., Michail, O., Chatzigiannakis, I. and
Spirakis, P.G. Temporal network optimization subject
to connectivity constraints. In Proceedings of ICALP,
29. Michail, O. Terminating distributed construction of
shapes and patterns in a fair solution of automata. In
Proceedings of PODC, 2015, 37–46. Also in Distributed
30. Michail, O. An introduction to temporal graphs: An
algorithmic perspective. Internet Mathematics 12, 4
31. Michail, O., Chatzigiannakis, I. and Spirakis, P. G.
Mediated population protocols. Theoretical Computer
Science 412, 22 (2011), 2434–2450.
32. Michail, O., Chatzigiannakis, I. and Spirakis, P. G. New
Models for Population Protocols. N. A. Lynch, ed.
Morgan & Claypool, 2011.
33. Michail, O., Chatzigiannakis, I. and Spirakis, P.G.
Causality, influence, and computation in possibly
disconnected synchronous dynamic networks. J.
Parallel Distrib. Comput. 74, 1 (2014), 2016–2026.
34. Michail, O. and Spirakis, P.G. How many cooks spoil the
soup? In Proceedings of SIROCCO, 2016, 3–18.
35. Michail, O. and Spirakis, P.G. Simple and efficient local
codes for distributed stable network construction.
Distributed Computing 29, 3 (2016), 207–237.
36. Michail, O. and Spirakis, P.G. Traveling salesman
problems in temporal graphs. Theoretical Computer
Science 634, 2016, 1–23.
37. Mone, G. The new smart cities. Commun. ACM 58, 7
(July 2015), 20–21.
38. O’Dell, R. and Wattenhofer, R. Information
dissemination in highly dynamic graphs. In
Proceedings of DIALM-POMC, 2005, 104–10.
39. Rubenstein, M., Cornejo, A. and Nagpal, R.
Programmable self-assembly in a thousand-robot
swarm. Science 345, 6198 (2014), 795–799.
Othon Michail ( Othon.Michail@liverpool.ac.uk) is a
lecturer in the Department of Computer Science at the
University of Liverpool, U.K.
Paul G. Spirakis ( P.Spirakis@liverpool.ac.uk) is a
professor in the Department of Computer Science at the
University of Liverpool, U.K. and senior researcher at the
Computer Technology Institute, Patras, Greece.
Copyright held by authors/owners.
Publication rights licensed to ACM. $15.00.
Watch the authors discuss
their work in this exclusive