Le vendredi 21 juin à 13h30 en salle 301, Swan DUBOIS, membre du Laboratoire d’Informatique de Paris 6 (LIP6), viendra faire un séminaire au sein du laboratoire.
Résumé : Distributed systems are a generic model for numerous real systems as wired or mobile networks, shared-memory multi-processor systems, and so on. From an algorithmic point of view, it is well-known that strong assumptions (as asynchronicity or mobility) on such systems lead often to impossibility results or high lower bounds on complexity. In this talk, we focus on algorithms that adapt themselves to their environment (\ie the union of all assumptions on the system) by focusing on the two following approaches. Graceful degradation circumvents impossibility results by degrading the properties offered by the algorithm as the environment become stronger. Speculation allows to bypass high lower bounds on complexity by optimizing the algorithm only on more probable environments. Robot networks are a particular case of distributed systems where processes are endowed with sensors and able to move from a location to another. We consider dynamic environments in which this ability may evolve with time. This talk answers positively to the open question whether it is possible and attractive to apply gracefully degrading and speculative approaches to robot networks in dynamic environments. This answer is obtained through contributions on gracefully degrading gathering (where all robots have to meet on the same location in finite time) and on speculative perpetual exploration (where robots must visit infinitely often each location).
