Conference Program

Sirocco Program

INVITED SPEAKERS

Susanne Albers, TU München, Germany

Susanne Albers is professor in Department of Informatics at Technical University of Munich. She received her PhD degree from the Max Planck Institute for Informatics and Saarland University in 1993. Her research interests are in the design and analysis of algorithms, with emphasis on online and approximation algorithms as well as algorithmic game theory. She serves on the editorial boards of several journals, e.g. the Journal of Computer and System Sciences, Algorithmica, the ACM Transactions on Algorithms and the Journal of Graph Algorithms and Applications. Susanne Albers is Fellow of the EATCS . In 2016 she was awarded an ERC Advanced Grant.

Talk: “On Energy Conservation in Data Centers”

Energy conservation has become a major concern in data centers. In this talk we study algorithmic problems in data center operations with the objective to minimize the consumed energy. The general goal is to dynamically right-size the pool of active servers depending on the current workload. For basic problems, we examine their complexity, develop exact and approximation algorithms and present online strategies. The solutions to some of the problems can be reduced to the computation of min-cost max-flows or shortest paths in associated networks. The research work belongs to the more general, timely scientific strand of energy-efficient computing.

Pierre Fraigniaud, CNRS and University Paris Diderot, France

Pierre Fraigniaud got his PhD degree in Computer Science from ENS Lyon in 1990. He joined CNRS in 1991. From Jan 2010 to Dec 2017, he was successively director of LIAFA (Laboratoire d’Informatique Algorithmique) located at University Paris Diderot, and of IRIF (Institut de Recherche en Informatique Fondamentale) located at Université de Paris.

Pierre Fraigniaud’s main research interest is parallel and distributed computing, and specifically the design and analysis of distributed algorithms and data structures for networks. He is member of the Editorial Boards of Distributed Computing (DC), and Theory of Computing Systems (TOCS), and he was Program Committee Chair of IPDPS 2017 (track Algorithms), ICALP 2014 (track Foundations of networked computation), PODC 2011, DISC 2005, SPAA 2001, and EuroPar 1996.

In 2012, Pierre Fraigniaud received the Silver Medal from CNRS, and, in 2014, he received the SIROCCO Prize for Innovation in Distributed Computing.

Talk: “A Topological Perspective on Distributed Network Computing”

This talk will introduce the audience with the use of algebraic topology, a.k.a. combinatorial topology, for analyzing the complexity of problems in the distributed computing setting. After surveying some of the important achievements obtained using algebraic topology applied to distributed computing under shared memory or message-passing systems, the talk will describe some new results obtained by applying topology to distributed computing in networks.

Joint work with: A. Castañeda, A. Paz, S. Rajsbaum, M. Roy, and C. Travers

Merav Parter, Weizmann Institute of Science, Israel

Merav Parter is faculty member in the compute science department of Weizmann Institute, Israel. She received her Phd under the guidance of Prof. David Peleg. She was later a postdoctoral fellow at the EECS department of CSAIL, MIT. Her main research interests include distributed graph algorithms, fault tolerant network design and the synergy of these topics with cryptography and biological systems.

Talk: “Secure Distributed Algorithms”

In the area of distributed graph algorithms a number of network’s entities with
local views solve some computational task by exchanging messages with their
neighbors. Quite unfortunately, an inherent property of most existing
distributed algorithms is that throughout the course of their execution, the
nodes get to learn not only their own output but rather learn quite a lot on
the inputs or outputs of many other entities.

We present a new framework for secure distributed graph
algorithms and provide the first general compiler that takes any
”natural” non-secure distributed algorithm that runs in r rounds, and turns
it into a secure algorithm that runs in O(r \cdot D \cdot
\poly(\Delta))$ rounds where $\Delta$
is the maximum degree in the graph and $D$ is its diameter.

The main technical part of our compiler is based on a new cycle cover theorem:
We show that the edges of every bridgeless graph G of diameter D can be
covered by a collection of cycles such that each cycle is of length
$\widetilde{O}(D)$ and each edge of the graph $G$ appears in
$\widetilde{O}(1)$ many cycles.

In the second part of the talk, I will also discuss the notion of optimality in secure computation. We will see how to adapt the existentially nearly optimal compiler into one that is nearly \emph{optimal} (w.r.t.\ running time) for the given input graph $G$.

Paola Flocchini, University of Ottawa

SIROCCO 2019 will also feature a talk by Paola Flocchini, University of Ottawa, Canada – recipient of the 2019 Prize for Innovation in Distributed Computing.Prof. Flocchini received her PhD from the University of Milan (Italy) and joined the School of Electrical Engineering and Computer Science at the University of Ottawa shortly thereafter. Now a Full Professor and University Research Chair in distributed computing, her main research area is theoretical computer science, specifically, distributed computing with special focus on mobility (“moving and computing”) and on dynamicity (“time-varying graphs”). She is interested in fundamental computational and algorithmic issues that arise among autonomous mobile computational entities, in the design of algorithmic solutions in the context of dynamic networks, and in sense of direction and other structural information.

Read the complete Laudatio.

Talk: On Sense of Direction and Mobile Agents

An edge-labeled graph is said to have Sense of Direction if the labeling satisfies a particular set of global consistency properties. When the graph represents a system of communicating entities, the presence of sense of direction has been shown to have a strong impact on computability and complexity.
Since its introduction, sense of direction has been investigated from various view points, revealing interesting graph theoretical properties and providing useful tools for the design of efficient distributed algorithms; furthermore, its presence allows to solve some otherwise unsolvable problems.
Far from being exhausted, the study of sense of direction and other consistency properties of edge-labeled graphs is still filled with interesting questions, open problems, and important new research directions.
In this talk, sense of direction is revisited reviewing the main results in the context of message passing point-to-point models, discussing its impact in the more recent mobile agents models, and indicating research directions for future study.

 

Roger Wattenhofer, ETH Zurich

Roger Wattenhofer is a full professor at the Information Technology and Electrical Engineering Department, ETH Zurich, Switzer­land. He received his doctorate in Computer Science from ETH Zurich. He also worked some years at Microsoft Research in Redmond, Washington, at Brown University in Providence, Rhode Island, and at Macquarie University in Sydney, Australia.

Roger Wattenhofer’s research interests are a variety of algorithmic and systems aspects in computer science and information technology, e.g., distributed systems, positioning systems, wireless networks, mobile systems, social networks, deep neural networks. He publishes in different communities: distributed computing (e.g., PODC, SPAA, DISC), networking and systems (e.g., SIGCOMM, MobiCom, SenSys, OSDI), and algorithmic theory (e.g., STOC, FOCS, SODA, ICALP). His work received multiple awards, e.g. the Prize for Innovation in Distributed Computing for his work in Distributed Approximation. He published the book “Blockchain Science: Distributed Ledger Technology“, which has been translated to Chinese, Korean and Vietnamese.

More information: complete CV, selected publications, google scholar, dblp, wikipedia, imdb, group page.

Sirocco conference will host a special lecture on Blockchain, 1 July

I cover a variety of topics on permissioned and permissionless blockchains. The morning lecture is for those participants who have never heard of fault-tolerant distributed systems. I cover some basic material which is often taught in computer sciences courses on distributed systems, such as Paxos, Consensus, Byzantine Fault-Tolerance. The second part is on permissionless blockchains, systems a la Bitcoin. The third and final part is on current research. This part may also be interesting for those who know blockchains well. I will try to tailor the material a bit towards a Sirocco audience, i.e., explain some interesting aspects that are related to information in networks.

Lecture Material:

(Most material is taken from this class.)