Complexité du consensus anonyme en l'absence de concurrence

Claire Capdevielle (1, 2) , Colette Johnen (2, 1) , Petr Kuznetsov (3) , Alessia Milani (2, 1)

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique
2 UB - Université de Bordeaux
3 Télécom ParisTech

Le consensus est l'une des abstractions fondamentales du distribué. En permettant a un ensemble de processus de se mettre d'accord sur l'une des valeurs qu'ils proposent, le consensus peut être utilisé pour implémenter , de manière cohérente et tolérante aux fautes, n'importe quel service distribué. Dans ce papier nous étudions la complexité du consensus anonyme en l'absence de concurrence : comptant le nombre d'emplacements mémoire et d'´ écritures lors d'une opération qui ne rencontre aucune concurrence. En supposant que les opérations privilégient les écritures et les lectures " simples " et ont recours a des primitives plus coûteuses , tel le CAS, seulement lorsque la concurrence est détectée , nous obtenons, pour ce type d'implémentation appelé " interval-solo-fast " , une borne atteignable pour la complexité en espace.

Mots clés: complexité en espace; borne inferieur; consensus; interval contention; solo-fast; complexité en temps

Domaines: Complexité [cs.CC]; Calcul parallèle, distribué et partagé [cs.DC]; Algorithme et structure de données [cs.DS]

Claire Capdevielle, Colette Johnen, Petr Kuznetsov, Alessia Milani. Complexité du consensus anonyme en l'absence de concurrence. ALGOTEL 2016 - 18èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2016, Bayonne, France. ⟨hal-01304268v2⟩