Distributed Multi-writer Multi-reader Atomic Register with Optimistically Fast Read and Write
Distributed Multi-writer Multi-reader Atomic Register with Optimistically Fast Read and Write
复制标题
DOI：
10.1145/3558481.3591086
复制
发表时间：
2023-04
期刊：
影响因子：
--
通讯作者：
Lewis Tseng;Neo Zhou;Cole Dumas;Tigran Bantikyan;R. Palmieri
中科院分区：
文献类型：
--
作者：
Lewis Tseng;Neo Zhou;Cole Dumas;Tigran Bantikyan;R. Palmieri
分布式多写入器多读取器(MWMR)原子寄存器是实现广泛的分布式算法的重要原语。因此，改善其业绩可能会产生大规模的后果。自从ABD仿真在消息传递网络中的开创性工作以来，许多研究人员研究了各种条件下原子寄存器的快速实现。“快速”意味着，通过联系简单多数，可以在1个往返时间(RTT)内完成一次读或写。在这项工作中，我们探索了一种具有最佳弹性和“乐观快速”读写操作的原子寄存器。也就是说，如果没有并发写入，这两个操作都可以很快。本文的主要贡献有三：(I)提出了一种具有最佳弹性和乐观读写速度的MWMR原子寄存器的仿真GUS；(Ii)我们证明了当存在>；5个节点时，不可能模拟具有这两种属性的MWMR原子寄存器；(Iii)我们在EPaxos和Gryff框架中实现了GUS，并证明了在地理复制对象存储系统的各种工作负载下，GUS提供了比最先进的EPaxos、Gryff、Giza和Tempo等系统更低的尾延。
A distributed multi-writer multi-reader (MWMR) atomic register is an important primitive that enables a wide range of distributed algorithms. Hence, improving its performance can have large-scale consequences. Since the seminal work of ABD emulation in the message-passing networks, many researchers study fast implementations of atomic registers under various conditions. "Fast'' means that a read or a write can be completed with 1 round-trip time (RTT), by contacting a simple majority. In this work, we explore an atomic register with optimal resilience and ''optimistically fast'' read and write operations. That is, both operations can be fast if there is no concurrent write. This paper has three contributions: (i) We present Gus, the emulation of an MWMR atomic register with optimal resilience and optimistically fast reads and writes when there are up to 5 nodes; (ii) We show that when there are > 5 nodes, it is impossible to emulate an MWMR atomic register with both properties; and (iii) We implement Gus in the framework of EPaxos and Gryff, and show that Gus provides lower tail latency than state-of-the-art systems such as EPaxos, Gryff, Giza, and Tempo under various workloads in the context of geo-replicated object storage systems.