Assignment 1

Find a concurrent algorithm in the literature. The algorithm should not be trivial but also not extremely complex (since you are going to implement and verify the algorithm in Assignment 2 and 3). Concurrent algorithms are applicable to various areas including databases, operating systems, etcetera. You are suggested to find a concurrent algorithm in an area of your interest. Preferably, the algorithm should be presented in a refereed journal or fairly recent conference proceedings. If you find a concurrent algorithm to accomplish x and that paper is published in the year y, then you should try to find out if any concurrent algorithms accomplishing x (improving/simplifying/generalizing the former algorithm) have been published after the year y.

Ask the instructor if the algorithm is appropriate. Email the doi of the paper describing the algorithm to the instructor.

Once your paper has been approved by the instructor, add your paper to the list below. Ensure that the reference in complete, that is, make sure that all relevant information is included. Attach a hyperlink to the title of your paper, linking it to the doi (something like http://dx.doi.org/10.1145/769800.769804).

Write a report. In the report, describe your algorithm using pseudocode. If you have found a description of the algorithm in pseudocode in the literature, you may use that description. However, do not forget to mention the source. Also explain the algorithm in your own words. This implies that you do not copy parts of the paper. Feel free to include examples. If the examples are not your own, then mention the source.

You may want to try LaTeX and BiBTeX to write your report. You may start from the files assignment1.tex and assignment1.bib. Skeletons of various types of entries of a BiBTeX file can be found in sample.bib. Numerous tutorials on LaTeX and BiBTeX can be found on the web. If you have any questions, feel free to contact the instructor.

The report should be roughly between 4 and 10 pages. These bounds are not absolute (but one page is definitely not enough and 20 pages is too much).

As the audience of your report, consider your fellow students in the course.

• Hussain Tinwala:
  Michael L. Scott and Maged M. Michael. Non-blocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors. Journal of Parallel and Distributed Computing, 51(1):1–26, May 1998.

• Bart Verzijlenberg:
  Håkan Sundell and Philippas Tsigas. Fast and lock-free concurrent priority queues for multi-thread systems. Journal of Parallel and Distributed Computing, 65(5):609-627, May 2005.

• Slawomir Kmiec:
  Adan Cosgaya-Lozano, Andrew Rau-Chaplin and Norbert Zeh. Parallel Computation of Skyline Queries. In Proceedings of the 21st International Symposium on High Performance Computing Systems and Applications, page 12, Saskatoon, SK, Canada, May 2007. IEEE.

• Shengjun Wang:
  Sascha Hunold, Thomas Rauber and Gudula Runger. Multilevel hierarchical matrix multiplication on clusters. In Proceedings of the 18th annual international conference on Supercomputing, pages 136-145, Saint-Malo, France, June/July 2004. ACM.

• Yi Zheng:
  Jon A. Preston and Sushil K. Prasad. An Efficient Synchronous Collaborative Editing System Employing Dynamic Locking of Varying Granularity in Generalized Document Trees, In Proceedings of the 2nd International Conference on Collaborative Computing: Networking, Applications and Worksharing, pages 1-10, Atlanta, GA, USA, November 2006. IEEE.

• Jing Yang:
  Erion Plaku and Lydia E. Kavraki. Distributed Sampling-Based Roadmap of Trees for Large-Scale Motion Planning. In Proceedings of IEEE International Conference on Robotics and Automation, pages 3868–3873, Barcelona, Spain, April 2005. IEEE.

• Zhenyu Pan:
  Vassos Hadzilacos. A note on group mutual exclusion. In Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, pages 100-106, Newport, Rhode Island, United States, August 2001. ACM

• Sujatha:
  Mikhail Fomitchev and Eric Ruppert.Lock-free linked lists and skip lists. In Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, pages 50-59, St. John's, Newfoundland, Canada, July 2004. ACM.

• Hui Wang:
  G. Dudek, M. Jenkin, E. Milios and D. Wilkes. Topological Exploration with Multiple Robots. In Proceedings of the 7th International Symposium on Robotics with Applications, Anchorage, Alaska, May 1998.

• Marcin Kwietniewski:
  Wei Wu, Wenyuan Guo, Lian-Lee Tan. Distributed Processing of Moving K-Nearest-Neighbor Query on Moving Objects. In Proceedings of IEEE 23rd International Conference on Data Engineering, pages 1116-1125, Istanbul, Turkey, April 2007. IEEE.

• Niloufar Shafiei:
  Maurice Herlihy, Victor Luchangco and Mark Moir. Obstruction-Free Synchronization: Double-Ended Queues as an Example.In Proceedings of the 23rd International Conference on Distributed Computing Systems, pages 522 - 529, Providence, RI, USA, May 2003. IEEE.
  William N. Scherer III and Michael L. Scott. Contention Management in Dynamic Software Transactional Memory. In PODC Workshop on Concurrency and Synchronization in Java Programs, St. John's, Newfoundland, Canada, July 2004.

• Nastaran Shafiei:
  Chien-Hua Shann, Ting-Lu Huang, and Cheng Chen. A practical nonblocking queue algorithm using compare-and-swap. In Proceedings of the Seventh International Conference on Parallel and Distributed Systems, pages 470–475, Iwate, Japan, July 2000. IEEE.

• Mark Shtern:
  Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer and Nir Shavit A Lazy Concurrent List-Based Set Algorithm. In Proceedings of the 9th International Conference On Principles Of Distributed Systems, volume 3974 of Lecture Notes in Computer Science, pages 3-16, Pisa, Italy, December 2005. Springer-Verlag.

• Yi Feng:
  Ori Shalev and Nir Shavit.Split-ordered lists: Lock-free extensible hash tables. Journal of the ACM, 53(3):379-405, May 2006.

• Pourya Jafari:
  Jehoshua Bruck, Ching-Tien Ho, Shlomo Kipnis, Shlomo Kipnis and Derrick Weathersby. Efficient Algorithms for All-to-All Communications in Multiport Message-Passing Systems . IEEE Transactions on Parallel and Distributed Systems, 8(11):1143 - 1156, November 1997.

• Bashir Raeesmohammadian:
  Sung-Chae Lim, Joonseon Ahn and Myoung Ho Kim A Concurrent B-Tree Algorithm Using a Cooperative Locking Protocol. In New Horizons in Information Management, volume 2713 of Lecture Notes in Computer Science, pages 165-??, Springer-Verlag. 2003.