Arrivals

The arrival day is Sunday, August 25. The check-in and welcome reception will be open from 17:00 to 21:00.


Program

Update: all plenary sessions will be held in the Museum room in the Castle.

Time Aug 26, Monday Aug 27, Tuesday Aug 28, Wednesday Aug 29, Thursday Aug 30,
Friday
7:30–9:00 breakfast breakfast breakfast breakfast breakfast
9:00–9:45 introduction Marcel Roeloffzen "Kinetic data structures" 9:00–9:40
status report
status report status report
Rik Sarkar "Range counting in planar graphs" 9:40–10:00
Dorian Rudolf "Shape formation in 3D"
9:45–10:30 Nicola Santoro Alfredo Navarra "Pattern formation with fixed points in the plane" 10:00–10:20
Vera Sacristán "Self-reconfiguring modular robots"
working session
Christian Schindelhauer "Algorithms for self-calibrating localization" 10:20–10:40
Christian Scheideler "LP-type problems"
10:30–11:00 coffee break coffee break 10:45–11:15
coffee break
coffee break coffee break
11:00–11:45 Subhash Suri Valentin Polishchuk "Motion conflict graphs" 11:15–12:30
working session
working session wrap up session
Fabian Kuhn TBA
11:45–12:30 Christian Scheideler Friedhelm Meyer auf der Heide TBA
Pierre Fraigniaud "A Topological Perspective on Distributed Computing"
12:30–14:00 lunch lunch lunch lunch lunch
14:00–14:45 Sándor Fekete working session excursion

dinner at 20:00 at Restaurant Casa Artusi in Forlimpopoli
working session departures
14:45–15:30 Irina Kostitsyna
15:30–16:00 coffee break coffee break coffee break
16:00–16:45 open problem session working session working session
16:45–17:30
19:30– ... dinner at Cà de Bé dinner at Enoteca Bistrot Colonna dinner at La Grotta Bertinoro

Tutorials

• Distributed geometric algorithms by mobile robots

Speaker: Nicola Santoro

Time: Monday, 9:45–10:30

Abstract: Within distributed computing, intensive investigations are being carried out on the computational and complexity issues arising in systems of mobile computational entities operating in Euclidean spaces. Totally autonomous, the entities, called robots and viewed as points, operate in Look-Compute-Move cycles {perceiving the position of the other robots, executing the same protocol to compute a destination point, and moving there), cooperating to solve some problems. Typical problems include pattern formation, gathering, scattering. The main algorithmic tools in the design of the solution protocols are geometric and the settings are fully distributed. Because the entities are mobile, the field is about kinematic geometry and design and analysis of distributed protocols. In this talk, I will describe the basic computational models, and overview some slgorithmic results as a way of explanation.


• Geometric constraint removal problems

Speaker: Subhash Suri

Time: Monday, 11:00–11:45

Abstract: Constraint removal or relaxation is a natural approach in optimization when the solution is either infeasible or unsatisfactory. This talk will explore the complexity and approximability of the following three problems in this framework:

  • Shortest paths with obstacle removal,
  • Minimum color paths, and
  • Maximum exposure.
These problems are motivated by applications in sensor networks and robotics, and might be worthy of study from a distributed computing perspective as well.


• Hybrid networks

Speaker: Christian Scheideler

Time: Monday, 14:00–14:45

Abstract: I will introduce a new communication model, called hybrid network, in which the nodes have the choice between two communication modes: a local mode that allows them to exchange messages with nearby nodes, and a global mode where communication between any pair of nodes is possible, but the amount of communication is limited. This can be motivated, for instance, by wireless networks in which we combine direct device-to-device communication with communication via the cellular infrastructure. I will show how to quickly build up a low-diameter, low-degree network of global edges (i.e., connections established via the global communication mode) on top of any network of local edges (i.e., connections given by the local communication mode) so that various problems such as computing minimum spanning trees and shortest paths can be solved much more efficiently than by just using the local edges.


• From nano to Mega: Coordinating swarms of objects at extreme dimensions

Speaker: Sándor Fekete

Time: Monday, 14:45–15:30

Abstract:
Coordinating and reconfiguring arrangements of objects poses important questions at various dimensions, ranging from tiny particles all the way to far-away satellite swarms. Ironically, systems of these very small and very large distances share a fundamental property: It becomes difficult to use "external" computation, in which a powerful central computing device is provided with input about the system, and output is fed back into the system. Instead, it becomes important to consider "internal" computation, in which algorithms and execution remain within the system itself, even if that comes at the expense of processing power. Additional challenges arise from coordinating the parallel motion of larger and larger sets of objects in a globally efficient manner.

This talk will describe a variety of algorithmic approaches to coordination and reconfiguration challenges. These include (1) Algorithmic aspects of "programmable matter", i.e., algorithmic methods for controlling structures that can change their physical properties (shape, density, moduli, conductivity, optical properties, etc.) in a programmable fashion. (2) Optimization methods for coordinated motion planning, in which a large swarm of objects needs to be reorganized in a minimum amount of time. (3) Distributed approaches for coordinating the downlink activities of satellite swarms with more than 1000 spacecraft.


• Hybrid programmable matter

Speaker: Irina Kostitsyna

Time: Monday, 11:45–12:30

Abstract: Recent developments in nanotechnology and the potential significance of its application to various areas, such as electronics, medicine, and energy, spiked an interest in computer science community for developing theoretical models of programmable matter. Programmable matter is any matter that has the ability to change its physical properties (like shape, density, moduli, conductivity, optical properties, etc.) based on user input or autonomous sensing. So far, only very primitive forms of adaptive programmable matter have been realized, and now is the right time to start developing fundamental models and approaches for the algorithmic study of programmable matter. A few models for programmable matter have been proposed already. For example, in tile self-assembly model semi-passive tiles attach to each other following certain rules growing into larger and larger structures, thus performing computation. Dealing with passive elements only does not allow one yet to create smart, adaptive materials. Thus, other suggested models consider computation on nanoscale by active agents. However, one can imagine, that for many practical problems, most of the nanostructures will remain static most of the time, with only small changes occurring over some short periods of time. In this case using active agents as static building blocks seems excessive. We envision a hybrid model, where the structures consist of static nanoscale materials which can be reconfigured by a comparatively small set of active agents. Thus, motivated by the problem of manipulating nanoscale materials by nanoscale active agents, we introduce a new theoretical model for programmable matter which combines active and passive agents.