Gadi Taubenfeld

TCS Journal 2023 Journal Article

Reaching agreement in the presence of contention-related crash failures

• Anaïs Durand
• Michel Raynal
• Gadi Taubenfeld

While consensus (and more generally agreement problems) is at the heart of many coordination problems in asynchronous distributed systems prone to process crashes, it has been shown to be impossible to solve in such systems where processes communicate by message-passing or by reading and writing a shared memory. Hence, these systems must be enriched with additional computational power for consensus to be solved on top of them. This article presents a new restriction of the classical basic computational model that combines process participation and a constraint on failure occurrences that can happen only while a predefined contention threshold has not yet been bypassed. This type of failure is called λ-constrained crashes, where λ defines the considered contention threshold. It appears that when assuming such contention-related crash failures and enriching the system with objects whose consensus number is x ≥ 1, consensus for n processes can be solved for any n ≥ x assuming up to x failures. The article proceeds incrementally. It first presents an algorithm that solves consensus on top of read/write registers if at most one crash occurs before the contention threshold λ = n − 1 has been bypassed. Then, the article considers two extensions. The first one assumes that the system is enriched with objects whose consensus number is x ≥ 1, and shows that when λ = n − x, consensus can be solved despite up to x λ-constrained crashes, for any n ≥ x, and when λ = n − 2 x + 1, consensus can be solved despite up to 2 x − 1 λ-constrained crashes, assuming x divides n. The second extension prolongs the previous results to the k-set agreement problem (which is a natural generalization of consensus). Impossibility results are also presented for the number of λ-constrained failures that can be tolerated.

TCS Journal 2022 Journal Article

A visit to mutual exclusion in seven dates

• Michel Raynal
• Gadi Taubenfeld

Mutual exclusion (mutex) is one of the most fundamental synchronization problems encountered in shared memory systems. It appears in all computer science first-degree curricula. This article presents nine mutex algorithms, each with its noteworthy features, spread over seven dates covering 1965-2020. Most of these algorithms are very well known and paved the way for new research directions. This article aims to present fundamental issues and basic principles that underlie the design of shared memory mutex algorithms in different contexts. So, differently from exhaustive surveys on shared memory mutex algorithms, it strives to give the reader a flavor of the many design facets of this still challenging problem.

TCS Journal 2022 Journal Article

Contention-related crash failures: Definitions, agreement algorithms, and impossibility results

• Anaïs Durand
• Michel Raynal
• Gadi Taubenfeld

This article explores an interplay between process crash failures and concurrency. Namely, it aims at answering the question, “Is it possible to cope with more crash failures when some number of crashes occur before some predefined contention point happened? ”. These crashes are named λ-constrained crashes, where λ is the predefined contention point (known by the processes). Hence, this article considers two types of process crashes: λ-constrained crashes and classical crashes (which can occur at any time and are consequently called any-time crashes). Considering a system made up of n asynchronous processes communicating through atomic read/write registers, the article focuses on the design of two agreement-related algorithms. Assuming λ = n − 1 and no any-time failure, the first algorithm solves the consensus problem in the presence of one λ-constrained crash failure, thereby circumventing the well-known FLP impossibility result. The second algorithm considers k-set agreement for k ≥ 2. It is a k-set agreement algorithm such that λ = n − ℓ and ℓ ≥ k = m + f that works in the presence of up to ( 2 m + ℓ − k ) λ-constrained crashes and ( f − 1 ) any-time crashes, i. e. , up to t = ( 2 m + ℓ − k ) + ( f − 1 ) process crashes. It follows that considering the timing of failures with respect to a predefined contention point enlarges the space of executions in which k-set agreement can be solved despite the combined effect of asynchrony, concurrency, and process crashes. The paper also presents agreement-related impossibility results for consensus and k-set agreement in the context of λ-constrained process crashes (with or without any-time crashes).

TCS Journal 2020 Journal Article

Leader-based de-anonymization of an anonymous read/write memory

• Emmanuel Godard
• Damien Imbs
• Michel Raynal
• Gadi Taubenfeld

A new notion of anonymity was recently introduced at PODC 2017, namely, anonymity on the names of the registers that define the shared memory. As an example, a shared register named A by a process p and a shared register named B by another process q may correspond to the very same shared register X, while the same name C may correspond to different shared registers for p and q. Considering an asynchronous n-process anonymous shared memory system, this paper is concerned with the de-anonymization of the memory, i. e. , at the end of the execution of a de-anonymization algorithm, the processes must agree on the same name for each shared register, and different shared registers must have different names. To this end, the paper first addresses leader election in an anonymous memory system. Let n be the number of processes and m the size of the anonymous memory (total number of anonymous registers). It is first shown that there is no election algorithm when the number of anonymous registers is a multiple of n. Then, assuming m = α n + β, where α is a positive integer, three election algorithms are presented, which consider the cases β = 1, β = n − 1, and β ∈ M ( n ), where the set M ( n ) characterizes the values for which mutual exclusion can be solved despite memory anonymity. Once election is solved, a general (and simple) de-anonymization algorithm is presented, which takes as a subroutine any memory anonymous leader election algorithm. Hence, any instance of this algorithm works for the values of m required by the selected underlying election algorithm. As the underlying election algorithms, the de-anonymization algorithm is symmetric in the sense that process identities can only be compared for equality.

TCS Journal 2017 Journal Article

Contention-sensitive data structures and algorithms

• Gadi Taubenfeld

A contention-sensitive data structure is a concurrent data structure in which the overhead introduced by locking is eliminated in common cases, when there is no contention, or when processes with non-interfering operations access it concurrently. When a process invokes an operation on a contention-sensitive data structure, in the absence of contention or interference, the process must be able to complete its operation in a small number of steps and without using locks. Using locks is permitted only when there is interference. We formally define the notion of contention-sensitive data structures, propose four general transformations that facilitate devising such data structures, and illustrate the benefits of the approach by implementing a contention-sensitive consensus algorithm, a contention-sensitive double-ended queue data structure, and a contention-sensitive election algorithm.

I&C Journal 2013 Journal Article

Computing with infinitely many processes

• Michael Merritt
• Gadi Taubenfeld

We explore four classic problems in concurrent computing (election, mutual exclusion, consensus, and naming) when the number of processes which may participate is unbounded. Partial information about the number of processes actually participating and the concurrency level is shown to affect the computability and complexity of solving these problems when using only atomic registers. We survey and generalize work carried out in models with known bounds on the number of processes, and prove several new results. These include improved bounds for election when participation is required and a new adaptive starvation-free mutual exclusion algorithm for unbounded concurrency. We also survey results in models with shared objects stronger than atomic registers, such as test&set bits, semaphores or read–modify–write registers, and update them for the unbounded case.

TCS Journal 2002 Journal Article

Public data structures: counters as a special case

• Hagit Brit
• Shlomo Moran
• Gadi Taubenfeld

A public data structure is required to work correctly in a concurrent environment where many processes may try to access it, possibly at the same time. In implementing such a structure nothing can be assumed in advance about the number or the identities of the processes that might access it. While most of the known concurrent data structures are not public, there are few which are public. Interestingly, these public data structures all deal with various variants of counters, which are data structures that support two operations: increment and read. In this paper, we define the notion of a public data structure, and investigate several types of public counters. Then we give an optimal construction of public counters which satisfies a weak correctness condition, and show that there is no public counter which satisfies a stronger condition. It is hoped that this work will provide insights into the design of other, more complicated, public data structures.

I&C Journal 1999 Journal Article

The Power of Multiobjects

• Yehuda Afek
• Michael Merritt
• Gadi Taubenfeld

We consider shared memory systems that support multiobject operations in which processes may simultaneously access several objects in one atomic operation. We provide upper and lower bounds on the synchronization power (consensus number) of multiobject systems as a function of the type and the number of objects that may be simultaneously accessed in one atomic operation. These bounds imply that known classifications of component objects fail to characterize the synchronization power of their combination. In particular, we show that in the context of multiobjects, fetch & add objects are less powerful than swap objects, which in turn are less powerful than queue objects. This stands in contrast to the fact that swap can be implemented from fetch & add. Herein we introduce a restricted notion of implementation, called direct implementation. We show that, if objects of type Y have a direct implementation from objects of type X, then Y-based multiobjects can also be implemented from X-based multiobjects. Using this observation, we derive results such as: there are no direct implementations of swap or queue objects from any collection of commutative objects (e. g. , fetch & add, test & set).

I&C Journal 1996 Journal Article

Contention-Free Complexity of Shared Memory Algorithms

• Rajeev Alur
• Gadi Taubenfeld

Worst-case time complexity is a measure of the maximum time needed to solve a problem over all runs. Contention-free time complexity indicates the maximum time needed when a process executes by itself, without competition from other processes. Since contention is rare in well-designed systems, it is important to design algorithms which perform well in the absence of contention. We study the contention-free time complexity of shared memory algorithms using two measures: step complexity, which counts the number of accesses to shared registers; and register complexity, which measures the number of different registers accessed. Depending on the system architecture, one of the two measures more accurately reflects the elapsed time. We provide lower and upper bounds for the contention-free step and register complexity of solving the mutual exclusion problem as a function of the number of processes and the size of the largest register that can be accessed in one atomic step. We also present bounds on the worst-case and contention-free step and register complexities of solving the naming problem. These bounds illustrate that the proposed complexity measures are useful in differentiating among the computational powers of different primitives

STOC Conference 1994 Conference Paper

Time-adaptive algorithms for synchronization

• Rajeev Alur
• Hagit Attiya
• Gadi Taubenfeld

STOC Conference 1990 Conference Paper

The Wakeup Problem (Extended Abstract)

• Michael J. Fischer
• Shlomo Moran
• Steven Rudich
• Gadi Taubenfeld