.png){kind=icon}
返回
Emulating a Shared Register in a System That Never Stops Changing
.png){kind=icon}
OA
AI
DOI：10.1109/TPDS.2018.2867479.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
Read / write register emulation
message passing systems
churn
crash resilience
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
5.2K
被引数:
1.1W
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容