3 citations · 14 across the 23 of their papers we have counts for
33 papers
Non-Leaking Concurrent Objects
Hagit Attiya, Rotem Oshman, Noa Schiller +1
Abstract specifications of concurrent objects determine which values operations may return, but they also implicitly constrain which information operations may know, for example th…
Space-Efficient Lock-Free Linear-Probing Hash Table
Hagit Attiya, Rotem Oshman, Noa Schiller
Linear probing is one of the simplest and most space-efficient approaches to hash table design, and is widely used in sequential settings due to its compact memory layout. However,…
Recoverable Lock-Free Locks
Hagit Attiya, Panagiota Fatourou, Eleftherios Kosmas +1
This paper presents the first transformation that introduces both lock-freedom and recoverability. Our transformation starts with a lock-based implementation, and provides a recove…
Equivalence and Separation between Heard-Of and Asynchronous Message-Passing Models
Hagit Attiya, Armando Castañeda, Dhrubajyoti Ghosh +1
We revisit the relationship between two fundamental models of distributed computation: the asynchronous message-passing model with up to crash failures ()…
Arbitration-Free Consistency is Available (and Vice Versa)
Hagit Attiya, Constantin Enea, Enrique Román-Calvo
The fundamental tension between availability and consistency shapes the design of distributed storage systems. Classical results capture extreme points of this trade-off: the CAP t…
Why Canonical Rounds Fail for Optimal Byzantine Resilience
Hagit Attiya, Itay Flam, Jennifer L. Welch
Canonical asynchronous rounds are a widely used abstraction for structuring distributed algorithms, making asynchronous executions appear synchronous and enabling modular reasoning…
Auditable Shared Objects: From Registers to Synchronization Primitives
Hagit Attiya, Antonio Fernández Anta, Alessia Milani +2
Auditability allows to track operations performed on a shared object, recording who accessed which information. This gives data owners more control on their data. Initially studied…
Impossibility Results for Strong Linearizability: The Difficulty of Consistent Refereeing
Hagit Attiya, Armando Castañeda, Constantin Enea
This paper studies the relation between agreement and strongly linearizable implementations of various objects. This leads to new results about implementations of concurrent object…
Auditing without Leaks Despite Curiosity
Hagit Attiya, Antonio Fernández Anta, Alessia Milani +2
\textit{Auditing} data accesses helps preserve privacy and ensures accountability by allowing one to determine who accessed (potentially sensitive) information. A prior formal defi…
History-Independent Concurrent Hash Tables
Hagit Attiya, Michael A. Bender, Martín Farach-Colton +2
A history-independent data structure does not reveal the history of operations applied to it, only its current logical state, even if its internal state is examined. This paper stu…
History-Independent Concurrent Objects
Hagit Attiya, Michael A. Bender, Martin Farach-Colton +2
A data structure is called history independent if its internal memory representation does not reveal the history of operations applied to it, only its current state. In this paper…
Strong Linearizability using Primitives with Consensus Number 2
Hagit Attiya, Armando Castañeda, Constantin Enea
A powerful tool for designing complex concurrent programs is through composition with object implementations from lower-level primitives. Strongly-linearizable implementations allo…
The Synchronization Power of Auditable Registers
Hagit Attiya, Antonella Del Pozzo, Alessia Milani +2
Auditability allows to track all the read operations performed on a register. It abstracts the need of data owners to control access to their data, tracking who read which informat…
Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit
Hagit Attiya, Jennifer L. Welch
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 a…
One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks
Hagit Attiya, Pierre Fraigniaud, Ami Paz +1
The paper compares two generic techniques for deriving lower bounds and impossibility results in distributed computing. First, we prove a speedup theorem (a-la Brandt, 2019), for w…
Recoverable and Detectable Self-Implementations of Swap
Tomer Lev Lehman, Hagit Attiya, Danny Hendler
Recoverable algorithms tolerate failures and recoveries of processes by using non-volatile memory. Of particular interest are self-implementations of key operations, in which a rec…
Topological Characterization of Task Solvability in General Models of Computation
Hagit Attiya, Armando Castañeda, Thomas Nowak
The famous asynchronous computability theorem (ACT) relates the existence of an asynchronous wait-free shared memory protocol for solving a task with the existence of a simplicial…
Recovery of Distributed Iterative Solvers for Linear Systems Using Non-Volatile RAM
Yehonatan Fridman, Yaniv Snir, Harel Levin +3
HPC systems are a critical resource for scientific research. The increased demand for computational power and memory ushers in the exascale era, in which supercomputers are designe…
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 , as a core par…
Assessing the Use Cases of Persistent Memory in High-Performance Scientific Computing
Yehonatan Fridman, Yaniv Snir, Matan Rusanovsky +5
As the High Performance Computing world moves towards the Exa-Scale era, huge amounts of data should be analyzed, manipulated and stored. In the traditional storage/memory hierarch…
Blunting an Adversary Against Randomized Concurrent Programs with Linearizable Implementations
Hagit Attiya, Constantin Enea, Jennifer L. Welch
Atomic shared objects, whose operations take place instantaneously, are a powerful abstraction for designing complex concurrent programs. Since they are not always available, they…
Impossibility of Strongly-Linearizable Message-Passing Objects via Simulation by Single-Writer Registers
Hagit Attiya, Constantin Enea, Jennifer Welch
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-tole…
Optimal Resilience in Systems that Mix Shared Memory and Message Passing
Hagit Attiya, Sweta Kumari, Noa Schiller
We investigate the minimal number of failures that can partition a system where processes communicate both through shared memory and by message passing. We prove that this number p…
Flat-Combining-Based Persistent Data Structures for Non-Volatile Memory
Matan Rusanovsky, Hagit Attiya, Ohad Ben-Baruch +3
Flat combining (FC) is a synchronization paradigm in which a single thread, holding a global lock, collects requests by multiple threads for accessing a concurrent data structure a…