Solvability of Three-Process General Tasks, with with Pierre Fraigniaud, Ami Paz and Sergio Rajsbaum long version

The journal version of “Lower Bounds on the Amortized Time Complexity of Shared Objects” (with Arie Fouren & Jeremy Ko) is published in Theory of Computing Systems. link

Two papers accepted to PODC 2024, to be held in June 2024, are now online.

• History-Independent Concurrent Objects, with Michael A. Bender, Martin Farach-Colton, Rotem Oshman and Noa Schiller. arxiv
• Strong Linearizability using Primitives with Consensus Number 2, with Armando Castañeda and Constantin Enea. arxiv

1. Attiya and Welch. Bounds on Worst-Case Responsiveness for Agreement Algorithms
2. Attiya and Welch. Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit arxiv
3. Attiya, Del Pozzo, Milani, Pavloff and Rapetti. The Synchronization Power of Auditable Registers arxiv
4. Lev Lehman, Attiya and Hendler. Recoverable and Detectable Self-Implementations of Swap arxiv

Two regular papers:

• Topological Characterization of Task Solvability in General Models of Computation with  Armando Castañeda and Thomas Nowak arxiv
• One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks with Pierre Fraigniaud, Ami Paz and Sergio Rajsbaum arxiv

Two brief announcments:

• Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit with Jennifer Welch arxiv
• Recoverable and Detectable Self-Implementations of Swap with Tomer Lev Lehman and Danny Hendler arxiv

Faithful Simulation of Randomized BFT Protocols on Block DAGs, with Constantin Enea and Shafik Nassar, was accepted to CONCUR 2023. paper in LIPIcs NEW

Participated in FCRC 2023 Plenary Panel: Reflecting on 50 Years of Computing Research, and Future Outlook. youtube recording

My paper with Armando Castañeda and Sergio Rajsbaum, “Locally Solvable Tasks and the Limitations of Valency Arguments” has appeared in Journal on Parallel and Distributed Computing (accessible link).

My paper with Faith Ellen, “The Step Complexity of Multidimensional Approximate Agreement“, which won the best paper award in OPODIS 2022 is now online.

Slides for my talk about hyperproprties and abstraction in concurrent objects, given at FRIDA 2022.