论文标题
摊销恒定的圆形原子快照在消息通信系统中
Amortized Constant Round Atomic Snapshot in Message-Passing Systems
论文作者
论文摘要
我们研究了异步通讯系统中的晶格协议（LA）和原子快照问题，其中最多可能会崩溃。我们的主要结果是具有\ textit {摊销常量圆形复杂性}的耐崩溃的原子快照算法。据我们所知，最好的先前结果是Delporte等人给出的。 [TPDS，18]如果扫描多于更新，则使用摊销$ o（n）$复杂性。如果有$ω（\ sqrt {k}）$操作，我们的算法将实现摊销的持续回合，其中$ k $是执行中实际失败的数量，并且受$ f $的限制。此外，当没有故障时，我们的算法无条件地具有$ o（1）$圆形复杂性。为了实现摊销的恒定复杂性，我们设计了一个简单的\ textit {早期 - 停止}晶格协议算法，并使用它来“订购”我们快照对象的更新和扫描操作。我们的LA算法具有$ O（\ sqrt {k}）$圆形复杂性。这是异步系统中第一种早期的LA算法。
We study the lattice agreement (LA) and atomic snapshot problems in asynchronous message-passing systems where up to $f$ nodes may crash. Our main result is a crash-tolerant atomic snapshot algorithm with \textit{amortized constant round complexity}. To the best of our knowledge, the best prior result is given by Delporte et al. [TPDS, 18] with amortized $O(n)$ complexity if there are more scans than updates. Our algorithm achieves amortized constant round if there are $Ω(\sqrt{k})$ operations, where $k$ is the number of actual failures in an execution and is bounded by $f$. Moreover, when there is no failure, our algorithm has $O(1)$ round complexity unconditionally. To achieve amortized constant round complexity, we devise a simple \textit{early-stopping} lattice agreement algorithm and use it to "order" the update and scan operations for our snapshot object. Our LA algorithm has $O(\sqrt{k})$ round complexity. It is the first early-stopping LA algorithm in asynchronous systems.
