Frédéric Desprez (INRIA Grenoble) and Adrien Lebre (IMT Atlantique)

(R)Evolution of the computing continuum

Initially proposed to interconnect computers worldwide, the Internet has significantly evolved to become in two decades a key element in almost all our activities. This (r)evolution mainly relies on the progress that has been achieved in computation and communication fields and that has led to the well-known and widely spread Cloud Computing paradigm.

With the emergence of the Internet of Things (IoT), stakeholders expect a new revolution that will push, once again, the limits of the Internet, in particular by favouring the convergence between physical and virtual worlds. This convergence is about to be made possible thanks to the development of minimalist sensors as well as complex industrial physical machines that can be connected to the Internet through edge computing infrastructures.

Among the obstacles to this new generation of Internet services is the development of a convenient and powerful framework that should allow operators, and devops, to manage the life-cycle of both the digital infrastructures and the applications deployed on top of these infrastructures, throughout the cloud to IoT continuum.

In this keynote, Frédéric Desprez and his colleague Adrien Lebre will present research issues and provide preliminary answers to identify whether the challenges brought by this new paradigm is an evolution or a revolution for our community.

Biography:

Frédéric Desprez is Senior Researcher at Inria. He obtained a PhD in computer science from the Institut National Polytechnique de Grenoble in 1994 working on parallel linear algebra problems at the Ecole Normale Supérieure de Lyon. He obtained a postdoctoral fellowship at the University of Tennessee, Knoxville in the ICL group of Jack Dongarra. He began his career as a lecturer at ENSEIRB (Bordeaux) before joining Inria as a researcher in the ReMaP team at ENS Lyon (under the supervision of Yves Robert). In 2002, he became a research director at INRIA and created the GRAAL team. In 2014, he joined the Corse research team working on compilation optimization for linear algebra problems and autotuning of numerical kernels. Between 2001 and 2006, he was deputy director of the LIP laboratory at ENS Lyon, France, and between 2006 and January 2009 director of LIP. In 2010, he co-founded the startup SysFera where he was a scientific advisor. Between 2012 and 2021, he served as deputy to the scientific director in charge of high performance computing, distributed systems, networking and software engineering. Since September 2021, he is the director of the INRIA Grenoble Rhône-Alpes research center. Frédéric's research activities include parallel algorithms, resource management for large-scale distributed platforms, cloud and edge computing and large-scale experimental infrastructures. He leads the Grid'5000 project, which provides a French infrastructure for experimental research on various aspects of distributed computing and networks, from small connected objects to large data centers of tomorrow.

Adrien Lebre is a full professor at IMT Atlantique (France) and head of the STACK research group, which deals with challenges related to the management and advanced usages of digital infrastructures (i.e. Cloud, Fog, Edge, and beyond). Adrien Lebre holds a Ph.D. from Grenoble Institute of Technologies and a habilitation from University of Nantes. His activities focus on large-scale distributed systems, their design, compositional properties and efficient implementation. Since 2015, his activities have been mainly focusing on the Edge Computing paradigm, in particular in the OpenStack, and more recently, Kubernetes ecosystems. Adrien Lebre is also strongly involved in several initiatives related to experiment-driven research on digital infrastructures (Silecs/Slices).

Fabian Kuhn (University of Freiburg)

Algorithmic Tools for Efficient Deterministic Distributed Symmetry Breaking

The problem of obtaining fast deterministic algorithms for distributed symmetry breaking problems in graphs has long been considered one of the most challenging problems in the area of distributed graph algorithms. Consider for example the distributed coloring problem, where a (computer) network is modeled by an arbitrary graph G = (V,E) and the objective is to compute a vertex coloring of G by running a distributed algorithm on the graph G. It is maybe not surprising that randomization can be a helpful tool to efficiently compute such a coloring. As long as each node v in V can choose among deg(v)+1 different colors, even an almost trivial algorithm in which all nodes keep trying a random available color allows to color all nodes in O(log n) parallel steps. How to obtain a similarly efficient deterministic algorithm is however far less obvious. In fact, for a long time, there has been an exponential gap between the time complexities of the best randomized and the best deterministic distributed algorithms for various graph coloring variants and many other basic graph problems. In the last few years, there however has been substantial progress and we now have deterministic distributed graph algorithms that are nearly as fast as the classic randomized algorithms for the same tasks.

In the first part of the talk, we give an overview on the history of the problem of finding fast deterministic algorithms for distributed symmetry breaking problems. In the second part, we then discuss a concrete, novel distributed derandomization technique that in many cases leads to particularly efficient and also particularly simple deterministic distributed algorithms. One interprets a given randomized algorithm (with certain nice properties) as a fractional relaxation of the problem at hand. This fractional solution is then gradually rounded to an integral solution that approximately preserves the expected quality of the initial randomized algorithm. The method leads to the current fastest deterministic algorithms for various important distributed graph problems.

Biography:

Fabian Kuhn received his M.Sc degree in computer science in 2001 and his Ph.D. degree in 2005, both from ETH Zurich in Switzerland. He then spent time as a postdoctoral researcher at Microsoft Research Silicon Valley, at ETH Zurich, and at MIT. In the following, he was an assistant professor at the University of Lugano in Switzerland and in 2012, he joined the University of Freiburg in Germany as a full professor, where he heads the Chair of Algorithms and Complexity. Fabian Kuhn is interested in a wide range of topics in theoretical computer science, especially in the area of distributed algorithms. In particular, his research interests include the complexity of graph-theoretic problems in a distributed context and the algorithmic foundations of mobile and wireless networks.