77 Search Results for "Attiya, Hagit"

Volume

LIPIcs, Volume 179

34th International Symposium on Distributed Computing (DISC 2020)

DISC 2020, October 12-16, 2020, Virtual Conference

Editors: Hagit Attiya

Document
DOI: 10.4230/LIPIcs.DISC.2023.4
One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks

Authors: Hagit Attiya, Pierre Fraigniaud, Ami Paz, and Sergio Rajsbaum

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
The paper compares two generic techniques for deriving lower bounds and impossibility results in distributed computing. First, we prove a speedup theorem (a-la Brandt, 2019), for wait-free colorless algorithms, aiming at capturing the essence of the seminal round-reduction proof establishing a lower bound on the number of rounds for 3-coloring a cycle (Linial, 1992), and going by backward induction. Second, we consider FLP-style proofs, aiming at capturing the essence of the seminal consensus impossibility proof (Fischer, Lynch, and Paterson, 1985) and using forward induction. We show that despite their very different natures, these two forms of proof are tightly connected. In particular, we show that for every colorless task Π, if there is a round-reduction proof establishing the impossibility of solving Π using wait-free colorless algorithms, then there is an FLP-style proof establishing the same impossibility. For 1-dimensional colorless tasks (for an arbitrarily number n ≥ 2 of processes), we prove that the two proof techniques have exactly the same power, and more importantly, both are complete: if a 1-dimensional colorless task is not wait-free solvable by n ≥ 2 processes, then the impossibility can be proved by both proof techniques. Moreover, a round-reduction proof can be automatically derived, and an FLP-style proof can be automatically generated from it. Finally, we illustrate the use of these two techniques by establishing the impossibility of solving any colorless covering task of arbitrary dimension by wait-free algorithms.
Cite as

Hagit Attiya, Pierre Fraigniaud, Ami Paz, and Sergio Rajsbaum. One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 4:1-4:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.DISC.2023.4,
  author =	{Attiya, Hagit and Fraigniaud, Pierre and Paz, Ami and Rajsbaum, Sergio},
  title =	{{One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{4:1--4:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.4},
  URN =		{urn:nbn:de:0030-drops-191304},
  doi =		{10.4230/LIPIcs.DISC.2023.4},
  annote =	{Keywords: Wait-free computing, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.5
Topological Characterization of Task Solvability in General Models of Computation

Authors: Hagit Attiya, Armando Castañeda, and Thomas Nowak

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
The famous asynchronous computability theorem (ACT) relates the existence of an asynchronous wait-free shared memory protocol for solving a task with the existence of a simplicial map from a subdivision of the simplicial complex representing the inputs to the simplicial complex representing the allowable outputs. The original theorem relies on a correspondence between protocols and simplicial maps in round-structured models of computation that induce a compact topology. This correspondence, however, is far from obvious for computation models that induce a non-compact topology, and indeed previous attempts to extend the ACT have failed. This paper shows that in every non-compact model, protocols solving tasks correspond to simplicial maps that need to be continuous. It first proves a generalized ACT for sub-IIS models, some of which are non-compact, and applies it to the set agreement task. Then it proves that in general models too, protocols are simplicial maps that need to be continuous, hence showing that the topological approach is universal. Finally, it shows that the approach used in ACT that equates protocols and simplicial complexes actually works for every compact model. Our study combines, for the first time, combinatorial and point-set topological aspects of the executions admitted by the computation model.
Cite as

Hagit Attiya, Armando Castañeda, and Thomas Nowak. Topological Characterization of Task Solvability in General Models of Computation. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 5:1-5:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.DISC.2023.5,
  author =	{Attiya, Hagit and Casta\~{n}eda, Armando and Nowak, Thomas},
  title =	{{Topological Characterization of Task Solvability in General Models of Computation}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{5:1--5:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.5},
  URN =		{urn:nbn:de:0030-drops-191315},
  doi =		{10.4230/LIPIcs.DISC.2023.5},
  annote =	{Keywords: task solvability, combinatorial topology, point-set topology}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2023.36
Brief Announcement: Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit

Authors: Hagit Attiya and Jennifer L. Welch

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
Algorithms to solve fault-tolerant consensus in asynchronous systems often rely on primitives such as crusader agreement, adopt-commit, and graded broadcast, which provide weaker agreement properties than consensus. Although these primitives have a similar flavor, they have been defined and implemented separately in ad hoc ways. We propose a new problem called connected consensus that has as special cases crusader agreement, adopt-commit, and graded broadcast, and generalizes them to handle multi-valued (non-binary) inputs. The generalization is accomplished by relating the problem to approximate agreement on graphs. We present three algorithms for multi-valued connected consensus in asynchronous message-passing systems, one tolerating crash failures and two tolerating malicious (unauthenticated Byzantine) failures. We extend the definition of binding, a desirable property recently identified as supporting binary consensus algorithms that are correct against adaptive adversaries, to the multi-valued input case and show that all our algorithms satisfy the property. Our crash-resilient algorithm has failure-resilience and time complexity that we show are optimal. When restricted to the case of binary inputs, the algorithm has improved time complexity over prior algorithms. Our two algorithms for malicious failures trade off failure resilience and time complexity. The first algorithm has time complexity that we prove is optimal but worse failure-resilience, while the second has failure-resilience that we prove is optimal but worse time complexity. When restricted to the case of binary inputs, the time complexity (as well as resilience) of the second algorithm matches that of prior algorithms.
Cite as

Hagit Attiya and Jennifer L. Welch. Brief Announcement: Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 36:1-36:7, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.DISC.2023.36,
  author =	{Attiya, Hagit and Welch, Jennifer L.},
  title =	{{Brief Announcement: Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{36:1--36:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.36},
  URN =		{urn:nbn:de:0030-drops-191620},
  doi =		{10.4230/LIPIcs.DISC.2023.36},
  annote =	{Keywords: graded broadcast, gradecast, binding, approximate agreement}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2023.44
Brief Announcement: Recoverable and Detectable Self-Implementations of Swap

Authors: Tomer Lev Lehman, Hagit Attiya, and Danny Hendler

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
Recoverable algorithms tolerate failures and recoveries of processes by using non-volatile memory. Of particular interest are self-implementations of key operations, in which a recoverable operation is implemented from its non-recoverable counterpart (in addition to reads and writes). This paper presents two self-implementations of the SWAP operation. One works in the system-wide failures model, where all processes fail and recover together, and the other in the independent failures model, where each process crashes and recovers independently of the other processes. Both algorithms are wait-free in crash-free executions, but their recovery code is blocking. We prove that this is inherent for the independent failures model. The impossibility result is proved for implementations of distinguishable operations using interfering functions, and in particular, it applies to a recoverable self-implementation of swap.
Cite as

Tomer Lev Lehman, Hagit Attiya, and Danny Hendler. Brief Announcement: Recoverable and Detectable Self-Implementations of Swap. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 44:1-44:7, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{levlehman_et_al:LIPIcs.DISC.2023.44,
  author =	{Lev Lehman, Tomer and Attiya, Hagit and Hendler, Danny},
  title =	{{Brief Announcement: Recoverable and Detectable Self-Implementations of Swap}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{44:1--44:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.44},
  URN =		{urn:nbn:de:0030-drops-191704},
  doi =		{10.4230/LIPIcs.DISC.2023.44},
  annote =	{Keywords: Persistent memory, non-volatile memory, recoverable objects, detectablitly}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2023.27
Faithful Simulation of Randomized BFT Protocols on Block DAGs

Authors: Hagit Attiya, Constantin Enea, and Shafik Nassar

Published in: LIPIcs, Volume 279, 34th International Conference on Concurrency Theory (CONCUR 2023)

Abstract
Byzantine Fault-Tolerant (BFT) protocols that are based on Directed Acyclic Graphs (DAGs) are attractive due to their many advantages in asynchronous blockchain systems. These DAG-based protocols can be viewed as a simulation of some BFT protocol on a DAG. Many DAG-based BFT protocols rely on randomization, since they are used for agreement and ordering of transactions, which cannot be achieved deterministically in asynchronous systems. Randomization is achieved either through local sources of randomness, or by employing shared objects that provide a common source of randomness, e.g., common coins. A DAG simulation of a randomized protocol should be faithful, in the sense that it precisely preserves the properties of the original BFT protocol, and in particular, their probability distributions. We argue that faithfulness is ensured by a forward simulation. We show how to faithfully simulate any BFT protocol that uses public coins and shared objects, like common coins.
Cite as

Hagit Attiya, Constantin Enea, and Shafik Nassar. Faithful Simulation of Randomized BFT Protocols on Block DAGs. In 34th International Conference on Concurrency Theory (CONCUR 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 279, pp. 27:1-27:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.CONCUR.2023.27,
  author =	{Attiya, Hagit and Enea, Constantin and Nassar, Shafik},
  title =	{{Faithful Simulation of Randomized BFT Protocols on Block DAGs}},
  booktitle =	{34th International Conference on Concurrency Theory (CONCUR 2023)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-299-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{279},
  editor =	{P\'{e}rez, Guillermo A. and Raskin, Jean-Fran\c{c}ois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2023.27},
  URN =		{urn:nbn:de:0030-drops-190210},
  doi =		{10.4230/LIPIcs.CONCUR.2023.27},
  annote =	{Keywords: Byzantine failures, Hyperproperties, Forward Simulation}
}
Document
DOI: 10.4230/DagRep.12.12.27
Formal Methods and Distributed Computing: Stronger Together (Dagstuhl Seminar 22492)

Authors: Hagit Attiya, Constantin Enea, Sergio Rajsbaum, and Ana Sokolova

Published in: Dagstuhl Reports, Volume 12, Issue 12 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22492 "Formal Methods and Distributed Computing: Stronger Together", held in December 2022.
Cite as

Hagit Attiya, Constantin Enea, Sergio Rajsbaum, and Ana Sokolova. Formal Methods and Distributed Computing: Stronger Together (Dagstuhl Seminar 22492). In Dagstuhl Reports, Volume 12, Issue 12, pp. 27-53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{attiya_et_al:DagRep.12.12.27,
  author =	{Attiya, Hagit and Enea, Constantin and Rajsbaum, Sergio and Sokolova, Ana},
  title =	{{Formal Methods and Distributed Computing: Stronger Together (Dagstuhl Seminar 22492)}},
  pages =	{27--53},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{12},
  editor =	{Attiya, Hagit and Enea, Constantin and Rajsbaum, Sergio and Sokolova, Ana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.12.27},
  URN =		{urn:nbn:de:0030-drops-178452},
  doi =		{10.4230/DagRep.12.12.27},
  annote =	{Keywords: automated verification and reasoning, concurrent data structures and transactions, distributed algorithms, large-scale replication}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.6
The Step Complexity of Multidimensional Approximate Agreement

Authors: Hagit Attiya and Faith Ellen

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Approximate agreement allows a set of n processes to obtain outputs that are within a specified distance ε > 0 of one another and within the convex hull of the inputs. When the inputs are real numbers, there is a wait-free shared-memory approximate agreement algorithm [Moran, 1995] whose step complexity is in O(n log(S/ε)), where S, the spread of the inputs, is the maximal distance between inputs. There is another wait-free algorithm [Schenk, 1995] that avoids the dependence on n and achieves O(log(M/ε)) step complexity where M, the magnitude of the inputs, is the absolute value of the maximal input. This paper considers whether it is possible to obtain an approximate agreement algorithm whose step complexity depends on neither n nor the magnitude of the inputs, which can be much larger than their spread. On the negative side, we prove that Ω(min{(log M)/(log log M), (√log n)/(log log n)}) is a lower bound on the step complexity of approximate agreement, even when the inputs are real numbers. On the positive side, we prove that a polylogarithmic dependence on n and S/ε can be achieved, by presenting an approximate agreement algorithm with O(log n (log n + log(S/ε))) step complexity. Our algorithm works for multidimensional domains. The step complexity can be further restricted to be in O(min{log n (log n + log (S/ε)), log(M/ε)}) when the inputs are real numbers.
Cite as

Hagit Attiya and Faith Ellen. The Step Complexity of Multidimensional Approximate Agreement. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 6:1-6:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.OPODIS.2022.6,
  author =	{Attiya, Hagit and Ellen, Faith},
  title =	{{The Step Complexity of Multidimensional Approximate Agreement}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{6:1--6:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.6},
  URN =		{urn:nbn:de:0030-drops-176261},
  doi =		{10.4230/LIPIcs.OPODIS.2022.6},
  annote =	{Keywords: approximate agreement, conflict detection, shared memory, wait-freedom, step complexity}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.DISC.2022.3
Using Linearizable Objects in Randomized Concurrent Programs (Invited Talk)

Authors: Jennifer L. Welch

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

Abstract
Atomic shared objects, whose operations take place instantaneously, are a powerful technique for designing complex concurrent programs. Since they are not always available, they are typically substituted with software implementations. A prominent condition relating these implementations to their atomic specifications is linearizability, which preserves safety properties of programs using them. However linearizability does not preserve hyper-properties, which include probabilistic guarantees about randomized programs. A more restrictive property, strong linearizability, does preserve hyper-properties but it is impossible to achieve in many situations. In particular, we show that there are no strongly linearizable implementations of multi-writer registers or snapshot objects in message-passing systems. On the other hand, we show that a wide class of linearizable implementations, including well-known ones for registers and snapshots, can be modified to approximate the probabilistic guarantees of randomized programs when using atomic objects. This is joint work with Hagit Attiya and Constantin Enea.
Cite as

Jennifer L. Welch. Using Linearizable Objects in Randomized Concurrent Programs (Invited Talk). In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, p. 3:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{welch:LIPIcs.DISC.2022.3,
  author =	{Welch, Jennifer L.},
  title =	{{Using Linearizable Objects in Randomized Concurrent Programs}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{3:1--3:1},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.3},
  URN =		{urn:nbn:de:0030-drops-171946},
  doi =		{10.4230/LIPIcs.DISC.2022.3},
  annote =	{Keywords: Concurrent objects, strong linearizability, impossibility proofs, message-passing systems, randomized algorithms}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.12
Liveness and Latency of Byzantine State-Machine Replication

Authors: Manuel Bravo, Gregory Chockler, and Alexey Gotsman

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

Abstract
Byzantine state-machine replication (SMR) ensures the consistency of replicated state in the presence of malicious replicas and lies at the heart of the modern blockchain technology. Byzantine SMR protocols often guarantee safety under all circumstances and liveness only under synchrony. However, guaranteeing liveness even under this assumption is nontrivial. So far we have lacked systematic ways of incorporating liveness mechanisms into Byzantine SMR protocols, which often led to subtle bugs. To close this gap, we introduce a modular framework to facilitate the design of provably live and efficient Byzantine SMR protocols. Our framework relies on a view abstraction generated by a special SMR synchronizer primitive to drive the agreement on command ordering. We present a simple formal specification of an SMR synchronizer and its bounded-space implementation under partial synchrony. We also apply our specification to prove liveness and analyze the latency of three Byzantine SMR protocols via a uniform methodology. In particular, one of these results yields what we believe is the first rigorous liveness proof for the algorithmic core of the seminal PBFT protocol.
Cite as

Manuel Bravo, Gregory Chockler, and Alexey Gotsman. Liveness and Latency of Byzantine State-Machine Replication. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 12:1-12:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bravo_et_al:LIPIcs.DISC.2022.12,
  author =	{Bravo, Manuel and Chockler, Gregory and Gotsman, Alexey},
  title =	{{Liveness and Latency of Byzantine State-Machine Replication}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{12:1--12: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.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.12},
  URN =		{urn:nbn:de:0030-drops-172037},
  doi =		{10.4230/LIPIcs.DISC.2022.12},
  annote =	{Keywords: Replication, blockchain, partial synchrony, liveness}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.29
Recoverable and Detectable Fetch&Add

Authors: Liad Nahum, Hagit Attiya, Ohad Ben-Baruch, and Danny Hendler

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
The emergence of systems with non-volatile main memory (NVRAM) increases the need for persistent concurrent objects. Of specific interest are recoverable implementations that, in addition to being robust to crash-failures, are also detectable. Detectability ensures that upon recovery, it is possible to infer whether the failed operation took effect or not and, in the former case, obtain its response. This work presents two recoverable detectable Fetch&Add (FAA) algorithms that are self-implementations, i.e, use only a fetch&add base object, in addition to read/write registers. The algorithms target two different models for recovery: the global-crash model and the individual-crash model. In both algorithms, operations are wait-free when there are no crashes, but the recovery code may block if there are repeated failures. We also prove that in the individual-crash model, there is no implementation of recoverable and detectable FAA using only read, write and fetch&add primitives in which all operations, including recovery, are lock-free.
Cite as

Liad Nahum, Hagit Attiya, Ohad Ben-Baruch, and Danny Hendler. Recoverable and Detectable Fetch&Add. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 29:1-29:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{nahum_et_al:LIPIcs.OPODIS.2021.29,
  author =	{Nahum, Liad and Attiya, Hagit and Ben-Baruch, Ohad and Hendler, Danny},
  title =	{{Recoverable and Detectable Fetch\&Add}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.29},
  URN =		{urn:nbn:de:0030-drops-158043},
  doi =		{10.4230/LIPIcs.OPODIS.2021.29},
  annote =	{Keywords: Multi-core algorithms, persistent memory, non-volatile memory}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.7
Impossibility of Strongly-Linearizable Message-Passing Objects via Simulation by Single-Writer Registers

Authors: Hagit Attiya, Constantin Enea, and Jennifer L. Welch

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
A key way to construct complex distributed systems is through modular composition of linearizable concurrent objects. A prominent example is shared registers, which have crash-tolerant implementations on top of message-passing systems, allowing the advantages of shared memory to carry over to message-passing. Yet linearizable registers do not always behave properly when used inside randomized programs. A strengthening of linearizability, called strong linearizability, has been shown to preserve probabilistic behavior, as well as other "hypersafety" properties. In order to exploit composition and abstraction in message-passing systems, it is crucial to know whether there exist strongly-linearizable implementations of registers in message-passing. This paper answers the question in the negative: there are no strongly-linearizable fault-tolerant message-passing implementations of multi-writer registers, max-registers, snapshots or counters. This result is proved by reduction from the corresponding result by Helmi et al. The reduction is a novel extension of the BG simulation that connects shared-memory and message-passing, supports long-lived objects, and preserves strong linearizability. The main technical challenge arises from the discrepancy between the potentially minuscule fraction of failures to be tolerated in the simulated message-passing algorithm and the large fraction of failures that can afflict the simulating shared-memory system. The reduction is general and can be viewed as the inverse of the ABD simulation of shared memory in message-passing.
Cite as

Hagit Attiya, Constantin Enea, and Jennifer L. Welch. Impossibility of Strongly-Linearizable Message-Passing Objects via Simulation by Single-Writer Registers. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 7:1-7:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.DISC.2021.7,
  author =	{Attiya, Hagit and Enea, Constantin and Welch, Jennifer L.},
  title =	{{Impossibility of Strongly-Linearizable Message-Passing Objects via Simulation by Single-Writer Registers}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.7},
  URN =		{urn:nbn:de:0030-drops-148096},
  doi =		{10.4230/LIPIcs.DISC.2021.7},
  annote =	{Keywords: Concurrent Objects, Message-passing systems, Strong linearizability, Impossibility proofs, BG simulation, 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.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.2020.18
Locally Solvable Tasks and the Limitations of Valency Arguments

Authors: Hagit Attiya, Armando Castañeda, and Sergio Rajsbaum

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

Abstract
An elegant strategy for proving impossibility results in distributed computing was introduced in the celebrated FLP consensus impossibility proof. This strategy is local in nature as at each stage, one configuration of a hypothetical protocol for consensus is considered, together with future valencies of possible extensions. This proof strategy has been used in numerous situations related to consensus, leading one to wonder why it has not been used in impossibility results of two other well-known tasks: set agreement and renaming. This paper provides an explanation of why impossibility proofs of these tasks have been of a global nature. It shows that a protocol can always solve such tasks locally, in the following sense. Given a configuration and all its future valencies, if a single successor configuration is selected, then the protocol can reveal all decisions in this branch of executions, satisfying the task specification. This result is shown for both set agreement and renaming, implying that there are no local impossibility proofs for these tasks.
Cite as

Hagit Attiya, Armando Castañeda, and Sergio Rajsbaum. Locally Solvable Tasks and the Limitations of Valency Arguments. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 18:1-18:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.OPODIS.2020.18,
  author =	{Attiya, Hagit and Casta\~{n}eda, Armando and Rajsbaum, Sergio},
  title =	{{Locally Solvable Tasks and the Limitations of Valency Arguments}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{18:1--18: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.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.18},
  URN =		{urn:nbn:de:0030-drops-135037},
  doi =		{10.4230/LIPIcs.OPODIS.2020.18},
  annote =	{Keywords: Wait-freedom, Set agreement, Weak symmetry breaking, Impossibility proofs}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.28
Fast Deterministic Algorithms for Highly-Dynamic Networks

Authors: Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz, and Gregory Schwartzman

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

Abstract
This paper provides an algorithmic framework for obtaining fast distributed algorithms for a highly-dynamic setting, in which arbitrarily many edge changes may occur in each round. Our algorithm significantly improves upon prior work in its combination of (1) having an O(1) amortized time complexity, (2) using only O(log{n})-bit messages, (3) not posing any restrictions on the dynamic behavior of the environment, (4) being deterministic, (5) having strong guarantees for intermediate solutions, and (6) being applicable for a wide family of tasks. The tasks for which we deduce such an algorithm are maximal matching, (degree+1)-coloring, 2-approximation for minimum weight vertex cover, and maximal independent set (which is the most subtle case). For some of these tasks, node insertions can also be among the allowed topology changes, and for some of them also abrupt node deletions.
Cite as

Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz, and Gregory Schwartzman. Fast Deterministic Algorithms for Highly-Dynamic Networks. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 28:1-28:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.OPODIS.2020.28,
  author =	{Censor-Hillel, Keren and Dafni, Neta and Kolobov, Victor I. and Paz, Ami and Schwartzman, Gregory},
  title =	{{Fast Deterministic Algorithms for Highly-Dynamic Networks}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{28:1--28: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.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.28},
  URN =		{urn:nbn:de:0030-drops-135138},
  doi =		{10.4230/LIPIcs.OPODIS.2020.28},
  annote =	{Keywords: dynamic distributed algorithms}
}
  • Refine by Author
  • 19 Attiya, Hagit
  • 5 Paz, Ami
  • 4 Enea, Constantin
  • 3 Brandt, Sebastian
  • 3 Gotsman, Alexey
  • Show More...

  • Refine by Classification
  • 30 Theory of computation → Distributed algorithms
  • 14 Theory of computation → Distributed computing models
  • 8 Computing methodologies → Distributed algorithms
  • 6 Networks → Network algorithms
  • 5 Computing methodologies → Concurrent algorithms
  • Show More...

  • Refine by Keyword
  • 3 Consensus
  • 3 LOCAL model
  • 3 approximate agreement
  • 2 Approximation algorithms
  • 2 Byzantine agreement
  • Show More...

  • Refine by Type
  • 76 document
  • 1 volume

  • Refine by Publication Year
  • 57 2020
  • 7 2023
  • 4 2021
  • 3 2022
  • 2 2016
  • Show More...

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact