Search Results

Documents authored by Welch, Jennifer

Found 2 Possible Name Variants:

Welch, Jennifer L.

Document
DOI: 10.4230/LIPIcs.OPODIS.2023.6
Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit

Authors: Hagit Attiya and Jennifer L. Welch

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 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 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. The contributions of the paper are first, a deeper insight into the connections between primitives commonly used to solve the fundamental problem of fault-tolerant consensus, and second, implementations of these primitives that can contribute to improved consensus algorithms.
Cite as

Hagit Attiya and Jennifer L. Welch. Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.OPODIS.2023.6,
  author =	{Attiya, Hagit and Welch, Jennifer L.},
  title =	{{Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{6:1--6:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.6},
  URN =		{urn:nbn:de:0030-drops-194967},
  doi =		{10.4230/LIPIcs.OPODIS.2023.6},
  annote =	{Keywords: graded broadcast, gradecast, binding, approximate agreement}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2023.32
Bounds on Worst-Case Responsiveness for Agreement Algorithms

Authors: Hagit Attiya and Jennifer L. Welch

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
We study the worst-case time complexity of solving two agreement problems, consensus and broadcast, in systems with n processes subject to no more than t process failures. In both problems, correct processes must decide on a common value; in the consensus problem, each process has an input and if the inputs of correct processes are all the same, then that must be the common decision, whereas in the broadcast problem, only one process (the sender) has an input and if the sender is correct, then its input must be the common decision. We focus on systems where there is an upper bound Δ on the message delivery time but it is expected that typically, messages arrive much faster, say within some time d. While Δ may or may not be known in advance, d is inherently unknown and specific to each execution. The goal is to design deterministic algorithms whose running times have minimal to no dependence on Δ, a property called responsiveness. We present a generic algorithm transformation that, when applied to appropriate eventually-synchronous consensus (or broadcast) algorithms, results in consensus (or broadcast) algorithms for send omission failures, authenticated Byzantine failures, and unauthenticated Byzantine failures whose running times have no dependence on Δ; their worst-case time complexities are all O(td), which is asymptotically optimal. The algorithm for send omission failures requires n > 2t, while those for Byzantine failures, both authenticated and unauthenticated, require n > 3t. The failure-resilience of the unauthenticated Byzantine algorithm is optimal. For authenticated Byzantine failures, existing agreement algorithms provide worst-case time complexity O(t Δ) when n is at most 3t. (When n ≤ 2t, broadcast is solvable while consensus is not.) We prove a lower bound on the worst-case time complexity of ⌊(3t-n)/2⌋ d + Δ when n is at most 3t. Although lower bounds of Δ and (t+1)d were already known, our new lower bound indicates that, at least when n ≤ 2t, it is impossible for an algorithm to pay these bounds in parallel.
Cite as

Hagit Attiya and Jennifer L. Welch. Bounds on Worst-Case Responsiveness for Agreement Algorithms. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 32:1-32:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.OPODIS.2023.32,
  author =	{Attiya, Hagit and Welch, Jennifer L.},
  title =	{{Bounds on Worst-Case Responsiveness for Agreement Algorithms}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{32:1--32:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.32},
  URN =		{urn:nbn:de:0030-drops-195229},
  doi =		{10.4230/LIPIcs.OPODIS.2023.32},
  annote =	{Keywords: bounded-delay model, basic round model, omission failures, Byzantine failures}
}
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
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.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
Keynote
DOI: 10.4230/LIPIcs.OPODIS.2018.1
Complexity of Multi-Valued Register Simulations: A Retrospective (Keynote)

Authors: Jennifer L. Welch

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
I will provide a historical perspective on wait-free simulations of multi-bit shared registers using single-bit shared registers, starting with classical results from the last century and ending with an overview of the recent resurgence of interest in the topic. Particular emphasis will be placed on the space and step complexities of such simulations.
Cite as

Jennifer L. Welch. Complexity of Multi-Valued Register Simulations: A Retrospective (Keynote). In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{welch:LIPIcs.OPODIS.2018.1,
  author =	{Welch, Jennifer L.},
  title =	{{Complexity of Multi-Valued Register Simulations: A Retrospective}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.1},
  URN =		{urn:nbn:de:0030-drops-100611},
  doi =		{10.4230/LIPIcs.OPODIS.2018.1},
  annote =	{Keywords: Distributed Systems}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2018.47
Brief Announcement: A Tight Lower Bound for Clock Synchronization in Odd-Ary M-Toroids

Authors: Reginald Frank and Jennifer L. Welch

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
In this paper we show a tight closed-form expression for the optimal clock synchronization in k-ary m-cubes with wraparound, where k is odd. This is done by proving a lower bound of 1/4um (k-1/k), where k is the (odd) number of processes in each of the m dimensions, and u is the uncertainty in delay on every link. Our lower bound matches the previously known upper bound.
Cite as

Reginald Frank and Jennifer L. Welch. Brief Announcement: A Tight Lower Bound for Clock Synchronization in Odd-Ary M-Toroids. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 47:1-47:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{frank_et_al:LIPIcs.DISC.2018.47,
  author =	{Frank, Reginald and Welch, Jennifer L.},
  title =	{{Brief Announcement: A Tight Lower Bound for Clock Synchronization in Odd-Ary M-Toroids}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{47:1--47:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.47},
  URN =		{urn:nbn:de:0030-drops-98360},
  doi =		{10.4230/LIPIcs.DISC.2018.47},
  annote =	{Keywords: Clock synchronization, Lower bound, k-ary m-toroid}
}

Welch, Jennifer

Document
DOI: 10.4230/LIPIcs.OPODIS.2015.32
Generic Proofs of Consensus Numbers for Abstract Data Types

Authors: Edward Talmage and Jennifer Welch

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
The power of shared data types to solve consensus in asynchronous wait-free systems is a fundamental question in distributed computing, but is largely considered only for specific data types. We consider general classes of abstract shared data types, and classify types of operations on those data types by the knowledge about past operations that processes can extract from the state of the shared object. We prove upper and lower bounds on the number of processes which can use data types in these classes to solve consensus. Our results generalize the consensus numbers known for a wide variety of specific shared data types, such as compare-and-swap, augmented queues and stacks, registers, and cyclic queues. Further, since the classification is based directly on the semantics of operations, one can use the bounds we present to determine the consensus number of a new data type from its specification. We show that, using sets of operations which can detect the first change to the shared object state, or even one at a fixed distance from the beginning of the execution, any number of processes can solve consensus. However, if instead of one of the first changes, operations can only detect one of the most recent changes, then fewer processes can solve consensus. In general, if each operation can either change shared state or read it, but not both, then the number of processes which can solve consensus is limited by the number of consecutive recent operations which can be viewed by a single operation. Allowing operations that both change and read the shared state can allow consensus algorithms with more processes, but if the operations can only see one change a fixed number of operations in the past, we upper bound the number of processes which can solve consensus with a small constant.
Cite as

Edward Talmage and Jennifer Welch. Generic Proofs of Consensus Numbers for Abstract Data Types. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{talmage_et_al:LIPIcs.OPODIS.2015.32,
  author =	{Talmage, Edward and Welch, Jennifer},
  title =	{{Generic Proofs of Consensus Numbers for Abstract Data Types}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{32:1--32:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.32},
  URN =		{urn:nbn:de:0030-drops-66217},
  doi =		{10.4230/LIPIcs.OPODIS.2015.32},
  annote =	{Keywords: Distributed Data Structures, Abstract Data Types, Consensus Numbers, Distributed Computing, Crash Failures}
}
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 About DROPS Imprint Privacy Contact