2 Search Results for "Lamport, Leslie"


Document
On Implementing SWMR Registers from SWSR Registers in Systems with Byzantine Failures

Authors: Xing Hu and Sam Toueg

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)


Abstract
The implementation of registers from (potentially) weaker registers is a classical problem in the theory of distributed computing. Since Lamport’s pioneering work [Leslie Lamport, 1986], 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. In particular, we first show a strong impossibility result, namely, that there is no wait-free linearizable implementation of a 1-writer n-reader register from atomic 1-writer (n-1)-reader registers. In fact, this impossibility result holds even if all the processes except the writer are given atomic 1-writer n-reader registers, and even if we assume that the writer can only crash and at most one reader is subject to Byzantine failures. In light of this impossibility result, we give two register implementations. The first one implements a 1-writer n-reader register from atomic 1-writer 1-reader registers. This implementation is linearizable (under any combination of Byzantine process failures), but it is wait-free only under the assumption that the writer is correct or no reader is Byzantine - thus matching the impossibility result. The second implementation assumes process signatures; it is wait-free and linearizable under any number and combination of Byzantine process failures.

Cite as

Xing Hu and Sam Toueg. On Implementing SWMR Registers from SWSR Registers in Systems with Byzantine Failures. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 36:1-36:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{hu_et_al:LIPIcs.DISC.2022.36,
  author =	{Hu, Xing and Toueg, Sam},
  title =	{{On Implementing SWMR Registers from SWSR Registers in Systems with Byzantine Failures}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{36:1--36:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.36},
  URN =		{urn:nbn:de:0030-drops-172272},
  doi =		{10.4230/LIPIcs.DISC.2022.36},
  annote =	{Keywords: distributed computing, concurrency, linearizability, shared registers}
}
Document
Specification Problem (Dagstuhl Seminar 9439)

Authors: Manfred Broy and Leslie Lamport

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

Manfred Broy and Leslie Lamport. Specification Problem (Dagstuhl Seminar 9439). Dagstuhl Seminar Report 98, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1994)


Copy BibTex To Clipboard

@TechReport{broy_et_al:DagSemRep.98,
  author =	{Broy, Manfred and Lamport, Leslie},
  title =	{{Specification Problem (Dagstuhl Seminar 9439)}},
  pages =	{1--18},
  ISSN =	{1619-0203},
  year =	{1994},
  type = 	{Dagstuhl Seminar Report},
  number =	{98},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.98},
  URN =		{urn:nbn:de:0030-drops-149861},
  doi =		{10.4230/DagSemRep.98},
}
  • Refine by Author
  • 1 Broy, Manfred
  • 1 Hu, Xing
  • 1 Lamport, Leslie
  • 1 Toueg, Sam

  • Refine by Classification
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Distributed computing models

  • Refine by Keyword
  • 1 concurrency
  • 1 distributed computing
  • 1 linearizability
  • 1 shared registers

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 1994
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail