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

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

Activités de recherche : Algorithmique distribuée

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
Measuring Similarity between Logical Arguments
Raisonnement automatique
Monday 06 March 2023 - 00h00
Salle : 0 - 650
Victor David .............................................

Imputing Out-of-Vocabulary Embeddings with LOVE Ma
Langages et systèmes centrés données
Monday 20 February 2023 - 00h00
Salle : 455 - PCRI-N
Lihu Chen .............................................

On the Interplay between Software Product Lines an
Raisonnement automatique
Tuesday 18 October 2022 - 14h15
Salle : 2013 - DIG-Moulon
Vander Alves .............................................

Combining randomized and observational data: Towar
Raisonnement automatique
Thursday 13 October 2022 - 10h30
Salle : 2011 - DIG-Moulon
Bénédicte Colnet .............................................

New Achievements of Artificial Intelligence in Mul
Raisonnement automatique
Tuesday 11 October 2022 - 14h15
Salle : 2013 - DIG-Moulon
.............................................