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.
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
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.
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.