Dipartimento di Ingegneria informatica, automatica e gestionale

Computing systems and networks are more and more becoming dynamic. The static and relatively stable models of computation can no longer represent a plethora of rapidly emerging new technologies. In recent years, we have seen a tremendous increase in the number of new mobile computing devices. Even the Internet has become mobile. Traditional approached have usually considered causes of dynamicity, such as failures, that induce a low rate of (temporary) topological changes. This is unsuitable for reasoning about truly dynamic networks, which may change at a very high rate and in a worst-case manner. Even graph-theoretic techniques need to be revisited: the suitable graph model is now that of a temporal graph, which, in the discrete case, may be viewed as a time-sequence of static graphs. Though static graphs have been extensively studied, for their temporal generalization we are still far from having a concrete set of structural and algorithmic principles. Additionally, it is not yet clear how is the complexity of combinatorial optimization problems affected by introducing to them a notion of time.

In this talk, we will survey our and others research in the fascinating and steadily growing area of dynamic networks. We will cover two equally important sub-areas: (i) distributed models and algorithms for dynamic networks and (ii) structural and algorithmic properties of temporal graphs. In the distributed computing part, we will begin by discussing the population protocol model (one of the first models in this area), which has served as a quite general model of computation in dynamic environments, as a model of distributed construction of networks and shapes, and which is related to chemical and algorithmic self-assembly models. Then we will revisit classical distributed tasks, like counting, naming, and information dissemination, in worst-case dynamic networks. Finally, we will turn our attention to the underlying model of temporal graphs. We will prove a temporal analogue of Menger's theorem, we will discuss the problem of designing an "efficient" temporal graph, given some requirements that the graph should meet, and we will touch on (algorithms and complexity of) temporal versions of classical graph problems.

Bio: Othon Michail is a Senior Researcher in the RU1 of the Computer Technology Institute (CTI) and an Adjunct Faculty at the University of Patras. He is the CI and Project Manager of project FOCUS (2012-2015), which is a regional grant for excellence in science and technology and studies the foundations of dynamic distributed systems and networks. He has also worked as a key researcher in several high-quality EU FET/FP7 research projects, such as FRONTS and VITRO. He is one of the authors of the book "New Models for Population Protocols" appearing in a series edited by Prof. Nancy Lynch (MIT). His research interests include Distributed and Mobile Computing, Modeling and Analyzing novel ICT systems, Theory of Computation, and Design and Analysis of Algorithms. He has been a PC Member of the international conferences ACM PODC 2015 and CIAC 2013.