Foundations of Dynamic Distributed Computing Systems
Greek GSRT PENED Project -12555/26.9.2012

Project web site -
Start-End Dates 26/09/2012 - 25/09/2015
Coordinator Spirakis, Paul (CTI)
Partners -

The goal of the proposed research is to significantly advance the mathematical foundations of dynamic distributed computing systems. Such systems change over time, as nodes join, leave, and move around, and as communication links appear and disappear. In these systems, changes of the underlying topology are continuous and may go on forever. Past research considered such changes to be exceptions, and focused on adapting to them and re-stabilizing. Only in recent years we begin to treat dynamic changes as the norm. Another novel point is that these dynamic systems should be treated from a worst-case perspective, in order to make robustness, dependability, and safety of operation as independent from statistical assumptions as possible. Under these extreme conditions, the design of algorithms and their analysis becomes a really challenging task. The situation becomes even harder due to the apparent lack of a concrete body of mathematical concepts and techniques suitable for dealing with dynamic graphs. Our research aims in providing (i) novel computational models for networks of mobile devices, new distributed techniques suitable for dealing with network dynamicity, bounds and optimal protocols for distributed tasks, and characterizations of complexity classes, (ii) novel graph-theoretic concepts, definitions, and results that will promote our understanding on graphs that change perpetually, and (iii) a set of design principles and (algorithmic) verification techniques for dynamic distributed computing systems. The study of dynamic distributed systems has a plethora of crucial everyday applications ranging from routing and broadcasting in delay-tolerant networks to social studies and networks of mobile sensors, and many other novel distributed systems and applications that are now within reach. Consequently, we are strongly convinced that such a study will positively affect future ICT industry while promoting the design of mobile applications.




This project is implemented under the “ARISTEIA” Action of the Operational Programme “Education and Lifelong Learning” and is co-funded by the European Union (European Social Fund) and Greek National Resources.

Project related publications


The publication database is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit