All workshops and tutorials will be held at the Arcadia Ichigaya hotel.
Note: Lunch on 5th and 6th won’t be organized at the hotel. Instead we prepare lunch map.
Workshops
Monday, October 5: WDRS – Workshop on Distributed Robotic Swarms
Location and Time: Held at the HOUHOU room on the 4th floor of Arcadia Ichigaya Hotel, 9:00-12:30 and 14:00-17:30.
WDRS is a one-day workshop that focuses on the theoretical aspect of distributed control of robotic swarms. The workshop consists of 3-5 invited talks and several open problem and work in progress sessions. The workshop accepts presentations of original contributions. The workshop is organized by Paola Flocchini, Fukuhito Ooshita, and Yukiko Yamauchi.
Tuesday, October 6: ADGA 2015 – The 4th Workshop on Advances in Distributed Graph Algorithms
Location and Time: Held at the HOUHOU room on the 4th floor of Arcadia Ichigaya Hotel, 9:00-12:30 and 14:00-17:30.
ADGA is a one-day workshop that focuses on the theoretical foundations of distributed graph algorithms. The programme consists of several invited talks, which are aimed at the general DISC audience. ADGA 2015 is chaired by Keren Censor-Hillel.
Tutorials (both on Tuesday October 6)
Morning Tutorial: Communication Complexity in Distributed Computing
by Rotem Oshman
Location and Time: Held at the ASO EAST room on the 6th floor of Arcadia Ichigaya Hotel, from 9:00 to 12:30. Coffee breaks at 10:00 and 11:15 in HOUHOU room, on the 4th floor.
Communication complexity plays a central role in studying distributed systems with bandwidth constraints, such as the CONGEST model. In this tutorial we will survey several popular models and some techniques that can be used to prove lower bounds for them, with emphasis on how techniques from information theory can be used to get the communication lower bounds we need. (No prior background in information theory will be assumed.)
The first part of the tutorial will be devoted to the classical CONGEST model, where we have a synchronous communication network in which each link can convey a bounded number of bits per round, and we ask how many rounds are needed to perform certain tasks. For this model, two-party communication complexity lower bounds are very useful. We will also touch on obstacles towards proving lower bounds for the congested clique (from Drucker, Kuhn, Oshman’14).
In the second part we will turn our attention to recent work [Phillips, Verbin, Zhang’12; Woodruff and Zhang ’12,’13 and ’14; Braverman, Ellen, Oshman, Pitassi and Vaikuntanathan’13; Braverman and Oshman ’15] studying the total number of bits that must be sent to solve problems in the synchronous message-passing model. We will cover the symmetrization technique from [Phillips, Verbin, Zhang’12] and an information-theoretic lower bound multi-party set disjointness lower bound from [Braverman, Oshman ’15], with applications to the hardness of checking graph properties.
Afternoon Tutorial: Distributed Fault-tolerant Runtime Verification
by Borzoo Bonakdarpour, Pierre Fraigniaud and Sergio Rajsbaum
Location and Time: Held at the ASO EAST room on the 6th floor of Arcadia Ichigaya Hotel, from 14:00 to 17:30. Coffee breaks at 15:00 and 16:15 in HOUHOU room, on the 4th floor.
Runtime verification (RV) is concerned with monitoring software and hardware system executions. RV techniques are complementary, and sometimes more versatile than conventional testing, and more practical than exhaustive formal verification, such as model checking and theorem proving, as well as incomplete solutions such as testing and debugging. The annual long running workshop RV is dedicated to these techniques, and starting with year 2010, RV is an international conference.
Distributed runtime verification (DRV) is less developed. Designing a decentralized runtime monitor for a distributed system is an especially difficult task since it involves designing distributed algorithms to coordinate the estimation by different monitors of the order of events in order for them to reason consistently about the temporal behavior of the system. It is about designing a fault-tolerant distributed algorithm that monitors another distributed algorithm.
This tutorial will provide an overview of distributed runtime verification (DRV), and give an introduction to the different types of techniques used, which range from formal methods techniques related to LTL and multi-valued logics, on the one hand, to algorithmic techniques related to computing snapshots in an efficient manner to reason about temporal properties of a distributed system, on the other hand, and passing through combinatorial and topological techniques. RV is an exemplary area for interdisciplinary research opportunities, given that logic and algorithmic techniques converge, and few papers explore the difficulties introduced when failures and asynchrony can occur in the system.
