Improving the Hu-Toueg Construction of a Byzantine Linearizable SWMR Register
摘要
Recently, Hu and Toueg gave an implementation of the SWMR register from SWSR registers in shared memory distributed systems. While their definition of register linearizability is consistent with the definition of Byzantine linearizability of a concurrent history of Cohen and Keidar, it has several drawbacks. A stronger definition of a Byzantine linearizable register that overcomes these drawbacks has been proposed. In this paper, we give a construction of a Byzantine linearizable SWMR atomic register from SWSR registers that meets the stronger definition. The construction is correct when \(n>3f\) , where n is the number of readers, f is the maximum number of Byzantine readers, and the writer can also be Byzantine. The construction relies on a public-key infrastructure.