First Workshop on Dynamic Graphs in Distributed Computing
in conjunction with DISC'16 Paris, September 30th, 2016
Mobile ad-hoc networks, sensor networks, or peer-to-peer systems are some examples of distributed systems that share a very challenging property: they are dynamic in the sense that their underlying topology changes unpredictably with time. Due to the great development of such systems in many fields, distributed computing practitioners must take dynamicity into account. The challenge is that it is not sufficient to adapt existing solutions from static systems due to the intrinsic nature of these systems, in which dynamics is not an exception. Even basic assumptions like the availability of paths may sometimes become irrelevant in highly-dynamic networks, leading to reconsider the meaning of basic tasks like election, broadcast, or routing.
From an algorithmic point of view, the first step is to correctly model the dynamicity of the underlying topology. In some cases, it can be reformulated in terms of classical properties (e.g. scheduling). However, numerous works in the field of distributed computing (and beyond) recently considered graph-theoretical approaches to capture various definitions of dynamics and their impact on distributed computing.
The DGDC workshop precisely focuses on these dynamic graph models and formalisms and their implications in distributed computing. Topics of interest include, but are not limited to:
- New models or improvement of existing models of dynamic graphs
- Computability and/or complexity in distributed computing based on dynamic graph assumptions
- Relations among dynamic graph properties and concepts
- Property testing in dynamic graphs
- Modelization and/or verification in dynamic systems
- Fault-tolerance in dynamic systems