Hagit Attiya

TCS Journal 2025 Journal Article

Asynchronous fully-decentralized SGD in the cluster-based model

• Hagit Attiya
• Noa Schiller

This paper presents fault-tolerant asynchronous Stochastic Gradient Descent (SGD) algorithms. SGD is widely used for approximating the minimum of a cost function Q, a core part of optimization and learning algorithms. Our algorithms are designed for the cluster-based model, which combines message-passing and shared-memory communication layers. Processes may fail by crashing, and the algorithm inside each cluster is wait-free, using only reads and writes. For a strongly convex Q, our algorithm can withstand partitions of the system. It provides convergence rate that is the maximal distributed acceleration over the optimal convergence rate of sequential SGD. For arbitrary smooth functions, the convergence rate has an additional term that depends on the maximal difference between the parameters at the same iteration. (This holds under standard assumptions on Q.) In this case, the algorithm obtains the same convergence rate as sequential SGD, up to a logarithmic factor. This is achieved by using, at each iteration, a multidimensional approximate agreement algorithm, tailored for the cluster-based model. The general algorithm communicates with nonfaulty processes belonging to clusters that include a majority of all processes. We prove that this condition is necessary when optimizing some non-convex functions.

STOC Conference 2025 Conference Paper

History-Independent Concurrent Hash Tables

• Hagit Attiya
• Michael A. Bender
• Martín Farach-Colton
• Rotem Oshman
• Noa Schiller

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.

TCS Journal 2021 Journal Article

Specification and space complexity of collaborative text editing

• Hagit Attiya
• Sebastian Burckhardt
• Alexey Gotsman
• Adam Morrison
• Hongseok Yang
• Marek Zawirski

Collaborative text editing systems allow users to concurrently edit a shared document, inserting and deleting elements (e. g. , characters or lines). There are a number of protocols for collaborative text editing, but so far there has been no abstract, high-level specification of their desired behavior, which is decoupled from their actual implementation. Several of these protocols have been shown not to satisfy even basic expectations. This paper provides a precise specification of a replicated abstract list object, which models the core functionality of replicated systems for collaborative text editing. We define a strong list specification, which we prove is implemented by an existing protocol, as well as a weak list specification, which admits additional protocol behaviors. A major factor determining the efficiency and practical feasibility of a collaborative text editing protocol is the space overhead of the metadata that the protocol must maintain to ensure correctness. We show that for a large class of list protocols, implementing either the strong or the weak list specification requires a metadata overhead that is at least linear in the number of elements deleted from the list. The class of protocols to which this lower bound applies includes all list protocols that we are aware of, in particular CRDT and OT protocols, and we show that one of these protocols almost matches the bound. The result holds for peer-to-peer protocols, even if the network guarantees causal atomic broadcast. The result also holds for the metadata cost at the clients in client/server protocols. 1

TCS Journal 2013 Journal Article

A non-topological proof for the impossibility of k -set agreement

• Hagit Attiya
• Armando Castañeda

In the k -set agreement task, each process proposes a value and each correct process has to decide a value which was proposed, so that at most k distinct values are decided. Using topological arguments it has been proved that k -set agreement is unsolvable in the asynchronous wait-free read/write shared memory model, when k < n, the number of processes. This paper presents an elementary, non-topological impossibility proof of k -set agreement. The proof depends on two simple properties of the immediate snapshot executions, a subset of all possible executions, and on the well known handshaking lemma stating that every graph has an even number of vertices with odd degree.

TCS Journal 2011 Journal Article

Highly concurrent multi-word synchronization

• Hagit Attiya
• Eshcar Hillel

The design of concurrent data structures is greatly facilitated by the availability of synchronization operations that atomically modify k arbitrary items, such as k -read–modify–write ( k rmw ). Aiming to increase concurrency in order to exploit the parallelism offered by today’s multi-core and multi-processing architectures, we propose a highly concurrent software implementation of k rmw, with only constant space overhead. Our algorithm ensures that two operations delay each other only if they are within distance O ( k ) in the conflict graph, induced by the operations’ data items. The algorithm uses double compare-and-swap (dcas). When dcas is not supported by the architecture, the algorithm of Attiya and Dagan (2001) [3] can be used to replace dcas with (unary) cas, with only a slight increase in the interference among operations.

STOC Conference 2008 Conference Paper

Tight rmr lower bounds for mutual exclusion and other problems

• Hagit Attiya
• Danny Hendler
• Philipp Woelfel

We investigate the remote memory references (RMRs) complexity of deterministic processes that communicate by reading and writing shared memory in asynchronous cache-coherent and distributed shared-memory multiprocessors. We define a class of algorithms that we call order encoding . By applying information-theoretic arguments, we prove that every order encoding algorithm, shared by n processes, has an execution that incurs Ω(n log n) RMRs. From this we derive the same lower bound for the mutual exclusion, bounded counter and store/collect synchronization problems. The bounds we obtain for these problems are tight. It follows from the results of [10] that our lower bounds hold also for algorithms that can use comparison primitives and load-linked/store-conditional in addition to reads and writes. Our mutual exclusion lower bound proves a longstanding conjecture of Anderson and Kim.

STOC Conference 2007 Conference Paper

Tight bounds for asynchronous randomized consensus

• Hagit Attiya
• Keren Censor-Hillel

A distributed consensus algorithm allows n processes to reach acommon decision value starting from individual inputs. Wait-free consensus, in which a process always terminates within a finite number of its own steps, is impossible in anasynchronous shared-memory system. However, consensus becomes solvable using randomization when a process only has to terminatewith probability 1. Randomized consensus algorithms are typically evaluated by their total step complexity, which is the expected total number of steps taken by all processes.

I&C Journal 2004 Journal Article

Tight bounds for FEC-based reliable multicast

• Hagit Attiya
• Hadas Shachnai

We study the problem of reliable multicast of a message to a set of receivers over a network that uses best effort transmission (e. g. , ATM), based on forward error correcting codes (FEC). We prove lower bounds on the time and message complexities of any algorithm for the problem. We present a synchronous randomized algorithm which guarantees the reliable multicast of a packet of size m to n receivers within O(logn) steps, and whose expected message complexity is O(logm). Its storage complexity is linear in the size of the original packet. The average message and time complexities of the algorithm are within a constant multiplicative factor of the lower bounds.

I&C Journal 2002 Journal Article

Computing in Totally Anonymous Asynchronous Shared Memory Systems

• Hagit Attiya
• Alla Gorbach
• Shlomo Moran

In the totally anonymous shared memory model of asynchronous distributed computing, processes have no identifiers and run identical programs. Moreover, processes have identical interface to the shared memory, and in particular, there are no single-writer registers. This paper assumes that processes do not fail, and the shared memory consists only of read/write registers, which are initialized to some default value. A complete characterization of the functions and agreement tasks that can be solved in this model is presented. Furthermore, it is shown that if a function is computable, then two registers are sufficient for some algorithm to compute it. Consensus is an important agreement task that can be computed. The paper proves logarithmic lower bounds on the number of registers and rounds needed for solving consensus in this model. A consensus protocol using a linear number of shared registers and rounds is also presented.

STOC Conference 1994 Conference Paper

Time-adaptive algorithms for synchronization

• Rajeev Alur
• Hagit Attiya
• Gadi Taubenfeld

STOC Conference 1992 Conference Paper

A Correctness Condition for High-Performance Multiprocessors (Extended Abstract)

• Hagit Attiya
• Roy Friedman 0001

SODA Conference 1992 Conference Paper

Counting Networks with Arbitrary Fan-Out

• Eran Aharonson
• Hagit Attiya

STOC Conference 1991 Conference Paper

Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty

• Hagit Attiya
• Cynthia Dwork
• Nancy A. Lynch
• Larry J. Stockmeyer

FOCS Conference 1990 Conference Paper

Are Wait-Free Algorithms Fast? (Extended Abstract)

• Hagit Attiya
• Nancy A. Lynch
• Nir Shavit

The time complexity of wait-free algorithms in so-called normal executions, where no failures occur and processes operate at approximately the same speed, is considered. A lower bound of log n on the time complexity of any wait-free algorithm that achieves approximate agreement among n processes is proved. In contrast, there exists a non-wait-free algorithm that solves this problem in constant time. This implies an Omega (log n)-time separation between the wait-free and non-wait-free computation models. An O(log n)-time wait-free approximate agreement algorithm is presented. Its complexity is within a small constant of the lower bound. >

FOCS Conference 1987 Conference Paper

Achievable Cases in an Asynchronous Environment (Extended Abstract)

• Hagit Attiya
• Amotz Bar-Noy
• Danny Dolev
• Daphne Koller
• David Peleg
• Rüdiger Reischuk

The paper deals with achievability of fault tolerant goals in a completely asynchronous distributed system. Fischer, Lynch, and Paterson [FLP] proved that in such a system "nontrivial agreement" cannot be achieved even in the (possible) presence of a single "benign" fault. In contrast, we exhibit two pairs of goals that are achievable even in the presence of up to t ≪ n/2 faulty processors, contradicting the widely held assumption that no nontrivial goals are attainable in such a system. The first pair deals with renaming processors so as to reduce the size of the initial name space. When only uniqueness is required of the new names, we present a lower bound of n + 1 on the size of the new name space, and a renaming algorithm which establishes an upper bound of n + t. In case the new names are required also to preserve the original order, a tight bound of 2t(n- t + 1) - 1 is obtained. The second pair of goals deals with the multi-slot critical section problem. We present algorithms for controlled access to a critical section. As for the number of slots required, a tight bound of t + 1 is proved in case the slots are identical. In the case of distinct slots the upper bound is 2t + 1.

TCS Journal 1987 Journal Article

Language complexity on the synchronous anonymous ring

• Hagit Attiya
• Yishay Mansour

A set of n nondistinct processors, organized as a ring and operating synchronously, have to compute a function of their initial values. Every computable function can be computed with O(n log n) messages, while some functions can be computed with as few as O(n) messages. We prove a necessary and sufficient condition for a regular language to be recognized with O(n) messages. Languages that do not satisfy this condition are ‘hard’ to compute, i. e. , their recognition requires Ω(n log n) message. The condition is an extension of the notion of counter-free regular languages. These results give a gap theorem for recognizing regular languages on the synchronous anonymous ring. In contrast, we show a family of nonregular languages, computing thresholds, that obtain any intermediate complexity in the range ϴ(n) to ϴ(n log n).