Seminar in Computer Science 236806 (Winter 98/99)
Recent research in Distributed Computing

  Material in this page may change.
 

Instructor: Hagit Attiya
Time: Thursday 10:30-12:30
Place: Fishbach 461
homepage: http://www.cs.technion.ac.il/~hagit/seminar98/
 

Suggested topics:

I have copies of most papers mentioned in the list.  In many cases, updated versions can be found through the authors' home pages.

  1. Impacts of contention on locking:   (Slides by Shiri Manor.)
      2.  
      Thomas E. Anderson.
      The performance of spin lock alternatives for shared-memory multiprocessors.
      IEEE Transactions on Parallel and Distributed Systems, 1(1):6-16, January 1990.

      Gary Graunke and Shreekant Thakkar.
      Synchronization algorithms for shared-memory multiprocessors.
      IEEE Computer, 23(6):60-69, June 1990.

      Larry Rudolph and Zary Segall.
      Dynamic decentralized cache schemes for MIMD parallel processors.
      In Proceedings of the 11th Annual International Symposium on Computer Architecture,
      pages 340-347, 1984.
       

  2. Theory of contention (two lectures): 
      3.  
      Cynthia Dwork, Maurice Herlihy, and Orli Waarts.
      Contention in shared memory systems.
      Journal of the ACM, 44(6):779-805, November 1997.

      P. B. Gibbons, Y. Matias, and V. Ramachandran.
      The QRQW PRAM: Accounting for contention in parallel algorithms.
      In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms,
      pages 638-648, 1994.

      P. B. Gibbons, Y. Matias, and V. Ramachandran.
      The queue-read queue-write asynchronous PRAM model.
      Theoretical Computer Science, 196(1-2):3-29, April 1998.
       

  3. Impact of memory locality:

    4.  
      Travis Craig. Building fifo and priority queuing spin locks from atomic swap.
      Technical Report 93-02-02, Department of CSE, University of Washington,
      Seattle, February 1993.

      John M. Mellor-Crummey and Michael L. Scott.
      Algorithms for scalable synchronization on shared-memory multiprocessors.
      ACM Transactions on Computer Systems, 9(1):21-65, February 1991.
       

  4. Theory of memory locality (possibly two lectures):
      5.  
      James H. Anderson and J.-H. Yang.
      Time/contention tradeoffs for multiprocessor synchronization.
      Information and Computation, 124(1):68-84, January 1996.

      Robert Cypher. The communication requirements of mutual exclusion.
      In Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 147-156, 1995.
       

  5. Fast mutual exclusion:   (Slides+additional material by Avi Rubenbach and Shahar Beiser.)
      6.  
      Leslie Lamport.  A fast mutual exclusion algorithm.
      ACM Transactions on Computer Systems, 5(1):1-11, February 1987.

      Jae-Heon Yang and James H. Anderson.
      A fast, scalable mutual exclusion algorithm.
      Distributed Computing, 9(1):51-60, August 1995.

      Manhoi Choy and Ambuj K. Singh.
      Adaptive solutions to the mutual exclusion problem.
      Distributed Computing, 8(1):1-17, August 1994.

         
  6. Adapting to concurrency (two lectures):   (Slides by Vita Bortnikov for the first two papers.)
      Mark Moir.
      Fast, long-lived renaming improved and simplified.
      Science of Computer Programming, 30(3):287-308, May 1998.

      Mark Moir and James H. Anderson.
      Wait-free algorithms for fast, long-lived renaming.
      Science of Computer Programming, 25(1):1-39, October 1995.

         
      Yehuda Afek, Dalia Dauber, and Dan Touitou.
      Wait-free made fast.
      In Proceedings of the 27th ACM Symposium on Theory of Computing,
      pages 538-547, 1995.

      H. Attiya and A. Fouren.
      Adaptive Wait-Free Algorithms for Lattice Agreement and Renaming.
      In Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing,
      pages 277-286, 1998.
       

  1. Non-blocking implementations of concurrent objects:   (Slides by Ilan Goldfeld.)
      2.  
      Nir Shavit and Dan Touitou.
      Software Transactional Memory.
      Distributed Computing, 10(2):99-116, February 1997.

      Greg Barnes.
      A Method for Implementing Lock-Free Data Structures.
      In Proceedings of the Annual ACM symposium on Parallel Algorithms and Architectures, pages 261-270, 1993.

      John Turek and Dennis Shasha and Sundeep Prakash.
      Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking.
      In Proceedings of the Annaul ACM symposium on Priciples of Database Systems, pages 212-222, 1992.
       

  2. Refined implementations of universal operations (one or two lectures):
      3.  
      Amos Israeli and Lihu Rappoport.  Disjoin-access-parallel implementations of strong shared memory primitives.  In Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, pages 151-160, 1994.

      Hagit Attiya and Eyal Dagan.  Universal operations: Unary versus binary.  In Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing, pages 223-232, 1996.

      Yehuda Afek, Michael Merritt, Gadi Taubenfeld, and Dan Touitou.  Disentangling multi-object operations.  In Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, pages 111-120, 1997.
       

  3. Exploiting scheduling policies: 
      4.  
      James H. Anderson, S. Ramamurthy, Mark Moir, and K. Jeffay.  Lock-free transactions for real-time systems. In A. Bestavros, K.J. Lin, and S. H. Son, editors, Real-Time Database Systems: Issues and Applications, pages 215-234. Kluwer Academic Publishers, Norwell, Massachusetts, May 1997.

      James H. Anderson, S. Ramamurthy, and K. Jeffay, Real-Time Computing with Lock-Free Shared Objects, ACM Transactions on Computer Systems, 15(2):134-165, May 1997.

      James H. Anderson, R. Jain, and D. Ott.  Wait-Free Synchronization in Quantum-Based Multiprogrammed Systems.  In Proceedings of the 12th International Symposium on Distributed Computing, pp. 34-48, September 1998. Longer version available from the first author's homepage.
       

  4. Counting networks, diffracting trees and all that jazz (at least two lectures, there are many more papers on this topic):
      5.  
      James Aspnes, Maurice Herlihy, and Nir Shavit.
      Counting Networks,
      Journal of the ACM, 41(5):1020-1048, September 1994.

      Maurice Herlihy, Beng-Hong Lim and Nir Shavit.
      Scalable concurrent counting.
      ACM Transactions on Computer Systems, 13(4), pp 343-364, November 1995.

      Nir Shavit and Asaph Zemach.
      Diffracting Trees.
      ACM Transactions on Computer Systems, 14(4), pp. 385-428, Nov 1996.

      Nir Shavit, Eli Upfal and Asaph Zemach.
      A Steady State Analysis of Diffracting Trees.
      Journal of Theory of Computing Systems, 1997.

      Nir Shavit and Asaph Zemach.
      Combining Funnels.
      In Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing,
      pages 61-70 , 1998.
       

  5. Topological tools for understanding distributed computing (two lectures):    (Slides by Shai Rubin and Guy Ray on the last paper)
      6.  
      Ofer Biran, Shlomo Moran and Shmuel Zaks.
      A Combinatorial Characterization of the Distributed 1-Solvable Tasks.
      Journal of Algorithms, 11(3):420-440, September 1990.

      Hagit Attiya. A Direct Proof of the Asynchronous Lower Bound for k-Set Consensus.
      Technical Report 0930, Department of Computer Science, Technion.

      Maurice Herlihy and Nir Shavit.  The Topological Structure of Asynchronous Computability.
      Brown TR CS-96-03, 1996.

      Hagit Attiya and Sergio Rajsbaum.
      The Combinatorial Structure of Wait-Free Solvable Tasks.
      In WDAG 1996.

Additional ideas can be found here (consult with me before choosing one of these topics).

Background material:

The following books can help if you didn't take the course on Distributed Algorithms.

  1. Hagit Attiya and Jennifer Welch, Distributed Computing: Fundamentals, Simulations, and Advanced Topics, McGraw-Hill, 1998.
  1. Nancy Lynch, Distributed Algorithms, Morgan Kaufmann, 1996.
The following papers are useful as background for many of the theoretical papers listed above.
  1. Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, and Rudiger Reischuk.  Renaming in an asynchronous environment. Journal of the ACM, 37(3):524-548, July 1990.
  1. Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson.  Impossibility of distributed consensus with one faulty processor. Journal of the ACM, 32(2):374-382, April 1985.
  1. Maurice Herlihy.  Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124-149, January 1991.