I have copies of most papers mentioned in the list. In many cases, updated versions can be found through the authors’ home pages.
-
Impacts of contention on locking: (Slides by Shiri Manor.)
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. -
Theory of contention (two lectures):
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. -
Exploiting scheduling policies:
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.
-
Counting networks, diffracting trees and all that jazz (at least two lectures, there are many more papers on this topic):
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. -
Topological tools for understanding distributed computing (two lectures):
(Slides by Shai Rubin and Guy Ray on the last paper)
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.
- Hagit Attiya and Jennifer Welch, Distributed Computing: Fundamentals, Simulations, and Advanced Topics, McGraw-Hill, 1998.
- Nancy Lynch, Distributed Algorithms, Morgan Kaufmann, 1996.
The following papers are useful as background for many of the theoretical papers listed above.
- 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.
- 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.
- Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124-149, January 1991.