Ê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 studies the time complexity of reading unauthenticated data from a distributed storage made of a set of failure-prone base objects. More specifically, we consider the abstraction of a robust read/write storage that provides wait-free access to unauthenticated data over a set of base storage objects with possible failures, out of which at most are arbitrary and the rest are simple crash failures. We prove a communication round-trip lower bound for reading from a {\em safe} storage that uses at most base objects, independently of the number or round-trips needed by the writer. We then prove the lower bound tight by exhibiting a {\em regular} storage that uses base objects (optimal resilience) and features communication round-trips for both read and write operations.
Touradj Ebrahimi, Michela Testolina
Serge Vaudenay, Fatma Betül Durak
Mikhail Kapralov, Jakab Tardos, Navid Nouri, Aidasadat Mousavifar