10 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,…
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…
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…
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 ()…
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…