6 Search Results for "Hadzilacos, Vassos"

Document
DOI: 10.4230/LIPIcs.DISC.2022.36
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
DOI: 10.4230/LIPIcs.OPODIS.2020.16
Optimal Resilience in Systems That Mix Shared Memory and Message Passing

Authors: Hagit Attiya, Sweta Kumari, and Noa Schiller

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
We investigate the minimal number of failures that can partition a system where processes communicate both through shared memory and by message passing. We prove that this number precisely captures the resilience that can be achieved by algorithms that implement a variety of shared objects, like registers and atomic snapshots, and solve common tasks, like randomized consensus, approximate agreement and renaming. This has implications for the m&m-model of [Aguilera et al., 2018] and for the hybrid, cluster-based model of [Damien Imbs and Michel Raynal, 2013; Michel Raynal and Jiannong Cao, 2019].
Cite as

Hagit Attiya, Sweta Kumari, and Noa Schiller. Optimal Resilience in Systems That Mix Shared Memory and Message Passing. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.OPODIS.2020.16,
  author =	{Attiya, Hagit and Kumari, Sweta and Schiller, Noa},
  title =	{{Optimal Resilience in Systems That Mix Shared Memory and Message Passing}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{16:1--16:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.16},
  URN =		{urn:nbn:de:0030-drops-135019},
  doi =		{10.4230/LIPIcs.OPODIS.2020.16},
  annote =	{Keywords: fault resilience, m\&m model, cluster-based model, randomized consensus, approximate agreement, renaming, register implementations, atomic snapshots}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.16
On Deterministic Linearizable Set Agreement Objects

Authors: Felipe de Azevedo Piovezan, Vassos Hadzilacos, and Sam Toueg

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
A recent work showed that, for all n and k, there is a linearizable (n,k)-set agreement object O_L that is equivalent to the (n,k)-set agreement task [David Yu Cheng Chan et al., 2017]: given O_L, it is possible to solve the (n,k)-set agreement task, and given any algorithm that solves the (n,k)-set agreement task (and registers), it is possible to implement O_L. This linearizable object O_L, however, is not deterministic. It turns out that there is also a deterministic (n,k)-set agreement object O_D that is equivalent to the (n,k)-set agreement task, but this deterministic object O_D is not linearizable. This raises the question whether there exists a deterministic and linearizable (n,k)-set agreement object that is equivalent to the (n,k)-set agreement task. Here we show that in general the answer is no: specifically, we prove that for all n ≥ 4, every deterministic linearizable (n,2)-set agreement object is strictly stronger than the (n,2)-set agreement task. We prove this by showing that, for all n ≥ 4, every deterministic and linearizable (n,2)-set agreement object (together with registers) can be used to solve 2-consensus, whereas it is known that the (n,2)-set agreement task cannot do so. For a natural subset of (n,2)-set agreement objects, we prove that this result holds even for n = 3.
Cite as

Felipe de Azevedo Piovezan, Vassos Hadzilacos, and Sam Toueg. On Deterministic Linearizable Set Agreement Objects. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{deazevedopiovezan_et_al:LIPIcs.OPODIS.2019.16,
  author =	{de Azevedo Piovezan, Felipe and Hadzilacos, Vassos and Toueg, Sam},
  title =	{{On Deterministic Linearizable Set Agreement Objects}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.16},
  URN =		{urn:nbn:de:0030-drops-118026},
  doi =		{10.4230/LIPIcs.OPODIS.2019.16},
  annote =	{Keywords: Asynchronous shared-memory systems, consensus, set agreement, deterministic objects}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.28
Optimal Register Construction in M&M Systems

Authors: Vassos Hadzilacos, Xing Hu, and Sam Toueg

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
Motivated by recent distributed systems technology, Aguilera et al. introduced a hybrid model of distributed computing, called message-and-memory model or m&m model for short [Marcos K. Aguilera et al., 2018]. In this model, processes can communicate by message passing and also by accessing some shared memory. We consider the basic problem of implementing an atomic single-writer multi-reader (SWMR) register shared by all the processes in m&m systems. Specifically, we give an algorithm that implements such a register in m&m systems and show that it is optimal in the number of process crashes that it can tolerate. This generalizes the well-known implementation of an atomic SWMR register in a pure message-passing system [Attiya et al., 1995].
Cite as

Vassos Hadzilacos, Xing Hu, and Sam Toueg. Optimal Register Construction in M&M Systems. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hadzilacos_et_al:LIPIcs.OPODIS.2019.28,
  author =	{Hadzilacos, Vassos and Hu, Xing and Toueg, Sam},
  title =	{{Optimal Register Construction in M\&M Systems}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.28},
  URN =		{urn:nbn:de:0030-drops-118148},
  doi =		{10.4230/LIPIcs.OPODIS.2019.28},
  annote =	{Keywords: asynchronous distributed system, shared memory, message passing}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.12
On the Number of Objects with Distinct Power and the Linearizability of Set Agreement Objects

Authors: David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
We first prove that there are uncountably many objects with distinct computational powers. More precisely, we show that there is an uncountable set of objects such that for any two of them, at least one cannot be implemented from the other (and registers) in a wait-free manner. We then strengthen this result by showing that there are uncountably many linearizable objects with distinct computational powers. To do so, we prove that for all positive integers n and k, there is a linearizable object that is computationally equivalent to the k-set agreement task among n processes. To the best of our knowledge, these are the first linearizable objects proven to be computationally equivalent to set agreement tasks.
Cite as

David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg. On the Number of Objects with Distinct Power and the Linearizability of Set Agreement Objects. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.DISC.2017.12,
  author =	{Chan, David Yu Cheng and Hadzilacos, Vassos and Toueg, Sam},
  title =	{{On the Number of Objects with Distinct Power and the Linearizability of Set Agreement Objects}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.12},
  URN =		{urn:nbn:de:0030-drops-79973},
  doi =		{10.4230/LIPIcs.DISC.2017.12},
  annote =	{Keywords: Set Agreement, Asynchronous System, Shared Memory}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.5
Bounded Disagreement

Authors: David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
A well-known generalization of the consensus problem, namely, set agreement (SA), limits the number of distinct decision values that processes decide. In some settings, it may be more important to limit the number of "disagreers". Thus, we introduce another natural generalization of the consensus problem, namely, bounded disagreement (BD), which limits the number of processes that decide differently from the plurality. More precisely, in a system with n processes, the (n, l)-BD task has the following requirement: there is a value v such that at most l processes (the disagreers) decide a value other than v. Despite their apparent similarities, the results described below show that bounded disagreement, consensus, and set agreement are in fact fundamentally different problems. We investigate the relationship between bounded disagreement, consensus, and set agreement. In particular, we determine the consensus number for every instance of the BD task. We also determine values of n, l, m, and k such that the (n, l)-BD task can solve the (m, k)-SA task (where m processes can decide at most k distinct values). Using our results and a previously known impossibility result for set agreement, we prove that for all n >= 2, there is a BD task (and a corresponding BD object) that has consensus number n but can not be solved using n-consensus and registers. Prior to our paper, the only objects known to have this unusual characteristic for n >= 2 (which shows that the consensus number of an object is not sufficient to fully capture its power) were artificial objects crafted solely for the purpose of exhibiting this behaviour.
Cite as

David Yu Cheng Chan, Vassos Hadzilacos, and Sam Toueg. Bounded Disagreement. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{yuchengchan_et_al:LIPIcs.OPODIS.2016.5,
  author =	{Yu Cheng Chan, David and Hadzilacos, Vassos and Toueg, Sam},
  title =	{{Bounded Disagreement}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.5},
  URN =		{urn:nbn:de:0030-drops-70742},
  doi =		{10.4230/LIPIcs.OPODIS.2016.5},
  annote =	{Keywords: Consensus, Set Agreement, Asynchronous System, Distributed Algorithms, Shared Memory}
}
  • Refine by Author
  • 5 Toueg, Sam
  • 4 Hadzilacos, Vassos
  • 2 Hu, Xing
  • 1 Attiya, Hagit
  • 1 Chan, David Yu Cheng
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Distributed computing models
  • 2 Theory of computation → Concurrency
  • 2 Theory of computation → Parallel computing models
  • 1 Computing methodologies → Distributed algorithms
  • 1 Theory of computation → Concurrent algorithms
  • Show More...

  • Refine by Keyword
  • 2 Asynchronous System
  • 2 Set Agreement
  • 2 Shared Memory
  • 1 Asynchronous shared-memory systems
  • 1 Consensus
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2017
  • 2 2020
  • 1 2021
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact