Emulating a Shared Register in a System That Never Stops Changing uri icon

abstract

  • 1990-2012 IEEE. Emulating a shared register can mask the intricacies of designing algorithms for asynchronous message-passing systems subject to crash failures, since it allows them to run algorithms designed for the simpler shared-memory model. Typically such emulations replicate the value of the register in multiple servers and require readers and writers to communicate with a majority of servers. The success of this approach for static systems, where the set of nodes (readers, writers, and servers) is fixed, has motivated several similar emulations for dynamic systems, where nodes may enter and leave. However, existing emulations need to assume that the system eventually stops changing for a long enough period or that the system size is bounded. This paper presents the first emulation of a register supporting any number of readers and writers in a crash-prone system that can withstand nodes continually entering and leaving and imposes no upper bound on the system size. The algorithm works as long as the number of nodes entering and leaving during a fixed time interval is at most a constant fraction of the system size at the beginning of the interval, and as long as the number of crashed nodes in the system is at most a constant fraction of the current system size. The paper includes a lower bound on the fraction of correct nodes that is strictly larger than the fraction sufficient to solve the problem in the static case.

published proceedings

  • IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS

author list (cited authors)

  • Attiya, H., Chung, H. C., Ellen, F., Kumar, S., & Welch, J. L.

citation count

  • 5

complete list of authors

  • Attiya, Hagit||Chung, Hyun Chul||Ellen, Faith||Kumar, Saptaparni||Welch, Jennifer L

publication date

  • March 2019