DiADN 2019
Workshop on Distributed Algorithms for Dynamic Networks
The aim of DiADN is to present algorithmic developments for distributed computations in contemporary local and global network architectures constrained by dynamicity. Such constraints may be due to various factors, including but not restricted to mobility, changes in physical conditions, variability of demand, reliability, computational resources, and hardware limitations. The challenges that these constraints impose yield classical assumptions such as the availability of communication paths or even the possibility of distinguishing network nodes invalid. Then, fundamental communication tasks such as broadcast, routing, or election need to be revisited to be applicable to realistic scenarios, including ad-hoc networks, mobile networks, sensor networks, and dynamic networks.
DiADN will be held on Friday, October 18, 2019 in Budapest, Hungary, and will be co-located with DISC 2019. The workshop chairs are Tomasz Jurdzinski and Miguel A. Mosteiro. For information on registration, please go to the DISC 2019 website.
Important dates:
- Early registration: August 31st, 2019
- Workshop: October 18th, 2019
Venue:
Hotel Danubius Health Spa Resort Margitsziget, Margitsziget (Margaret Island), H-1007 Budapest, Hungary. (Special rates can be found in the accommodation section of DISC website.)
Invited Speakers:
- Janna Burman, Université Paris-Saclay.
- Arnaud Casteigts, LaBRI, Université de Bordeaux .
- Leszek Gąsieniec, University of Liverpool.
- Andrea Richa, Arizona State University.
- Gregory Schwartzman, National Institute of Informatics, Japan.
- Paul G. Spirakis, University of Liverpool and University of Patras.
- Sébastien Tixeuil, Sorbonne Université.
Program (updated):
09:15 - 10:00 Janna Burman (Université Paris-Saclay), Self-stabilizing Population Protocols
10:00 - 10:30 Coffee break
10:30 - 11:15 Arnaud Casteigts (LaBRI, Université de Bordeaux), Exploiting Temporal Properties in Dynamic Networks: An Overview
11:15 - 12:00 Sébastien Tixeuil (Sorbonne Université), Mitigating faults in Mobile Robotic Swarms
12:00 - 14:00 Lunch break
14:00 - 14:45 Andrea Richa (Arizona State University), Algorithmic Foundations of Programmable Matter
14:45 - 15:30 Gregory Schwartzman (National Institute of Informatics, Japan), Fast and Simple Deterministic Algorithms for Highly-Dynamic Networks
15:30 - 16:15 Leszek Gasieniec (University of Liverpool), Perpetual network monitoring
16:15 - 16:45 Coffee break
16:45 Workshop ends
Abstracts and Slides:
Title : Self-stabilizing Population Protocols
Speaker : Janna Burman (Université Paris-Saclay)
Population protocols model distributed systems of mobile anonymous entities having no control over their movements. The entities interact in pairs in an opportunistic way. In an interaction, the two entities exchange and update their internal states, according to the protocol. This model is proven to be useful for modeling networks in various domains, like those of wireless sensors, social networks and even chemical reaction and gene regulatory networks. Such networks are inherently unreliable and have limited resources.
Focusing on resources of memory and time, we will discuss about how efficiently tasks can be solved when facing transient faults, modeled by means of self-stabilization. The talk will give an overview of the related work and focus on several fundamental tasks like counting, naming and leader election.
Title : Exploiting Temporal Properties in Dynamic Networks: An Overview
Speaker : Arnaud Casteigts (LaBRI, Université de Bordeaux)
Mobile entities like robots, drones, and vehicles can communicate directly with each other, resulting in highly-dynamic networks whose communication links appear and disappear frequently (and unpredictably). While these networks may look chaotic at first, they often satisfy subtle properties over time and space, which a distributed algorithm can exploit to solve a given problem. In this talk, I will review a number of such properties in relation to basic distributed problems. The talk is technology-insensitive, it will focus on graph-theoretical properties (formulated using dynamic graphs, a.k.a. temporal, evolving, or time-varying graphs) and algorithmic ideas at a general level.
Title : Perpetual network monitoring
Speaker : Leszek Gasieniec (University of Liverpool)
A graph based or geometric network $G=(V,E)$ is formed of n nodes in V={v_1, v_2, ..., v_n} which need to be monitored, i.e., visited and properly maintained on a regular basis. The network operates in rounds. Every node $v_i$ has a maintenance indicator $x_i$ which is incremented at the end of each round by a fixed value $h_i$, where $h_1 \ge ... \ge h_m$. A (software) mobile agent able to manouver through the network connections is delegated to monitor all nodes of the network, and on the conclusion of each visit in $v_i$ the maintenance indicator $x_i$ is set to $0$.
The perpetual network monitoring problem refers to the design of perpetual (indefinite) schedules of visits at the network nodes with the goal of keeping the maintenance indicators as low as possible. The problem is relatedto a number of classical challenges including TSP, The Art Gallery Problem, network patrolling, Pinwheel scheduling, and others.
We present several effcient solutions to the considered problem and discuss related problems. The talk is concluded with a list of open problems.
Title : Algorithmic Foundations of Programmable Matter
Speaker : Andrea Richa (Arizona State University)
Many programmable matter systems have been developed, including modular and swarm robotics, synthetic biology, DNA tiling, and smart materials. We describe programmable matter as an abstract collection of simple computational elements (particles) with limited memory that each execute fully distributed, local, asynchronous algorithms to self-organize and solve system-wide problems such as movement, configuration, and coordination. Self-organizing particle systems (SOPS) have many interesting applications like coating objects for monitoring and repair purposes, and forming nano-scale devices for surgery and molecular-scale electronic structures. In this talk, we describe our work on establishing an algorithmic foundation for programmable matter. We investigate how macro-scale system behaviors can naturally emerge from local micro-behaviors by individual particles. We start by investigating shape formation, leader election and coating in SOPS. We then utilize tools from statistical physics and Markov chain analysis to translate Markov chains defined at a system level into asynchronous, distributed, local algorithms for self-organizing particle systems that drive the emergent phenomenon of compression, expansion, bridging, and phototaxing, also establishing direct ties to the notion of *active matter* in physics.
Title : Fast and Simple Deterministic Algorithms for Highly-Dynamic Networks
Speaker: Gregory Schwartzman, National Institute of Informatics, Japan
Abstract :
In this talk we present a simple algorithmic template for obtaining fast distributed algorithms for a highly-dynamic setting, in which arbitrarily many edge changes may occur in each round. Our algorithm significantly improves upon prior work in its combination of (1) having an O(1) amortized time complexity, (2) not posing any restrictions on the dynamic behavior of the environment, (3) being deterministic, (4) having strong guarantees for intermediate solutions, and (5) being applicable for a wide family of tasks which we combinatorially define.
The tasks for which we deduce such an algorithm are maximal matching, (degree+1)-coloring, maximal independent set (which, perhaps surprisingly, seems to behave very differently from the other problems), and the seemingly unrelated problem of a 2-approximation for minimum weight vertex cover. For some of these tasks, node insertions can also be among the allowed topology changes, and for some of them also abrupt node deletions.
At the core of our work is a combinatorial definition of a subclass of the celebrated family of locally-checkable labelings (LCLs) defined by Naor and Stockmeyer. We call the subclass that we define locally-fixable labelings (LFLs). Very roughly speaking, as their name suggests, these are labelings that allow a node to fix its own label and the labels of its neighbors after a topology change, based solely on their old labels.
Title : The impact of temporal availability patterns on the Complexity of Temporal Problems : An analysis of two cases.
Speaker : Paul G. Spirakis (University of Liverpool and University of Patras)
Abstract : Modern , inherently dynamic systems are usually characterized by a network structure , that is an underlying graph topology which is subject to discrete changes over time. Given a static underlying graph G , a temporal graph on G is a sequence of snapshots {G_t = (V ,E_t) where t is in N} , one snapshot for each time step. But there are several different ways of specifying the snapshots that may lead to quite different ways of thinking about the temporal network.
In this talk we first consider the traditional way of specifying such availability changes by directly providing , for every edge of G , a set of “time slots (labels) “ at which the edge is “active”. For this way of specifying availability of network edges we study some natural temporal extensions of the classical VERTEX COVER problem and we provide a thorough investigation of the computational complexity and approximability of such problems.
Then , we study Stochastic Temporal Graphs , i.e. stochastic processes whose random variables are the snapshots of a temporal graph on G. We consider edge-centric ways of network evolution , where each edge of G has its own stochastic laws for its appearance over time independently of other edges. We also consider a memory effect in the appearance probabilities of particular edges ; that is , the probability an edge e in G appears at time step t depends on its appearance (or absence) at the previous k steps , where k >=0 is a parameter. Here , for each k >=0 we investigate the computational complexity of two related (but fundamentally different) temporal path (journey) problems , namely MINIMUM ARRIVAL and BEST POLICY.
The two ways of specifying availabilities lead to quite different analysis and complexity results.
This talk is based on recent joint works with E. Akrida, G. Mertzios, S. Nikoletseas, Ch. Raptopoulos, V. Zamaraev and the speaker. Most of the results appeared in ICALP 2018 and ICALP 2019.
Title : Mitigating faults in Mobile Robotic Swarms
Speaker : Sébastien Tixeuil (Sorbonne Université)
Our supporters:
