论文标题
从SWSR寄存器中实现SWMR寄存器中的SWSR寄存器
On implementing SWMR registers from SWSR registers in systems with Byzantine failures
论文作者
论文摘要
在分布式计算理论中，（潜在的）较弱寄存器的寄存器实现是一个经典问题。自从Lamport的开创性工作[13]以来，此问题已在异步过程中进行了广泛研究。在本文中，我们在拜占庭过程失败的背景下调查了这个问题，有或没有过程签名。 我们首先证明，如果没有签名，就无法从Atomic 1-Writer 1-Reader寄存器中1撰写的N-Reader寄存器的无线化实现。实际上，我们表现出更强的结果，即，即使在作者只能崩溃的假设下，最多有一个读者可能是恶意的，也没有可线化的实现Atomic 1-writer（n-1）读取器（N-1）阅读器 - 可确保每个正确过程最终完成其操作最终都能完成其操作的1次读取器n-Reader寄存器。鉴于这种不可能的结果，我们从Atomic 1-writer 1-Reader寄存器中提供了两个在不同假设下工作的实现。第一个实现是可线化的（在过程失败的任何组合下），但是它可以保证每个正确的过程最终仅在作者是正确或没有读者的假设下完成其操作，因此与不可能的结果相匹配。第二个实现假定过程签名；在任何过程失败的组合中，它都是无限的等待和线性化的。最后，我们表明，如果没有过程签名，即使我们假设作者是正确的，并且最多有一个读者可能是恶意的，也无法确保每个正确的读者都以有界数的步骤来完成每个读取操作。
The implementation of registers from (potentially) weaker registers is a classical problem in the theory of distributed computing. Since Lamport's pioneering work [13], this problem has been extensively studied in the context of asynchronous processes with crash failures. In this paper, we investigate this problem in the context of Byzantine process failures, with and without process signatures. We first prove that, without signatures, there is no wait-free linearizable implementation of a 1-writer n-reader register from atomic 1-writer 1-reader registers. In fact, we show a stronger result, namely, even under the assumption that the writer can only crash and at most one reader can be malicious, there is no linearizable implementation of a 1-writer n-reader register from atomic 1-writer (n-1)-reader registers that ensures that every correct process eventually completes its operations. In light of this impossibility result, we give two implementations of a 1-writer n-reader register from atomic 1-writer 1-reader registers that work under different assumptions. The first implementation is linearizable (under any combination of process failures), but it guarantees that every correct process eventually completes its operations only under the assumption that the writer is correct or no reader is malicious -- thus matching the impossibility result. The second implementation assumes process signatures; it is bounded wait-free and linearizable under any combination of process failures. Finally, we show that without process signatures, even if we assume that the writer is correct and at most one of the readers can be malicious, it is impossible to guarantee that every correct reader completes each read operation in a bounded number of steps.
