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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Improving the Hu-Toueg Construction of a Byzantine Linearizable SWMR Register

  • Ajay D. Kshemkalyani,
  • Manaswini Piduguralla,
  • Sathya Peri,
  • Anshuman Misra

摘要

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.