Programme & Pre-proceedings

23rd International Colloquium on Structural Information and Communication Complexity

19–21 July 2016 · Helsinki, Finland

Tuesday | Wednesday | Thursday | |
---|---|---|---|

19 July 2016 | 20 July 2016 | 21 July 2016 | |

9:00am | keynote lecture: Yoram Moses |
award lecture: Masafumi Yamashita |
invited talk: Danupon Nanongkai |

10:00am | coffee | coffee | coffee |

10:30am | 4 × presentation | 4 × presentation | 4 × presentation |

12:00pm | lunch | lunch | lunch |

1:40pm | invited talk: Keren Censor-Hillel |
invited talk: Adrian Kosowski |
invited talk: Thomas Sauerwald |

2:40pm | 2 × presentation | coffee | 2 × presentation |

3:20pm | coffee | walking tour | coffee |

4:00pm | 5 × presentation (until 5:40pm) |
excursion (until 7:00pm) |
4 × presentation (until 5:20pm) |

7:00pm | dinner |

All contributed talks have 20-minute slots in the programme. Coffee will be served at the conference site. Lunch is served at Restaurant Helka, which is a 5-minute walk from the conference site. See the local information page for more details on the venue and the social programme.

The conference programme is also available as a PDF file for easier printing.

Tuesday, 19 July 2016 | ||
---|---|---|

9:00am | Yoram Moses | A principled way of designing efficient distributed protocols (keynote lecture) |

session chair: Jukka Suomela | ||

10:00am | coffee | |

10:30am | Othon Michail and Paul Spirakis | How Many Cooks Spoil the Soup? |

10:50am | Jara Uitto and Yuval Emek | Dynamic Networks of Finite State Machines |

11:10am | Ralf Klasing, Adrian Kosowski and Dominik Pajak | Setting Ports in an Anonymous Network: How to Reduce the Level of Symmetry? |

11:30am | Gopal Pandurangan, David Peleg and Michele Scquizzato | Message Lower Bounds via Efficient Network Synchronization |

session chair: Keren Censor-Hillel | ||

11:50am | break | |

12:00pm | lunch at Restaurant Helka | |

1:40pm | Keren Censor-Hillel | The Landscape of Lower Bounds for the Congest Model (invited talk) |

2:40pm | Orr Fischer, Rotem Oshman and Uri Zwick | Public vs. Private Randomness in Simultaneous Multi-Party Communication Complexity |

3:00pm | Shay Moran, Makrand Sinha and Amir Yehudayoff | Fooling Pairs in Randomized Communication Complexity |

session chair: Pierre Fraigniaud | ||

3:20pm | coffee | |

4:00pm | Armando Castaneda, Pierre Fraigniaud, Eli Gafni, Sergio Rajsbaum and Matthieu Roy | Asynchronous Coordination Under Preferences and Constraints |

4:20pm | James Aspnes, Keren Censor-Hillel and Eitan Yaakobi | Concurrent use of write-once memory |

4:40pm | Vincent Gramoli, Petr Kuznetsov and Srivatsan Ravi | In the Search for Optimal Concurrency |

5:00pm | Gal Amram | The F-snapshot Problem |

5:20pm | Hugues Fauconnier, Michel Raynal, Carole Delporte-Gallet and Sergio Rajsbaum | Revisiting Immediate Snapshot |

session chair: Yoram Moses | ||

5:40pm | end | |

Wednesday, 20 July 2016 | ||

9:00am | Masafumi (Mark) Yamashita | Towards a Theory of Formal Distributed Systems (award lecture) |

session chair: Andrzej Pelc | ||

10:00am | coffee | |

10:30am | Evangelos Bampas, Jurek Czyzowicz, Leszek Gasieniec, David Ilcinkas, Ralf Klasing, Tomasz Kociumaka and Dominik Pajak | Linear search by a pair of distinct-speed robots |

10:50am | Samir Elouasbi and Andrzej Pelc | Deterministic Meeting of Sniffing Agents in the Plane |

11:10am | Piotr Borowiecki, Shantanu Das, Dariusz Dereniowski and Lukasz Kuszner | Distributed Evacuation in Graphs with Multiple Exits |

11:30am | Giovanni Viglietta, Paola Flocchini, Nicola Santoro and Masafumi Yamashita | Universal Systems of Oblivious Mobile Robots |

session chair: Christopher Purcell | ||

11:50am | break | |

12:00pm | lunch at Restaurant Helka | |

1:40pm | Adrian Kosowski | What Makes a Distributed Problem Truly Local? (invited talk) |

session chair: Janne H. Korhonen | ||

2:40pm | coffee | |

3:20pm | walking tour (from conference site to Halkolaituri) | |

4:00pm | excursion and business meeting on Schooner Linden (departs and arrives at Halkolaituri) | |

7:00pm | conference dinner at Katajanokan Kasino (a short walk from Halkolaituri) | |

Thursday, 21 July 2016 | ||

9:00am | Danupon Nanongkai | Challenges in Distributed Shortest Paths Algorithms (invited talk) |

session chair: Adrian Kosowski | ||

10:00am | coffee | |

10:30am | Lewis Tseng | Recent Results on Fault-Tolerance Consensus in Message-Passing Networks (survey) |

10:50am | Alkida Balliu, Pierre Fraigniaud, Zvi Lotker and Dennis Olivetti | Sparsifying Congested Cliques and Core-Periphery Networks |

11:10am | Jurek Czyzowicz, Krzysztof Diks, Jean Moussi and Wojciech Rytter | Communication Problems for Mobile Agents Exchanging Energy |

11:30am | Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Barbara Geissmann, Daniel Graf, Arnaud Labourel and Matúš Mihalák | Collaborative Delivery with Energy-Constrained Mobile Robots |

session chair: Thomas Sauerwald | ||

11:50am | break | |

12:00pm | lunch at Restaurant Helka | |

1:40pm | Thomas Sauerwald | A Survey on Smoothing Networks (invited talk) |

2:40pm | Kokouvi Hounkanli and Andrzej Pelc | Asynchronous Broadcasting with Bivalent Beeps |

3:00pm | Philipp Brandes, Marcin Kardas, Marek Klonowski, Dominik Pajak and Roger Wattenhofer | Approximating the Size of a Radio Network in Beeping Model |

session chair: Rotem Oshman | ||

3:20pm | coffee | |

4:00pm | Fabian Kuhn, Yannic Maus and Sebastian Daum | Rumor Spreading with Bounded In-Degree (best paper) |

4:20pm | Manuel Lafond, Lata Narayanan and Kangkang Wu | Whom to befriend to influence people |

4:40pm | Guy Even, Matthias Rost and Stefan Schmid | An Approximation Algorithm for Path Computation and Function Placement in SDNs |

5:00pm | Saeed Akhoondian Amiri, Arne Ludwig, Jan Marcinkowski and Stefan Schmid | Transiently Consistent SDN Updates: Being Greedy is Hard |

session chair: Jukka Suomela | ||

5:20pm | end |

Lecture by the recipient of the 2016 SIROCCO Prize for Innovation in distributed computing

**Abstract:**
In the title, the word *towards* means incomplete, immature or not ready
for presenting, and the word *formal* means unrealistic, imaginary
or useless. Please keep them in mind.

One might find similarity between two phenomena, seabirds competing for good nesting places in a small island and cars looking (or fighting) for parking space. Regardless of whether conscious or unconscious, they are solving a conflict resolution problem, which is a well-known problem in distributed computing (in computer science). This suggests us there are many (artificial or natural) systems that are in the face of solving distributed problems.

Lamport and Lynch claimed “although one usually speak of a
distributed system, it is more accurate to speak of a distributed
*view* of a system,” after defining the word *distributed*
to mean spread across space. This claim seems to imply that every system
is a distributed system at least from the view of atoms or molecules,
and may be in the face of solving a distributed problem,
when we concentrate on the distributed view,
like seabirds and cars in the example above.

An abstract distributed view, which we call a *formal distributed system*
(FDS), describes how system elements interact logically. Our final goal is
to understand a variety of FDSs and compare them in terms of the solvability
of distributed problems.

We first propose a candidate for the model of FDS in such a way that it can describe a wide variety of FDSs, and explain that many of the models of distributed systems (including ones suitable to describe biological systems) can be described as FDSs. Compared with other distributed system models, FDSs have two features: First, the system elements are modeled by points in $d$-dimensional space, where $d$ can be greater than 3. Second incomputable functions can be taken as transition functions (corresponding to distributed algorithms).

We next explain some of our ongoing works in three research areas, localization, symmetry breaking and self-organization. In localization, we discuss the simplest problem of locating a single element with limited visibility to the center of a line segment. In symmetry breaking, we observe how elements in 3D space can eliminate some symmetries. Finally in self-organization, we examine why natural systems appear to have richer autonomous properties than artificial systems, despite that the latter would have stronger interaction mechanisms, e.g., unique identifiers, memory, synchrony, and so on.

The **pre-proceedings versions** of all papers are **available for download**! You can click on the titles of the individual papers below, you can browse all files in this directory, or you can download all papers as a zip file (10 MB). Please note that these are preliminary versions of the papers. The post-proceedings of SIROCCO 2016 with the final versions of these papers have been published by Springer in the Lecture Notes in Computer Science (LNCS) series.

How Many Cooks Spoil the Soup?The definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_1.

Dynamic Networks of Finite State MachinesThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_2.

Setting Ports in an Anonymous Network: How to Reduce the Level of Symmetry?The definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_3.

Fooling Pairs in Randomized Communication ComplexityThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_4.

Public vs. Private Randomness in Simultaneous Multi-Party Communication ComplexityThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_5.

Message Lower Bounds via Efficient Network SynchronizationThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_6.

Recent Results on Fault-Tolerance Consensus in Message-Passing NetworksThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_7.

Asynchronous Coordination Under Preferences and ConstraintsThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_8.

Concurrent use of write-once memoryThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_9.

In the Search for Optimal ConcurrencyThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_10.

The F-snapshot ProblemThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_11.

Revisiting Immediate SnapshotThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_12.

Linear search by a pair of distinct-speed robotsThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_13.

Deterministic Meeting of Sniffing Agents in the PlaneThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_14.

Distributed Evacuation in Graphs with Multiple ExitsThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_15.

Universal Systems of Oblivious Mobile RobotsThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_16.

Collaborative Delivery with Energy-Constrained Mobile RobotsThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_17.

Communication Problems for Mobile Agents Exchanging EnergyThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_18.

Asynchronous Broadcasting with Bivalent BeepsThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_19.

Sparsifying Congested Cliques and Core-Periphery NetworksThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_20.

Rumor Spreading with Bounded In-DegreeThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_21.

Whom to befriend to influence peopleThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_22.

Approximating the Size of a Radio Network in Beeping ModelThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_23.

An Approximation Algorithm for Path Computation and Function Placement in SDNsThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_24.

Transiently Consistent SDN Updates: Being Greedy is HardThe definitive version is available at link.springer.com, doi:10.1007/978-3-319-48314-6_25.

- Saeed Akhoondian Amiri · Technical University Berlin
- Gal Amram · Ben-Gurion University
- Alkida Balliu · CNRS Univ. Paris 7 and GSSI L'Aquila
- Keren Censor-Hillel · Technion
- Jurek Czyzowicz · Université du Québec en Outaouais
- Shantanu Das · Aix-Marseille University
- Carole Delporte · Université Paris Diderot
- Burkhard Englert · CSULB
- Hugues Fauconnier · Université Paris-Diderot IRIF
- Orr Fischer · Tel-Aviv University
- Pierre Fraigniaud · CNRS and University Paris Diderot
- Mika Göös · University of Toronto
- Daniel Graf · ETH Zürich
- Juho Hirvonen · Aalto University
- Marcin Kardas · Wroclaw University of Technology
- Janne H. Korhonen · Reykjavik University
- Zuzanna Kosowska-Stamirowska · Institute of Complex Systems of Paris, CNRS
- Adrian Kosowski · LIAFA
- Łukasz Kuszner · Gdańsk Univ. of Technology
- Petr Kuznetsov · Telecom ParisTech
- Manuel Lafond · Université de Montréal
- Tuomo Lempiäinen · Aalto University
- Mikko Malinen · University of Eastern Finland
- Yannic Maus · University of Freiburg
- Shay Moran · Technion
- Yoram Moses · Technion
- Danupon Nanongkai · KTH Royal Institute of Technology
- Dennis Olivetti · GSSI, L'Aquila and CNRS Univ. Paris 7
- Rotem Oshman · Tel Aviv University
- Dominik Pajak · Wroclaw University of Science and Technology
- Boaz Patt-Shamir · Tel Aviv University
- Andrzej Pelc · University of Quebec
- Christopher Purcell · Aalto University
- Ivan Rapaport · Universidad de Chile
- Michel Raynal · IRISA, Rennes
- Matthias Rost · TU Berlin
- Matthieu Roy · LAAS, CNRS, Toulouse
- Joel Rybicki · Aalto University
- Thomas Sauerwald · University of Cambridge
- Michele Scquizzato · University of Houston
- Paul Spirakis · U. of Liverpool and CTI
- Jukka Suomela · Aalto University
- Lewis Tseng · University of Illinois at Urbana-Champaign
- Jara Uitto · Comerge AG
- Giovanni Viglietta · University of Ottawa
- Chris Wastell · Durham University
- Masafumi (Mark) Yamashita · Kyushu University
- Yukiko Yamauchi · Kyushu University

- Web: sirocco2016.hiit.fi
- Email: sirocco2016@hiit.fi
- Twitter: @sirocco2016
- Local chair: Jukka Suomela