Evènement pour le groupe Algorithmique Distribuée

Date 2016-03-14  14:00-15:00
TitreTime and Homonyms Considerations over Community Protocols 
Résumé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(nlog 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 consider 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.  
OrateurMikaël Rabie 
UrlLAMSADE, U. Paris Dauphine 

Aucun document lié à cet événement.

Retour à l'index