Eli Gafni

TCS Journal 2021 Journal Article

The assignment problem

• Carole Delporte-Gallet
• Hugues Fauconnier
• Eli Gafni
• Giuliano Losa

In the allocation problem, asynchronous processors must partition a set of items so that each processor leaves knowing all items exclusively allocated to it. We introduce a new variant of the allocation problem called the assignment problem, in which processors might leave having only partial knowledge of their assigned items. The missing items in a processor's assignment must eventually be announced by other processors. While allocation has consensus number 2, we show that the assignment problem is solvable read-write wait-free when k processors compete for at least 2 k − 1 items. Moreover, we propose a long-lived read-write wait-free assignment algorithm which is fair, allocating no more than 2 items per processor, and in which a slow processor may delay the assignment of at most n items, where n is the number of processors. The assignment problem and its read-write solution may be of practical interest for implementing resource allocators and work queues, which are pervasive concurrent programming patterns, as well as stream-processing systems.

TCS Journal 2018 Journal Article

Group mutual exclusion in linear time and space

• Yuan He
• K. Gopalakrishnan
• Eli Gafni

We present two algorithms for the Group Mutual Exclusion (GME) Problem that satisfy the properties of Mutual Exclusion, Starvation Freedom, Bounded Exit, Concurrent Entry and First Come First Served. Both our algorithms use only simple read and write instructions, have O ( N ) Shared Space complexity and O ( N ) Remote Memory Reference (RMR) complexity in the Cache Coherency (CC) model. Our first algorithm is developed by generalizing the well-known Lamport's Bakery Algorithm for the classical mutual exclusion problem, while preserving its simplicity and elegance. However, it uses unbounded shared registers. Our second algorithm uses only bounded registers and is developed by generalizing Taubenfeld's Black and White Bakery Algorithm to solve the classical mutual exclusion problem using only bounded shared registers. We show that contrary to common perception our algorithms are the first to achieve these properties with this combination of complexities.

TCS Journal 2015 Journal Article

A simple characterization of asynchronous computations

• Yehuda Afek
• Eli Gafni

In this paper we investigate synchronous message-passing systems with reliable processors but different scenarios of message loss. In particular, we investigate and present the minimum set of messages whose delivery must be guaranteed to ensure the equivalence of this model to asynchronous wait–free shared-memory. Delivery guarantees were investigated in the past at the other extreme – delivery guarantees that ensure consensus. Because message failure is a more refined type of fault than processor crash failure, we were able to use in this paper an extremely simple message-passing model to characterize exactly what is computable in wait–free read–write shared memory. We use a synchronous complete network where in each round a subset from a defined family of subsets of messages, must be successfully delivered. With this model we obtain an extremely simple derivation of the Herlihy–Shavit condition that equates the wait–free read–write model with a subdivided-simplex. We show how each step in the computation inductively takes a subdivided-simplex and further subdivides it in the simplest way possible, making the characterization of read–write wait–free widely accessible.

TCS Journal 2015 Journal Article

Linear space bootstrap communication schemes

• Carole Delporte-Gallet
• Hugues Fauconnier
• Eli Gafni
• Sergio Rajsbaum

Consider a system of n processes with ids that are drawn from a large space. How can these n processes communicate to solve a problem? It is shown that linear number of Multi-Writer Multi-Reader (MWMR) registers are sufficient to solve any read-write wait-free solvable problem and needed to solve some read-write wait-free solvable problem. This contrasts with the existing possible solution borrowed from adaptive algorithms that require Θ ( n 3 / 2 ) MWMR registers. To obtain the sufficiency result, the paper shows how the processes can non-blocking emulate a system of n Single-Writer Multi-Reader (SWMR) registers on top of n Multi-Writer Multi-Reader (MWMR) registers. For the necessity result, it shows it is impossible to do such an emulation with n − 1 MWMR registers. The paper also presents a wait-free emulation, using 2 n − 1 rather than just n registers. The emulation can be used to solve an infinite sequence of tasks that are sequentially dependent (processes need the previous task's outputs in order to proceed to the next task). A non-blocking emulation cannot be used in this case, because it might starve a process forever.

TCS Journal 2009 Journal Article

From adaptive renaming to set agreement

• Eli Gafni
• Achour Mostéfaoui
• Michel Raynal
• Corentin Travers

The adaptive M -renaming problem consists of providing processes with a new name taken from a name space whose size M depends only on the number p of processes that participate in the renaming (and not on the total number n of processes that could ask for a new name). The k -set agreement problem allows each process that proposes a value to decide a proposed value in such a way that at most k different values are decided. In an asynchronous system prone to up to t process crash failures, and where processes can cooperate by accessing atomic read/write registers only, the best that can be done is a renaming space of size M = p + t. In the same setting, the k -set agreement problem cannot be solved when t ≥ k. This paper focuses on the way a solution to the adaptive renaming problem can help in solving the k -set agreement problem when t ≥ k. It has two contributions. Considering the case k = t ( 1 ≤ t < n ), the first contribution is a t -resilient algorithm that solves the k -set agreement problem from any adaptive ( p + k − 1 ) -renaming algorithm. The second contribution considers the case k < t. It shows that there is no such wait-free algorithm when k < n / 2 (wait-free means t = n − 1 ). So, while a solution to the adaptive ( p + k − 1 ) -renaming problem allows t -resiliently solving the k -set agreement problem despite t = k failures, when k < t such an additional power becomes useless for the values of n > 2 k (i. e. adaptive ( p + k − 1 ) -renaming allows progressing from k > t to k = t, but does not allow bypassing the “ k = t ” frontier when n > 2 k ).

STOC Conference 2009 Conference Paper

The extended BG-simulation and the characterization of t-resiliency

• Eli Gafni

A distributed task T on n processors is an input/output relation between a collection of processors' inputs and outputs. While all tasks are solvable if no processor may ever crash, the FLP result revealed that the possibility of a failure of just a single processor precludes a solution to the task of consensus. That is consensus is not solvable 1-resiliently. Yet, some nontrivial tasks are wait-free solvable, i.e. n-1-resiliently. What tasks are solvable if at most t 1 and 0 1 and n>2, is undecidable, by a simple reduction to the undecidability of the wait-free solvability of 3-processors tasks.

STOC Conference 2005 Conference Paper

From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement

• Eli Gafni
• Rachid Guerraoui
• Bastian Pochon

Set agreement, where processors decisions constitute a set of outputs, is notoriously harder to analyze than consensus where the decisions are restricted to a single output. This is because the topological questions that underly set agreement are not about simple connectivity as in consensus. Analyzing set agreement inspired the discovery of the relation between topology and distributed algorithms, and consequently the impossibility of asynchronous set agreement.Yet, the application of topological reasoning has been to the static case, that of asynchronous and synchronous tasks. It is not known yet for example, how to characterize starvation-free solvability of non-terminating tasks. Non-terminating tasks are dynamic entities with no defined end. In a similar vain, early deciding synchronous set agreement, in which the number of rounds it takes a processor to decide adapts to the actual number of failures, falls in this category of dynamic entities.This paper develops a simulation technique that brings to bear topological results to deal with the dynamic situation that arises with early decisions. The novelty of the new simulation is the ability of simulators to look back at the transcript of past rounds of the simulation to influence their current behavior.Using our new technique, we not only re-derive past results, but we propose and prove a lower bound to synchronous early stopping set agreement. We then provide an algorithm to match the lower bound. Our technique uses the BG simulation, in the most creative way it was used to-date, to obtain a rather simple reduction from a static asynchronous impossibility. This reduction is a simple alternative to yet unknown topological argument, and in fact may suggest the way of finding such an argument.

FOCS Conference 2002 Conference Paper

A Simple Algorithmic Characterization of Uniform Solvability

• Eli Gafni

The Herlihy-Shavit (HS) conditions characterizing the solvability of asynchronous tasks over n processors have been a milestone in the development of the theory of distributed computing. Yet, they were of no help when researcher sought algorithms that do not depend on n. To help in this pursuit we investigate the uniform solvability of an infinite uniform sequence of tasks T/sub 0/, T/sub 1/, T/sub 2/, .. ., where T/sub i/ is a task over processors p/sub 0/, p/sub 1/, .. ., p/sub i/, and T/sub i/ extends T/sub i-1/. We say that such a sequence is uniformly solvable if there exit protocols to solve each T/sub i/ and the protocol for T/sub i/ extends the protocol for T/sub i-1/. This paper establishes that although each T/sub i/ may be solvable, the uniform sequence is not necessarily uniformly solvable. We show this by proposing a novel uniform sequence of solvable tasks and proving that the sequence is not amenable to a uniform solution. We then extend the HS conditions for a task over n processors, to uniform solvability in a natural way. The technique we use to accomplish this is to generalize the alternative algorithmic proof, by Borowsky and Gafni, of the HS conditions, by showing that the infinite uniform sequence of task of Immediate Snapshots is uniformly solvable. A side benefit of the technique is a widely applicable methodology for the development of uniform protocols.

STOC Conference 1993 Conference Paper

Generalized FLP impossibility result for t-resilient asynchronous computations

• Elizabeth Borowsky
• Eli Gafni

TCS Journal 1989 Journal Article

On separating the EREW and CREW PRAM models

• Eli Gafni
• Joseph Naor
• Prabhakar Ragde

In (1985), Snir proposed the Selection Problem (searching in a sorted table) to show that the CREW PRAM is strictly more powerful than the EREW PRAM. This problem defines a partial function, that is, one that is defined only on a restricted set of inputs. Recognizing whether an arbitrary input belongs to this restricted set is hard for both CREW and EREW PRAMs. The existence of a total function that exhibits the power of the CREW model over the EREW model was an open problem. Here we solve this problem by generalizing the Selection Problem to a decision tree problem which is defined on a full domain and to which Snir's lower bound applies.

FOCS Conference 1989 Conference Paper

Upper and Lower Bounds for Routing Schemes in Dynamic Networks (Abstract)

• Yehuda Afek
• Eli Gafni
• Moty Ricklin

An algorithm and two lower bounds are presented for the problem of constructing and maintaining routing schemes in dynamic networks. The algorithm distributively assigns addresses to nodes and constructs routing tables in a dynamically growing tree. The resulting scheme routes data messages over the shortest path between any source and destination, assigns addresses of O(log/sup 2/n) bits to each node, and uses in its routing table O(log/sup 3/n) bits of memory per incident link, where n is the final number of nodes in the tree. The amortized communication cost of the algorithm is O(log n) messages per node. Also given are two lower bounds on the tradeoff between the quality of routing schemes (i. e. their stretch factor) and their amortized communication cost in general dynamic networks. >

STOC Conference 1988 Conference Paper

Toward a Non-Atomic Era: \ell-Exclusion as a Test Case

• Danny Dolev
• Eli Gafni
• Nir Shavit

Most of the research in concurrency control has been based on the existence of strong synchronization primitives such as test and set. Following Lamport, recent research promoting the use of weaker primitives, “safe” rather than “atomic,” has resulted in construction of atomic registers from safe ones, in the belief that they would be useful tools for process synchronization. We argue that the properties provided by atomic operations may be too powerful, masking core difficulties of problems and leading to inefficiency. We therefore advocate a different approach, to skip the intermediate step of achieving atomicity, and solve problems directly from safe registers. Though it has been shown that “test and set” cannot be implemented from safe registers, we show how to achieve a fair solution to l -exclusion, a classical concurrency control problem previously solved assuming a very powerful form of atomic “test and set”. We do so using safe registers alone and without introducing atomicity. The solution is based on the construction of a simple novel non-atomic synchronization primitive.

FOCS Conference 1987 Conference Paper

Applying Static Network Protocols to Dynamic Networks

• Yehuda Afek
• Baruch Awerbuch
• Eli Gafni

This paper addresses the problem of how to adapt an algorithm designed for fixed topology networks to produce the intended results, when run in a network whose topology changes dynamically, in spite of encountering topological changes during its execution. We present a simple and unified procedure, called a reset procedure, which, when combined with the static algorithm, achieves this adaptation. The communication and time complexities of the reset procedure, per topological change, are independent of the number of topological changes and are linearly bounded by the size of the subset of the network which participates in the algorithm.

TCS Journal 1987 Journal Article

Distributed sorting algorithms for multi-channel broadcast networks

• John M. Marberg
• Eli Gafni

A multi-channel broadcast network is a distributed computation model in which p independent processors communicate over a set of p shared broadcast channels. Computation proceeds in synchronous cycles, during each of which the processors first write and read the channels, then perform local computations. Performance is measured in terms of the number of cycles used in the computation, where each bit to be transmitted is assumed to require a separate cycle. In this paper we investigate the problem of sorting p bit strings of uniform length m, each string initially located at a different processor in the broadcast network. We develop an efficient sorting method that first reduces the length of the strings without affecting their relative order, then proceeds using only the shorter strings. A sequence of three successively improved algorithms based on this approach is presented, the best of which runs in O(m + p log p) cycles. By showing a lower bound of Ω(m) cycles, we prove that the algorithm is optimal for sufficiently large m. Our results improve by a factor of log p the solution of the multiple identification problem presented by Landau, Yung and Galil (1985).