Skip to Main content Skip to Navigation
Conference papers

Complexité du consensus anonyme en l'absence de concurrence

Résumé : 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.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01304268
Contributor : Claire Capdevielle <>
Submitted on : Thursday, April 28, 2016 - 11:57:27 AM
Last modification on : Friday, April 9, 2021 - 4:28:05 PM
Long-term archiving on: : Tuesday, November 15, 2016 - 4:04:31 PM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01304268, version 2

Citation

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⟩

Share

Metrics

Record views

293

Files downloads

87