Hagit Attiya: Publications

(Last updated: September 2011)

• Talks and non-technical writings.
• Papers that did not appear in journals yet.
• References to papers that appeared in journals (since 1994).
• My entry in the DBLP bibliography server is fairly up-to-date.
• A chapter in the Parallel and Distributed Computing Handbook, McGraw-Hill

---

Talks.

1. Sharing memories, robustly. A Prezi presentation upon receiving the Dijkstra award, September 2011. (Needs Adobe Flash.)
2. Inherent limitations can facilitate design and verification of concurrent programs, invited talk at Intel & Technion Symposium, 2011. slides
   Longer version given as HiPEACS seminar, April 2011.
3. The inherent complexity of transactional memory and what to do about it, invited talk at PODC 2010. slides paper (in ACM DL) also in ICDCN 2011 (paper in Springer)
4. Algorithms that Adapt to Contention, in Winter School: Hot Topics in Distributed Computing 2010. slides
5. A World of (Im)Possibilities, a talk (with Jennifer Welch) at the Nancy Lynch Celebration in PODC 2008. slides
6. When parallel met distributed, invited talk in SPAA 2008. slides
7. A mile-high view of concurrent algorithms, in Workshop on the Verification of Concurrent Algorithms (COVA 2008). slides
8. Highly-Concurrent Data Structures, talk in the LADIS 2007 workshop. slides another version from the Multi-Core 2008 seminar at Ben-Gurion University.
9. The Cost of Obstruction-Freedom, talk prepared for a national seminar on distributed computing at Ben-Gurion University. slides
10. Adapting to Point Contention with Long-Lived Safe Agreement, invited talk in SIROCCO 2006. article slides photo
11. Algorithms that Adapt to Contention.  slides
12. The Inherent Queuing Delay of Parallel Packet Switches. slides

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

1. Robust Simulation of Shared Memory: 20 Years After, EATCS Distributed Computing Column, 100, pages 99-113, February 2010.
2. Distributing your data and having it, too, technical perspective for Communications of the ACM, Vol. 51, No. 9, September 2008.
3. 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)², CAV 2008 workshop.
4. Needed: Foundations for Transactional Memory, in ACM SIGACT News Distributed Computing Column, Vol. 39, No. 1, March 2008.
5. Concurrency and the Principle of Data Locality, (local copy) in the Distributed Wisdom column of IEEE DS Online, Vol. 8, No. 9, 2007.

Papers that did not appear in journals yet.

1. Hagit Attiya, Fatemeh Borran, Martin Hutle, Zarko Milosevic and Andre Schiper
   ``Structured Derivation of Semi-Synchronous Algorithm”,
   in DISC 2011.
   
   
2. 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.
   
   
3. Hagit Attiya and Eshcar Hillel,
   ``Single-Version STMs can be Multi-Version Permissive”,
   extended abstract to appear in ICDCN 2011.
   Also, brief announcement in PODC 2010.
   
   
4. Hagit Attiya and Eshcar Hillel,
   ``The Cost of Privatization”,
   extended abstract in DISC 2010.
   Technical Report CS-2010-11, Department of Computer Science, Technion. slides
   
   
5. Hagit Attiya, Vincent Gramoli and Alessia Milani,
   ``A Provably Starvation-Free Distributed Directory Protocol”,
   extended abstract in SSS 2010.
   
   
6. 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.
   
   
7. Hagit Attiya, G. Ramalingam and Noam Rinetzky,
   ``Sequential Verification of Serializability”,
   extended abstract to appear in POPL 2010. TR slides
   
   
8. Hagit Attiya and Alessia Milani,
   ``Transactional Scheduling for Read-Dominated Workloads”,
   extended abstract in OPODIS 2009. (Best paper award)
   
   
9. James Aspnes, Hagit Attiya and Keren Censor,
   ``Max Registers, Counters, and Monotone Circuits”,
   extended abstract in PODC 2009. (Best student paper)
   
   
10. James Aspnes, Hagit Attiya and Keren Censor,
    ``Randomized Consensus with O(n log n) Individual Work”,
    extended abstract in PODC 2008.
    
    
11. Hagit Attiya, Rachid Guerraoui and Eric Ruppert,
    ``Partial Snapshot Objects”,
    extended abstract in SPAA 2008. slides
    
    
12. Hagit Attiya, Danny Hendler and Philipp Woelfel,
    ``Tight RMR Lower Bounds for Mutual Exclusion and Other Problems”,
    extended abstract in STOC 2008.
    
    
13. Hagit Attiya and Eshcar Hillel,
    ``Built-in Coloring for Highly-Concurrent Doubly-Linked Lists”,
    extended abstract in DISC 2006. presentation (Full version in PDF and in ps.)
    
    
14. Hagit Attiya, Rachid Guerraoui, Danny Hendler and Petr Kouznetsov,
    ``Synchronizing without Locks is Inherently Expensive”,
    extended abstract in PODC 2006.
    
    
15. Hagit Attiya, David Hay and Jennifer L. Welch,
    ``Optimal Clock Synchronization under Energy Constraints in Wireless Ad-Hoc Networks”,
    extended abstract in OPODIS 2005.
    
    
16. 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).
    
    
17. R. Nossenson and H. Attiya,
    "The N-Burst/G/1 model with heavy-tailed service-times distribution",
    extended abstract in MASCOTS 2004.
    
18. H. Attiya, F. Fich and Y. Kaplan,
    "Lower Bounds for Adaptive Collect and Related Problems",
    extended abstract in PODC 2004. Presentation
    
19. R. Nossenson and H. Attiya,
    "Evaluating Self-Similar Processes for Modeling Web Servers",
    extended abstract in SPECTS 2004.
    
20. H. Attiya and Idan Zach,
    "Incremental Calculation for Fully-Adaptive Algorithms, "
    Brief announcement in DISC 2004 (presentation).
    unpublished manuscript.
    
21. Hagit Attiya, Arie Fouren and Eli Gafni,
    "A Polynomial Adaptive Algorithm for Long-Lived (2k-1)-Renaming",
    full version submitted for publication.
    
22. H. Attiya and Z. Avidor, 
    "Wait-Free n-set Consensus when Inputs are Restricted", 
    extended abstract in DISC 2002. 
23. H. Attiya and A. Fouren,
    ``Polynomial and Adaptive Long-lived (2k-1)-Renaming,''
    Extended abstract in DISC 2000. (Best student paper) 
    
24. Y. Afek, H. Attiya, A. Fouren, G. Stupp and D. Touitou.
    ``Adaptive Long-Lived Renaming using Bounded Memory,''
    manuscript.
    
25. Y. Afek, H. Attiya, A. Fouren, G. Stupp and D. Touitou.
    ``Long-Lived Renaming Made Adaptive,''
    Regular presentation in PODC99.
    
26. 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.
    
27. J. Kleinberg, H. Attiya and N. A. Lynch,
    ``Trade-Offs Between Message Delivery and Quiesce Times in Connection Management Protocols,''
    ISTCS 1995. ps
    
28. 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.

1. Hagit Attiya, Faith Ellen and Panagiota Fatourou,
   ``The Complexity of Updating Multi-Writer Snapshot Objects”,
   full version to appear in Journal on Parallel and Distributed Computing. Link to Science Direct
   Previously, an extended abstract in ICDCN 2006.
   
   
2. 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.
   
   
3. 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.
   
   
4. 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.
   
   
5. 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.
   
   
6. 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
   
   
7. 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 2006. Presentation
   
8. 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
   
   
9. 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.
   
   
10. 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.)
    
    
11. 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 2007. slides
    
    
12. 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.
    
    
13. 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
    
    
14. 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.
    
15. 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)
    
    
16. 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.
    
    
17. 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.
    
    
18. 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.
    
19. 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
    
20. 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.
    
21. 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.
    
22. 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.
    
23. 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.
    
24. 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
    
25. 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.
    
26. 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
    
27. 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
    
28. 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
    
29. H. Attiya,
    ``Efficient and Robust Sharing of Memory in Message-Passing Systems,''
    Journal of Algorithms, Vol. 34, No. 1 (January 2000), pp. 109-127.
    
30. H. Attiya and O. Rachman,
    ``Atomic Snapshots in O(nlogn) Operations,''
    SIAM Journal on Computing, Vol. 27, No. 2 (April 1998), pp. 319-340.
    
31. 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.
    
32. 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.
    
33. 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.
    
34. 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.
    
35. H. Attiya and R. Friedman,
    ``Limitations of Local Consistency Conditions for Distributed Shared Memories,''
    Information Processing Letters, Vol. 57, No. 5, pp. 243--248.
    
36. 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.
    
37. E. Aharonson and H. Attiya,
    ``Counting Networks with Arbitrary Fan-Out,''
    Distributed Computing, Vol. 8, No. 4, pp. 163--169.
    
38. H. Attiya, M. Herlihy and O. Rachman,
    ``Atomic Snapshots Using Lattice Agreement,''
    Distributed Computing, Vol. 8, No. 3, pp. 121--132.
    
39. 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.
    
40. 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.
    
41. H. Attiya and M. Mavronicolas,
    ``Efficiency of Semi-Synchronous versus Asynchronous Networks,''
    Mathematical Systems Theory, Vol. 27 (1994), pp. 547--571.
    
42. 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.
    
43. H. Attiya and J. L. Welch,
    ``Sequential Consistency versus Linearizability,''
    ACM Trans. on Computer Systems, Vol. 12, No. 2, pp. 99--122.
    
44. 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.
    
45. 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.

---