Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) Parallel Systems
Slow Molecule Revolution
David Doty

05 July 2017, 10:30
Salle/Bat : 465/PCRI-N
Contact :

Activités de recherche : Distributed algorithms

Résumé :
Suppose to function correctly, a chemical system requires a single molecule of a certain species L. Preparing a solution with just a single copy of L is a difficult task to achieve with imprecise pipettors. Could we engineer artificial reactions (a chemical election algorithm, so to speak) that whittle down an initially large count of L to 1? Yes, with the reaction L+L→L+F: whenever two candidate leaders encounter each other, one drops out of the race. In volume v convergence to a single L requires expected time proportional to v; the final reaction --- two lone L's seeking each other in the vast expanse of volume v --- dominates the whole expected time.

One might hope that more cleverly designed reactions could elect a leader more quickly. We dash this hope: L+L→L+F, despite its sloth, is the fastest chemical algorithm for leader election there is (subject to some reasonable constraints on the reactions). The techniques generalize to establish lower bounds on the time required to do other distributed computing tasks, such as computing which of two species X or Y holds an initial majority, whether the initial number of X's is odd, or cutting the total number of X's in half.

Pour en savoir plus : https://parsys.lri.fr/seminar.html
Séminaires
A Two-level Auction for Resource Allocation in Mul
Wireless and mobile networks
Friday 09 March 2018 - 14:30
Salle : 445 - PCRI-N
Mira Morcos .............................................

Binary pattern of length greater than 14 are abeli
Combinatorics
Friday 09 February 2018 - 14:30
Salle : 445 - PCRI-N
Matthieu Rosenfeld .............................................

Approximate Bayesian Computation and Random Forest
Thursday 08 February 2018 - 00:00
Salle : 455 - PCRI-N
Valentin Thouzeau .............................................

A concurrent lock-free algorithm for computing a f
Combinatorics
Friday 12 January 2018 - 14:30
Salle : 445 - PCRI-N
James Mitchell .............................................

Acyclic Partitioning of Large Directed Acyclic Gra
High-performance computing
Tuesday 09 January 2018 - 10:30
Salle : 465 - PCRI-N
Julien Herrmann .............................................