Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
This paper addresses the problem of designing an efficient implementation of a basic atomic read-write data structure over an asynchronous message-passing system. In particular, we consider time-efficient implementations of this abstraction in the case of a single writer, multiple readers (also called a SWMR atomic register) and S servers: the writer, the readers, and t out of the S servers may fail by crashing. Previous implementations tolerate the failure of any minority of servers (i.e., t < S/2) and require one communication round-trip for every write, and two round-trips for every read.We investigate the possibility of fast implementations, namely, implementations that complete both reads and writes in one round-trip. We show that, interestingly, the existence of a fast implementation depends on the maximum number of readers considered. More precisely, we show that a fast implementation is possible if and only if the number of readers is less that S/(t-2). We also show that a fast implementation is impossible in a multiple writers setting when t ≥ 1.Our results draw sharp lines between the time-complexity of regular and atomic register implementations, as well as between single-writer and multi-writer implementations. The results lead also to revisit, in a message-passing context, the folklore theorem that "atomic reads must write".
, , ,
Mikhail Kapralov, Jakab Tardos, Navid Nouri, Aidasadat Mousavifar
Rachid Guerraoui, Mihail Igor Zablotchi