Table of Contents
Assignment 1
Find a concurrent algorithm
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 journal or conference proceedings.
Ask the instructor
Ask the instructor if the paper and algorithm is appropriate. Email the doi of the paper describing the algorithm to the instructor.
Add your paper to the list
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
Write a report. In the introduction of your report, describe why the algorithm is of interest and why it is important. Feel free to use arguments found in the literature, but add proper references. Also briefly discuss related work (published before and after the paper you chose). In the main part of your 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.
Use 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 3 and 8 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.
List your paper
- Franck van Breugel:
Carla Schlatter Ellis. Concurrent Search and Insertion in AVL Trees. IEEE Transactions on Computers, 29(9): 811-817, September 1980. - Natalia Bogdan:
R.V. Nageshwara, V. Kumar. Concurrent Access of Priority Queues. IEEE Transactions on Computers, 37(12): 1657-1665, December 1988. - Liping Han:
Vladimir Lanin and Dennis Shasha. A symmetric concurrent B-tree algorithm. In Proceedings of 1986 ACM Fall Joint Computer Conference, pages 380-389, Dallas, Texas, United States, 1986. IEEE Computer Society Press. - Xuanqing Chu:
Patrick Keane and Mark Moir. A simple local-spin group mutual exclusion algorithm. In Proceedings of the 18th annual ACM Symposium on Principles of Distributed Computing, pages 23-32, Atlanta, Georgia, United States, 1999. ACM.
Srdjan Petrovic. Space-efficient FCFS group mutual exclusion. Information Processing Letters, 95(2): 343-350, July 2005. - Alexandre Walzberg:
Mikhail Fomitchev and Eric Ruppert.Lock-Free Linked Lists and Skip Lists. In Proceedings of the 23rd annual ACM Symposium on Principles of Distributed Computing, pages 50-59, St. Johns, Newfoundland, Canada, July 2004. ACM. - Huxia Shi:
Carla Schlatter Ellis. Concurrency in linear hashing. ACM Transactions on Database Systems, 12(2): 195-217, June 1987. - Miroslaw Kuc:
Piotr Kraj, Ashok Sharma, Nikhil Garge, Robert Podolsky, and Richard A McIndoe. ParaKMeans: Implementation of a parallelized K-means algorithm suitable for general laboratory use. BMC Bioinformatics, 9: 200, April 2008.
Ruoming Jin and Ge Yang. Shared Memory Parallelization of Data Mining Algorithms: Techniques, Programming Interface, and Performance. IEEE Transactions on Knowledge and Data Engineering, 17(1): 71-89, January 2005. - Ulka Thaker:
Anurag Kahol, Sumit Khurana, Sandeep K.S. Gupta, Pradip K. Srimani. Adaptive Distributed Dynamic Channel Allocation for Wireless Networks. Journal of Parallel and Distributed Computing, 16(7): 898-914, July 2001. - Xin Zhang:
Daniel Lehmann and Michael O. Rabin On the advantages of free choice: a symmetric and fully distributed solution to the dining philosophers problem. In Proceedings of the 8th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 133–138, Williamsburg, VI, USA, January 1981. ACM.
I. Rhee, A. Warrier, and L. Xu Randomized dining philosophers to TDMA scheduling in wireless sensor networks. Technical Report TR-2005-20, Computer Science Department, North Carolina State University, Raleigh, NC, USA, 2005.