Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) ParSys
Space-Optimal Counting in Population Protocols
Janna Burman

08 December 2015, 10h30
Salle/Bat : 465/PCRI-N
Contact :

Activités de recherche : Algorithmique distribuée

Résumé :
In this paper, we study the fundamental problem of counting, which consists in computing the size of a system. We consider the distributed communication model of population protocols of finite state, anonymous and asynchronous mobile devices (agents) communicating in pairs (according to a fairness condition). This work significantly improves the previous results known for counting in this model, in terms of (exact) space complexity. We present and prove correct the first space optimal protocols solving the problem for two classical types of fairness, global and weak. Both protocols require no initialization of the counted agents.

The protocol designed for global fairness, surprisingly, uses only one bit of memory (two states) per counted agent. The protocol, functioning under weak fairness, requires the necessary log P bits (P states, per counted agent) to be able to count up to P agents. Interestingly, this protocol exploits the intriguing Gros sequence of natural numbers, which is also used in the solutions to the Chinese Rings and the Hanoi Towers puzzles.

Pour en savoir plus : https://parsys.lri.fr/seminar.html
Séminaires
Binary pattern of length greater than 14 are abeli
Combinatoire
Friday 29 June 2018 - 14h30
Salle : 445 - PCRI-N
Matthieu Rosenfeld .............................................

Resilient PDE solving approaches for exascale comp
Calcul à haute performance
Tuesday 29 May 2018 - 10h30
Salle : 465 - PCRI-N
Paul Mycek .............................................

Decentralized Data Management for the Semantic Web
Intégration de données et de connaissances
Thursday 24 May 2018 - 14h00
Salle : 445 - PCRI-N
Hala Skaf-Molli .............................................

Efforts in Machine Topology-Aware Global Schedulin
Calcul à haute performance
Tuesday 22 May 2018 - 10h30
Salle : 465 - PCRI-N
Laércio LIMA PILLA .............................................

Collaborative delivery by robots that can share en
Algorithmique distribuée
Wednesday 02 May 2018 - 10h30
Salle : 465 - PCRI-N
Evangelos Bampas .............................................