Publications


Non-technical writing (surveys, opinion pieces, etc)

  1. Indistiguishability, with Sergio Rajsbaum, Communications of the ACM, May 2020. new
  2. Shared Memory and the Bakery Algorithm (with Jennifer Welch), Chapter 1 in the book Concurrency: The Works of Leslie Lamport (also here). new
  3. Lower Bounds and Impossibility Results for Transactional Memory Computing. Bulletin of the EATCS 112, February 2014.
  4. Robust Simulation of Shared Memory: 20 Years After, EATCS Distributed Computing Column, 100, pages 99-113, February 2010.
  5. Distributing your data and having it, too, technical perspective for Communications of the ACM, Vol. 51, No. 9, September 2008.
  6. Martin Vechev, Eran Yahav, Maged Michael, Hagit Attiya, and Greta Yorsh, Computer Assisted Construction of Efficient Concurrent Algorithms, in Exploiting Concurrency Efficiently and Correctly (EC)2, CAV 2008 workshop.
  7. Needed: Foundations for Transactional Memory, in ACM SIGACT News Distributed Computing Column, Vol. 39, No. 1, March 2008.
  8. Concurrency and the Principle of Data Locality, (local copy) in the Distributed Wisdom column of IEEE DS Online, Vol. 8, No. 9, 2007.

Papers in peer-reviewed conferences

  1. Hagit Attiya, Sweta Kumari, Archit Somani, Jennifer L. Welch, Collect in the Presence of Continuous Churn with Application to Snapshots and Lattice Agreement. In SSS 2020Video link for brief announcement in PODC 2020. arxiv new
  2. Hagit Attiya, Ohad Ben-Baruch, Panagiota Fatourou, Danny Hendler, Eleftherios Kosmas, Tracking in Order to Recover – Detectable Recovery of Lock-Free Data Structures. Video link for brief announcement in SPAA 2020. arxiv new
  3. Parwat Singh Anjana, Hagit Attiya, Sweta Kumari, Sathya Peri and Archit Somani. Efficient Concurrent Execution of Smart Contracts in Blockchains using Object-based Transactional Memory, Netys 2020. (Video Link)
  4. Eleni Kanellou, Hagit Attiya, Panagiota Fatourou and Sandeep Hans. Staleness and Local Progress in Transactional Memory, Netys 2020 (Video Link)
  5. Hagit Attiya, Constantin Enea:
    Putting Strong Linearizability in Context: Preserving Hyperproperties in Programs that Use Concurrent Objects. DISC 2019
  6. Artem Khyzha, Hagit Attiya, Alexey Gotsman:
    Privatization-Safe Transactional Memories. DISC 2019
  7. Hagit Attiya, Ohad Ben-Baruch, Danny Hendler:
    Nesting-Safe Recoverable Linearizability: Modular Constructions for Non-Volatile Memory. PODC 2018
  8. Hagit Attiya, Armando Castañeda, Danny Hendler, Matthieu Perrin:
    Separating Lock-Freedom from Wait-Freedom. PODC 2018
  9. Artem Khyzha, Hagit Attiya, Alexey Gotsman, Noam Rinetzky:
    Safe privatization in transactional memory. PPOPP 2018
  10. Hagit Attiya, Gili Yavneh. Remote Memory References at Block Granularity. OPODIS 2017
  11. Hagit Attiya, Arie Fouren.
    Lower Bounds on the Amortized Time Complexity of Shared Objects. OPODIS 2017
  12. Hagit Attiya, Ohad Ben-Baruch, Danny Hendler.
    Lower Bound on the Step Complexity of Anonymous Binary Consensus. DISC 2016: 257-268
  13. Hagit Attiya, Sebastian Burckhardt, Alexey Gotsman, Adam Morrison, Hongseok Yang, Marek Zawirski.
    Specification and Complexity of Collaborative Text Editing. PODC 2016: 259-268
  14. Hagit Attiya, Hyun Chul Chung, Faith Ellen, Saptaparni Kumar, Jennifer L. Welch:
    Simulating a Shared Register in an Asynchronous System that Never Stops Changing. DISC 2015: 75-91
  15. Hagit Attiya, Danny Hendler and Philipp Woelfel.
    Trading Fences with RMRs and Separating Memory Models.
    PODC 2015.
  16. Hagit Attiya, Faith Ellen and Adam Morrison
    Limitations of Highly-Available Eventually-Consistent Data Stores.
    PODC 2015.
  17. Hagit Attiya, Alexey Gotsman, Sandeep Hans and Noam Rinetzky.
    Safety of Live Transactions in Transactional Memory: TMS is Necessary and Sufficient.
    DISC 2014.
  18. Maya Arbel and Hagit Attiya
    Concurrent updates with RCU: search tree as an example.
    PODC 2014.
    Covered by Paul McKenney in Linux Weekly News.
  19. Hagit Attiya, Armando Castaneda, Maurice Herlihy and Ami Paz.
    Upper Bound on the Complexity of Solving Hard Renaming.
    PODC 2013.  (Best student paper award)
  20. Hagit Attiya, Danny Hendler and Smadar Levy.
    An O(1)-Barriers Optimal RMRs Mutual Exclusion Algorithm.
    PODC 2013.
  21. Hagit Attiya, Alexey Gotsman, Sandeep Hans and Noam Rinetzky.
    A Programming Language Perspective on Transactional Memory Consistency.
    to appear in PODC 2013. Extended version (TR)
  22. Hagit Attiya, Sandeep Hans, Petr Kuznetsov and Srivatsan Ravi.
    Safety of Deferred Update in Transactional Memory.
    to appear in ICDCS 2013. arxiv
  23. Hagit Attiya and Ami Paz.
    Counting-Based Impossibility Proofs for Renaming and Set Agreement
    extended abstract to appear in DISC 2012. Ami’s presentation
  24. James Aspnes, Hagit Attiya, Keren Censor-Hillel and Danny Hendler.
    “Lower Bounds for Restricted-Use Objects”,
    extended abstract in SPAA 2012.
  25. Dan Alistarh, Hagit Attiya, Rachid Guerraoui, Corentin Travers,
    “Early Deciding Synchronous Renaming in O(log f) Rounds or Less”,
    extended abstract in SIROCCO 2012.
  26. Hagit Attiya and Armando Castañeda,
    “A Non-topological Proof for the Impossibility of k-Set Agreement.
    extended abstract in SSS 2011.
  27. Hagit Attiya, Fatemeh Borran, Martin Hutle, Zarko Milosevic and Andre Schiper
    “Structured Derivation of Semi-Synchronous Algorithm”,
    extended abstract in DISC 2011.
  28. Hagit Attiya, Rachid Guerraoui, Danny Hendler, Petr Kuznetsov, Maged M. Michael and Martin Vechev,
    “Laws of Order: Expensive Synchronization in Concurrent Algorithms Cannot be Eliminated”,
    extended abstract to appear in POPL 2011.
    Coverage by Paul McKenney in Linux Weekly News.
  29. Hagit Attiya, Vincent Gramoli and Alessia Milani,
    “A Provably Starvation-Free Distributed Directory Protocol”,
    extended abstract in SSS 2010.
  30. Dan Alistarh, Hagit Attiya, Seth Gilbert, Andrei Giurgiu, and Rachid Guerraoui,
    “Fast Randomized Test-and-Set and Renaming”,
    extended abstract in DISC 2010.
    Technical Report EPFL-REPORT-149943, July 2010.
  31. Hagit Attiya, G. Ramalingam and Noam Rinetzky,
    “Sequential Verification of Serializability”,
    extended abstract to appear in POPL 2010. TR  slides
  32. James Aspnes, Hagit Attiya and Keren Censor,
    “Randomized Consensus with O(n log n) Individual Work”,
    extended abstract in PODC 2008.
  33. Hagit Attiya, Rachid Guerraoui and Eric Ruppert,
    “Partial Snapshot Objects”,
    extended abstract in SPAA 2008. slides
  34. Hagit Attiya, Danny Hendler and Philipp Woelfel,
    “Tight RMR Lower Bounds for Mutual Exclusion and Other Problems”,
    extended abstract in STOC 2008.
  35. Hagit Attiya, Rachid Guerraoui, Danny Hendler and Petr Kouznetsov,
    “Synchronizing without Locks is Inherently Expensive”,
    extended abstract in PODC 2006.
  36. Hagit Attiya, David Hay and Jennifer L. Welch,
    “Optimal Clock Synchronization under Energy Constraints in Wireless Ad-Hoc Networks”,
    extended abstract in OPODIS 2005.
  37. Hagit Attiya, Rachid Guerraoui and Petr Kouznetsov,
    “Computing with Reads and Writes in the Absence of Step Contention”,
    extended abstract in DISC 2005 (EPFL technical report).
  38. R. Nossenson and H. Attiya,
    “The N-Burst/G/1 model with heavy-tailed service-times distribution”,
    extended abstract in MASCOTS 2004.
  39. H. Attiya, F. Fich and Y. Kaplan,
    “Lower Bounds for Adaptive Collect and Related Problems”,
    extended abstract in PODC 2004. Presentation
  40. R. Nossenson and H. Attiya,
    “Evaluating Self-Similar Processes for Modeling Web Servers”,
    extended abstract in SPECTS 2004.
  41. H. Attiya and Idan Zach,
    “Incremental Calculation for Fully-Adaptive Algorithms, ”
    Brief announcement in DISC 2004 (presentation).
    unpublished manuscript.
  42. Hagit Attiya, Arie Fouren and Eli Gafni,
    “A Polynomial Adaptive Algorithm for Long-Lived (2k-1)-Renaming”,
    full version submitted for publication.
  43. H. Attiya and Z. Avidor,
    “Wait-Free n-set Consensus when Inputs are Restricted”,
    extended abstract in DISC 2002.
  44. H. Attiya and A. Fouren,
    “Polynomial and Adaptive Long-lived (2k-1)-Renaming,”
    Extended abstract in DISC 2000. (Best student paper award)
  45. Y. Afek, H. Attiya, A. Fouren, G. Stupp and D. Touitou.
    “Adaptive Long-Lived Renaming using Bounded Memory,”
    manuscript.
  46. Y. Afek, H. Attiya, A. Fouren, G. Stupp and D. Touitou.
    “Long-Lived Renaming Made Adaptive,”
    Regular presentation in PODC99.
  47. H. Attiya,
    “A Direct Proof of the Asynchronous Lower Bound for k-Set Consensus”
    Brief announcement in PODC98 (slides).
    Full version available as Technical Report 0930, Department of Computer Science, The Technion.
  48. J. Kleinberg, H. Attiya and N. A. Lynch,
    “Trade-Offs Between Message Delivery and Quiesce Times in Connection Management Protocols,”
    ISTCS 1995.  ps
  49. H. Attiya and R. Friedman,
    “Programming DEC-Alpha Based Multiprocessors the Easy Way,”
    SPAA 1994.
    Full version available as Technical Report LPCR 9411, Department of Computer Science, Technion, October 1994.

Papers that appeared in journals (NOT UP TO DATE, REFER TO DBLP)

  1. James Aspnes, Hagit Attiya, Keren Censor-Hillel and Faith Ellen.
    “Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity”,
    Journal of the ACM, Volume 62, Issue 1, Article 3, February 2015. link to ACM DL
    Previously, an extended abstract in PODC 2012. new
  2. Hagit Attiya and Eshcar Hillel,
    “The Cost of Privatization in Software Transactional Memory”,
    to appear in IEEE Transactions on Computers. local copy
    Previously, an extended abstract in DISC 2010. slides
  3. Hagit Attiya and Eshcar Hillel,
    “Built-in Coloring for Highly-Concurrent Doubly-Linked Lists”,
    Theory of Computing Systems 52(4): 729-762 (2013). Springer link local copy
    Previously, an extended abstract in DISC 2006. presentation
  4. Hagit Attiya and Alessia Milani,
    “Transactional Scheduling for Read-Dominated Workloads”,
    Journal of Parallel and Distributed Computing, Volume 72, Issue 10, October 2012, Pages 1386–1396. link to Science Direct local copy
    Previously, an extended abstract in OPODIS 2009. (Best paper award)
  5. Hagit Attiya and Eshcar Hillel,
    “A Single-Version STM that is Multi-Version Permissive”,
    Theory of Computing Systems, Volume 51, Issue 4 (2012), Page 425-446. Springer link local copy
    Previously, an extended abstract in ICDCN 2011.
    Also, brief announcement in PODC 2010.
  6. James Aspnes, Hagit Attiya and Keren Censor,
    “Polylogarithmic concurrent data structures from monotone circuits”,
    Journal of the ACM, Volume 59, Issue 1, Article 2, February 2012. link to ACM DL
    Previously, an extended abstract in PODC 2009. new (Best student paper award)
  7. Hagit Attiya, Faith Ellen and Panagiota Fatourou,
    “The Complexity of Updating Multi-Writer Snapshot Objects”,
    Journal on Parallel and Distributed Computing, Volume 71, Issue 12, December 2011, Pages 1570–1577. Link to Science Direct
    Previously, an extended abstract in ICDCN 2006.
  8. Hagit Attiya and Eshcar Hillel
    “Highly-Concurrent Multi-Word Synchronization”,
    Theoretical Computer Science 412 (March 2011), pages 1243–1262. local copy link to Science Direct
    Previously, an extended abstract in ICDCN 2008.
  9. Hagit Attiya, Eshcar Hillel and Alessia Milani
    “Inherent Limitations on Disjoint-Access Parallel Implementations of Transactional Memory”,
    Theory of Computer Systems, Volume 49, Number 4 / November 2011, pages 698-719. Link to Springer Online local copy
    Previously, an extended abstract in SPAA 2009, and short paper in Transact 2009.
  10. Hagit Attiya, David Hay and Isaac Keslassy,
    “Packet-Mode Emulation of Output-Queued Switches”,
    IEEE Transactions on Computers 59(10): 1378-1391 (2010).  Link to IEEE Xplore
    Previously, an extended abstract in SPAA 2006.
  11. Hagit Attiya and Keren Censor,
    “Lower Bounds for Randomized Consensus under a Weak Adversary”,
    Full version in SIAM Journal on Computing, Vol.39, No.8 (2010), pp. 3885-3904.   Link to SIAM Online
    Previously, an extended abstract in PODC 2008.
  12. James Aspnes, Hagit Attiya and Keren Censor,
    “Combining Shared Coin Algorithms”,
    Journal of Parallel and Distributed Computing, Volume 70 (2010), pp. 317-322. pdf   link to Science Direct
  13. Hagit Attiya, Leah Epstein, Hadas Shachnai and Tami Tamir,
    “Transactional Contention Management as a Non-Clairvoyant Scheduling Problem”,
    Full version in Algorithmica, Volume 57, Number 1 (May 2010), pp. 44-61. Link to Science Direct
    Previously, an extended abstract in PODC 2006Presentation
  14. Hagit Attiya and Danny Hendler,
    “Time and Space Lower Bounds for Implementations Using k-CAS”,
    IEEE Transactions on Parallel and Distributed Processing, 21(2): 162-173 (2010). link to IEEE DL
    Previously, an extended abstract in DISC 2005. Presentation
  15. Hagit Attiya, Alex Kogan and Jennifer Welch,
    “Efficient and Robust Local Mutual Exclusion in Mobile Ad Hoc Networks”,
    accepted for publication in IEEE transactions on Mobile Computing, Volume 9, Number. 3, pp.361-375 (2010). link to IEEE DL
    Previously, an extended abstract  in ICDCS 2008.
  16. Hagit Attiya, Rachid Guerraoui, Danny Hendler and Petr Kouznetsov,
    “The Complexity of Obstruction-Free Implementations”,
    Journal of the ACM, Volume 56, Issue 4, Article 24, June 2009. link to ACM DL
    (This is the full version of our DISC05 and PODC06 papers.)
  17. Hagit Attiya and Keren Censor,
    “Tight Bounds for Asynchronous Randomized Consensus”,
    Journal of the ACM, Volume 55, Issue 5, Article 20, October 2008. link to ACM DL
    Previously, an extended abstract in STOC 2007slides
  18. H. Attiya and David Hay,
    “Randomization does not Reduce the Average Delay in Parallel Packet Switches”,
    SIAM Journal on Computing, Vol. 37, No. 5, pp. 1613-1636. link to SIAM Online
    Previously, an extended abstract in SPAA 2005.
  19. H. Attiya and A. Bar-Or,
    “Sharing Memory with semi-Byzantine Clients and Faulty Storage Servers,”
    Parallel Processing Letters, Vol. 16, No. 4 (December 2006) 419-428. link to World Scientific
    Previously, an extended abstract in SRDS 2003. Presentation
  20. H. Attiya and David Hay,
    “The Inherent Queuing Delay of Parallel Packet Switches”,
    IEEE Transactions on Parallel and Distributed Systems, Vol. 17, No. 9 (2006) pp.1048-1056. link to IEEE Xplore
    Previously, an extended abstract in IFIP TCS 2004.
  21. Hagit Attiya, Fabian Kuhn, C. Greg Plaxton, Mirjam Wattenhofer, and Roger Wattenhofer.
    “Efficient Adaptive Collect using Randomization”,
    Distributed Computing, Vol. 18, No. 3 (2006), pp. 177-189. link to Springer online
    Previously, an extended abstract in DISC 2004. (Best student paper)
  22. R. Nossenson and H. Attiya,
    “Understanding the Distribution of File Transmission Duration in the Web,”
    International Journal of Communication Systems, Volume 17, Issue 5 (June 2004).
    Previous version in SPECTS 2003. Also poster in WWW 2003.
  23. H. Attiya and Hadas Shachnai,
    “IDA-Based Protocols for Reliable Multicast,”
    Information and Computation, Vol. 190, No. 2 (May 2004), Pages 117-135.
    Previous version in OPODIS 1997.
  24. A. Agbaria, H. Attiya, R. Friedman and R. Vitenberg,
    “Quantifying Rollback Propagation in Distributed Checkpointing,”
    Journal of Parallel and Distributed Computing, Vol. 64, No. 3 (March 2004), Pages 370-384.
    Previous version in SRDS 2001.
  25. H. Attiya and A. Fouren,
    “Algorithms Adapting to Point Contention”,
    Journal of the ACM, Vol. 50, No. 4 (July 2003), pp. 444-468. link to ACM DL
  26. Allon Adir, Hagit Attiya, Gil Shurek,
    “Information-Flow Models for Shared Memory with an Application to the PowerPC Architecture,”
    IEEE Transactions on Parallel and Distributed Systems, Vol. 14, No. 5 (2003), pp. 502-515.
  27. H. Attiya and V. Bortnikov,
    “Adaptive and Efficient Mutual Exclusion,”
    Distributed Computing, Vol. 15, No. 3 (2002), pp. 177-189. ps
    Previous version in PODC2000.
  28. H. Attiya, A. Gorbach and S. Moran,
    “Computing in Totally Anonymous Asynchronous Shared Memory Systems,”
    Information and Computation 173(2): 162-183 (2002)
    Previous version in DISC 1998.
  29. H. Attiya and S. Rajsbaum,
    “The Combinatorial Structure of Wait-Free Solvable Tasks,”
    SIAM Journal on Computing, Vol. 31, No. 4 (2002), pp. 1286-1313. early version
    Conference version, in WDAG 1996.
  30. H. Attiya, A. Fouren and E. Gafni,
    “An Adaptive Collect Algorithm with Applications,”
    Distributed Computing, Vol. 15, No. 2 (2002), pp. 87-96. ps
    Previous version
  31. H. Attiya and E. Dagan,
    “Universal Operations: Unary versus Binary,”
    Journal of the ACM, Vol. 48, No. 5 (September 2001), pp. 1013-1037. ps
    extended abstract in PODC 96.
  32. H. Attiya and A. Fouren,
    “Adaptive and Efficient Wait-Free Algorithms for Lattice Agreement and Renaming,”
    Regular presentation in PODC98 (slides).
    SIAM Journal on Computing, Vol. 31, No. 2 (2001), pp. 642-664. ps
  33. H. Attiya and T. Djerassi-Shintel,
    “Time Bounds for Decision Problems in the Presence of Timing Uncertainties and Failures,”
    Journal on Parallel and Distributed Computing, Vol. 61, No. 8, (August 2001), pp. 1096-1109.  ps
  34. H. Attiya, H. Shachnai and T. Tamir,
    “Local Labeling and Resource Allocation Using Preprocessing,”
    SIAM Journal on Computing, Vol. 28, No. 4 (1999), pp. 1397-1414. ps
  35. H. Attiya,
    “Efficient and Robust Sharing of Memory in Message-Passing Systems,”
    Journal of Algorithms, Vol. 34, No. 1 (January 2000), pp. 109-127.
  36. H. Attiya and O. Rachman,
    “Atomic Snapshots in O(nlogn) Operations,”
    SIAM Journal on Computing, Vol. 27, No. 2 (April 1998), pp. 319-340.
  37. H. Attiya, S. Chaudhuri, R. Friedman and J. L. Welch,
    “Shared Memory Consistency Conditions for Non-Sequential Execution:
    Definitions and Programming Strategies,”
    SIAM Journal on Computing, Vol. 27, No. 1 (February 1998), pp. 65-89.
  38. H. Attiya and R. Rappoport,
    “The Level of Handshake Required for Establishing a Connection,”
    Distributed Computing, Vol. 11, No. 1 (November 1997), pp. 41-57.
  39. R. Alur, H. Attiya and G. Taubenfeld,
    “Time-Adaptive Algorithms for Synchronization,”
    SIAM Journal on Computing, Vol. 26, No. 2 (April 1997), pp. 539–556.
  40. H. Attiya, A. Herzberg and S. Rajsbaum,
    “Clock Synchronization Under Different Delay Assumptions,”
    SIAM Journal on Computing, Vol. 25, No. 2 (April 1996), pp. 369-389.
  41. H. Attiya and R. Friedman,
    “Limitations of Local Consistency Conditions for Distributed Shared Memories,”
    Information Processing Letters, Vol. 57, No. 5, pp. 243–248.
  42. H. Attiya, S. Dolev and J. L. Welch,
    “Connection Management without Retaining Information,”
    Information and Control, Vol. 123, No. 2 (December 1995), pp. 155–171.
  43. E. Aharonson and H. Attiya,
    “Counting Networks with Arbitrary Fan-Out,”
    Distributed Computing, Vol. 8, No. 4, pp. 163–169.
  44. H. Attiya, M. Herlihy and O. Rachman,
    “Atomic Snapshots Using Lattice Agreement,”
    Distributed Computing, Vol. 8, No. 3, pp. 121–132.
  45. H. Attiya, A. Bar-Noy and D. Dolev,
    “Sharing Memory Robustly in Message-Passing Systems,”
    Journal of the ACM, Vol. 42, No. 1 (January 1995), pp. 124–142.
  46. Y. Afek, H. Attiya, A. Fekete, M. J. Fischer, N. Lynch, Y. Mansour, D. Wang and L. D. Zuck,
    “Reliable Communication Over Unreliable Channels,”
    Journal of the ACM, Vol. 41, No. 6 (November 1994), pp. 1267–1297.
  47. H. Attiya and M. Mavronicolas,
    “Efficiency of Semi-Synchronous versus Asynchronous Networks,”
    Mathematical Systems Theory, Vol. 27 (1994), pp. 547–571.
  48. H. Attiya, N. Lynch and N. Shavit,
    “Are Wait-Free Algorithms Fast?”
    Journal of the ACM, Vol. 41, No. 4 (July 1994), pp. 725-763.
  49. H. Attiya and J. L. Welch,
    “Sequential Consistency versus Linearizability,”
    ACM Trans. on Computer Systems, Vol. 12, No. 2, pp. 99–122.
  50. H. Attiya and N. A. Lynch,
    “Time Bounds for Real-Time Process Control in the Presence of Timing Uncertainty,”
    Information and Computation, Vol. 110, No. 1 (April 1994), pp. 183–232.
  51. H. Attiya, C. Dwork, N. A. Lynch and L. J. Stockmeyer,
    “Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty,”
    Journal of the ACM, Vol. 41, No. 1 (January 1994), pp. 122–152.