Author name cluster

Jennifer L. Welch

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

I&C Journal 2022 Journal Article

Store-collect in the presence of continuous churn with application to snapshots and lattice agreement

Hagit Attiya
Sweta Kumari
Archit Somani
Jennifer L. Welch

We present an algorithm for implementing a store-collect object in an asynchronous crash-prone message-passing dynamic system, where nodes continually enter and leave. The algorithm is very simple and efficient, requiring just one round trip for a store operation and two for a collect. We then show the versatility of the store-collect object for implementing churn-tolerant versions of useful data structures, while shielding the user from the complications of the underlying churn. In particular, we present elegant and efficient implementations of atomic snapshot and generalized lattice agreement objects that use store-collect.

Details DOI

I&C Journal 2018 Journal Article

Improved time bounds for linearizable implementations of abstract data types

Jiaqi Wang
Edward Talmage
Hyunyoung Lee
Jennifer L. Welch

Linearizability is a well-known consistency condition for shared objects in concurrent systems. We focus on the problem of implementing linearizable objects of arbitrary data types in message-passing systems with bounded, but uncertain, message delay and bounded, but non-zero, clock skew. We present an algorithm that exploits axiomatic properties of different operations to reduce the running time of each operation below that obtainable with previously known algorithms. We also prove lower bounds on the time complexity of various kinds of operations, specified by the axioms they satisfy, resulting in reduced gaps in some cases and tight bounds in others.

Details DOI

TCS Journal 2013 Journal Article

Dynamic regular registers in systems with churn

Andreas Klappenecker
Hyunyoung Lee
Jennifer L. Welch

Distributed systems with churn, or dynamic distributed systems, allow the processes to join and leave the system at will. In this paper, we present a new consistency condition for shared read-write registers which is based on multi-writer regularity, but allows for the likelihood of the register to lose its state with some probability; we call this a dynamic regular register. We then describe an algorithm for implementing a dynamic regular register using copies of the register distributed among the processes. When a process joins the system, it attempts to obtain an up-to-date copy of the data from other processes. Copies of the register are updated by broadcasting information. To model the dynamicity of the register system with churn, we use a continuous-time birth-death process which is a special case of continuous-time Markov processes. Then, we analyze the probability and the time duration that the dynamic regular register system keeps its state, given the joining rate and the leaving rate of the processes.

Details DOI

I&C Journal 1992 Journal Article

Modular construction of a Byzantine agreement protocol with optimal message bit complexity

Brian A. Coan
Jennifer L. Welch

This paper presents a new Byzantine agreement protocol that tolerates t processor faults using 3t + 1 processors, t + o(t) rounds, O(t 2) total message bits, and O(t ɛ) maximum message size, for any ɛ > 0. The protocol is optimal or near optimal in all cost measures: the number of processors is optimal, the message bit complexity is optimal, the number of rounds exceeds the lower bound by o(t), and the maximum message size exceeds the lower bound by O(t ɛ). The round complexity is uniformly better than 2·(t + 1) and thus is reasonable even for small t. This is the first Byzantine agreement protocol to have optimal message bit complexity. The new protocol is constructed by recursively applying a simple, yet general, transformation that changes the number of rounds, total message bits, and maximum message size required by a Byzantine agreement protocol, but preserves correctness, number of processor faults tolerated, and total number of processors. Each application of this new transformation reduces the number of message bits sent—at the expense of adding rounds of communication. Surprisingly, the base case of the recursive construction is the agreement protocol of Lamport, Shostak, and Pease, which has a number of message bits exponential in t.

Details DOI