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: