CS Forum: Mikaël Rabie, LIP - ENS de Lyon

2017-07-19 14:15:00 2017-07-19 15:00:00 Europe/Helsinki CS Forum: Mikaël Rabie, LIP - ENS de Lyon CS department's public guest lecture on 'Time and Homonyms Considerations over Community Protocols'. The lecture is open to everyone free-of-charge. http://cs.aalto.fi/en/midcom-permalink-1e7688c945e4986688c11e7bbce0bfca8c897a397a3 Konemiehentie 2, 02150, Espoo

CS department's public guest lecture on 'Time and Homonyms Considerations over Community Protocols'. The lecture is open to everyone free-of-charge.

19.07.2017 / 14:15 - 15:00
seminar room T5, Konemiehentie 2, 02150, Espoo, FI

Mikaël Rabie
LIP - ENS de Lyon

Host: Prof. Jukka Suomela
Time: 14:15 (coffee at 14:00)
Venue: T5, CS building

Time and Homonyms Considerations over Community Protocols

Abstract:

Guerraoui and Ruppert introduced the model of Community Protocols. This Distributed System works with agents having a finite memory and unique identifiers (the set of identifiers being ordered). Each agent can store a finite number of identifiers they heard about. The interactions are asynchronous and pairwise, following a fair scheduler. The computation power of this model is fully characterized: it corresponds exactly to what non deterministic Turing Machines can compute on a space O(n log n).

In this talk, I will focus on two restrictions of the model:
The first is what happens when agents may share identifiers, the population admitting homonyms. I will introduce a hierarchy, with characterizations depending on the rate of unique identifiers present in the population. The main result is that with log n identifiers, a Turing Machine with a polylogarithmic space can be simulated.

The second considers the following time restriction: what can be computed in a polylogarithmic number of parallel interactions. This version is not yet characterized, but I will provide some impossibility results, some computable protocols, and I will give the tighter bound we found.

Bio:

Mikaël Rabie: Currently in a Teaching Position in the LIP - ENS de Lyon. PhD received in 2015 under the supervision of Olivier Bournez in the Ecole Polytechnique, titled "The Power of Weaknesses, what can be Computed with Populations, Protocols and Machines". Main research interests: Distributed Algorithm, Complexity, Computability, Graph Theory.