论文标题
对分布式多作者原子寄存器的快速实施的细粒度分析
Fine-grained Analysis on Fast Implementations of Distributed Multi-writer Atomic Registers
论文作者
论文摘要
分布式的多作者原子寄存器是大量分布式算法的核心。研究人员在享受原子能的好处时，进一步探索了在数据访问潜伏期方面最佳的原子雷格斯的快速实施。尽管事实证明，当读取和写入要快速时，多撰写的原子寄存器实现是不可能的，但是当仅需要写或读取即可快速时，是否不可能实现。这项工作证明了基于不可分割的执行中的一系列链参数的快速写入实现的可能性。我们还通过在单作者案例中扩展结果来显示快速读取实现的必要条件。这项工作总结了一系列关于分布式原子寄存器快速实施的研究。
Distributed multi-writer atomic registers are at the heart of a large number of distributed algorithms. While enjoying the benefits of atomicity, researchers further explore fast implementations of atomic reigsters which are optimal in terms of data access latency. Though it is proved that multi-writer atomic register implementations are impossible when both read and write are required to be fast, it is still open whether implementations are impossible when only write or read is required to be fast. This work proves the impossibility of fast write implementations based on a series of chain arguments among indistiguishable executions. We also show the necessary and sufficient condition for fast read implementations by extending the results in the single-writer case. This work concludes a series of studies on fast implementations of distributed atomic registers.
