Hagit Attiya: Publications

(Last updated: August 2012)

• 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 and Ami Paz.
   Counting-Based Impossibility Proofs for Renaming and Set Agreement
   extended abstract to appear in DISC 2012. Ami's presentation
   
   
2. James Aspnes, Hagit Attiya, Keren Censor-Hillel and Faith Ellen.
   ``Faster than Optimal Snapshots (for a While) ”,
   extended abstract in PODC 2012.
   
   
3. James Aspnes, Hagit Attiya, Keren Censor-Hillel and Danny Hendler.
   ``Lower Bounds for Restricted-Use Objects”,
   extended abstract in SPAA 2012.
   
   
4. Dan Alistarh, Hagit Attiya, Rachid Guerraoui, Corentin Travers,
   ``Early Deciding Synchronous Renaming in O(log f) Rounds or Less”,
   extended abstract in SIROCCO 2012.
   
   
5. Hagit Attiya and Armando Castañeda,
   ``A Non-topological Proof for the Impossibility of k-Set Agreement.
   extended abstract in SSS 2011.
   
   
6. Hagit Attiya, Fatemeh Borran, Martin Hutle, Zarko Milosevic and Andre Schiper
   ``Structured Derivation of Semi-Synchronous Algorithm”,
   extended abstract in DISC 2011.
   
   
7. 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.
   
   
8. Hagit Attiya, Vincent Gramoli and Alessia Milani,
   ``A Provably Starvation-Free Distributed Directory Protocol”,
   extended abstract in SSS 2010.
   
   
9. 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.
   
   
10. Hagit Attiya, G. Ramalingam and Noam Rinetzky,
    ``Sequential Verification of Serializability”,
    extended abstract to appear in POPL 2010. TR slides
    
    
11. James Aspnes, Hagit Attiya and Keren Censor,
    ``Randomized Consensus with O(n log n) Individual Work”,
    extended abstract in PODC 2008.
    
    
12. Hagit Attiya, Rachid Guerraoui and Eric Ruppert,
    ``Partial Snapshot Objects”,
    extended abstract in SPAA 2008. slides
    
    
13. Hagit Attiya, Danny Hendler and Philipp Woelfel,
    ``Tight RMR Lower Bounds for Mutual Exclusion and Other Problems”,
    extended abstract in STOC 2008.
    
    
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 award) 
    
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 and Eshcar Hillel,
   ``Built-in Coloring for Highly-Concurrent Doubly-Linked Lists”,
   to appear in Theory of Computing Systems. Springer link local copy
   Previously, an extended abstract in DISC 2006. presentation
   
   
2. Hagit Attiya and Eshcar Hillel,
   ``The Cost of Privatization”,
   to appear in IEEE Transactions on Computers. local copy
   Previously, an extended abstract in DISC 2010. slides
   
   
3. 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)
   
   
4. 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.
   
   
5. James Aspnes, Hagit Attiya and Keren Censor,
   ``Max Registers, Counters, and 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. (Best student paper award)
   
   
6. 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.
   
   
7. 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.
   
   
8. 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.
   
   
9. 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.
   
   
10. 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.
    
    
11. 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
    
    
12. 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
    
13. 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
    
    
14. 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.
    
    
15. 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.)
    
    
16. 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
    
    
17. 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.
    
    
18. 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
    
    
19. 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.
    
20. 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)
    
    
21. 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.
    
    
22. 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.
    
    
23. 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.
    
24. 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
    
25. 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.
    
26. 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.
    
27. 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.
    
28. 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.
    
29. 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
    
30. 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.
    
31. 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
    
32. 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
    
33. 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
    
34. H. Attiya,
    ``Efficient and Robust Sharing of Memory in Message-Passing Systems,''
    Journal of Algorithms, Vol. 34, No. 1 (January 2000), pp. 109-127.
    
35. H. Attiya and O. Rachman,
    ``Atomic Snapshots in O(nlogn) Operations,''
    SIAM Journal on Computing, Vol. 27, No. 2 (April 1998), pp. 319-340.
    
36. 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.
    
37. 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.
    
38. 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.
    
39. 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.
    
40. H. Attiya and R. Friedman,
    ``Limitations of Local Consistency Conditions for Distributed Shared Memories,''
    Information Processing Letters, Vol. 57, No. 5, pp. 243--248.
    
41. 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.
    
42. E. Aharonson and H. Attiya,
    ``Counting Networks with Arbitrary Fan-Out,''
    Distributed Computing, Vol. 8, No. 4, pp. 163--169.
    
43. H. Attiya, M. Herlihy and O. Rachman,
    ``Atomic Snapshots Using Lattice Agreement,''
    Distributed Computing, Vol. 8, No. 3, pp. 121--132.
    
44. 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.
    
45. 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.
    
46. H. Attiya and M. Mavronicolas,
    ``Efficiency of Semi-Synchronous versus Asynchronous Networks,''
    Mathematical Systems Theory, Vol. 27 (1994), pp. 547--571.
    
47. 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.
    
48. H. Attiya and J. L. Welch,
    ``Sequential Consistency versus Linearizability,''
    ACM Trans. on Computer Systems, Vol. 12, No. 2, pp. 99--122.
    
49. 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.
    
50. 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.

---