The Complexity of Robust Atomic Storage
The authors study the time-complexity of robust atomic read/write storage from fault-prone storage components in asynchronous message-passing systems. Robustness here means wait-free tolerating the largest possible number t of Byzantine storage component failures (optimal resilience) without relying on data authentication. They show that no Single-Writer Multiple-Reader (SWMR) robust atomic storage implementation exists if read operations complete in less than four communication round-trips (rounds), and the time-complexity of write operations is constant. More precisely, they present two lower bounds. The first is a read lower bound stating that three rounds of communication are necessary to read from a SWMR robust atomic storage.