Concurrent and Distributed Algorithms (Spring'12)

Course description: This course is for students interested in design and analysis of algorithms for concurrent and distributed systems, where multiple entities interact through shared memory or message passing. We will study well-known algorithms, which underlie today's most important distributed storage and concurrent processing applications. We will also discuss methods for systematically developing them and reasoning about them, and implement some of the algorithms. | Course work: Weekly problem-solving exercises in class, a few reading and homework assignments, and a course project where students may implement and experiment with known solutions to known problems, design and implement new solutions to new and old problems, formulate problems in concurrent and distributed applications and develop frameworks for solving them, or take on other tasks that exploit or extend the methods studied. | Prerequisites: a programming language or compiler course, an algorithm course, a database course, and skills for programming in a high-level language such as Java; or permission of the instructor. | Credits: 3.

Instructor: Annie Liu | Email: liu@cs.sunysb.edu | Office: Computer Science 1433 | Phone: 631-632-8463.

Hours: Tue 12:50AM-3:20PM, in Computer Science 2114 | Office hours: Mon 10:45-11:15AM and 1:30-2PM, Tue and Thu 9:30-10AM and 11-11:15AM, email for an appointment, or stop by any time I'm around.

Textbook: There is no required textbook for this course; relevant materials and additional references will be given as the course proceeds. Taking good lecture notes is an important part of the course.

Grading: In-class exercises, reading and homework assignments, and a course project, each worth 20%, 30%, and 50% of the grade, respectively (full scores on exercises for everyone who does them all, whether problems are solved or not:-)). Reduced credit for late submissions, 20% per day.

Course homepage: http://www.cs.sunysb.edu/~liu/csex9x

Note:  Many example problems will be discussed in class, and everyone will be asked to participate in problem solving exercises in class, almost every time (but don't worry---the grading will be on how you came up with solutions or how you tried and failed, not whether you came up with solutions and how fast).

Week 1: Overview: problems, application domains, and challenges. Assignment 1

Week 2: Mutual exclusion in shared-memory systems.

Week 3: Distributed mutual exclusion.

Week 4: Concurrent and distributed programming languages. Assignment 2

Week 5: Leader election.

Week 6: More distributed algorithms.

Week 7: Project plan. Assignment 3

Week 8: Non-blocking queue.

Week 9: More concurrent algorithms.

Week 10: Transaction processing. Project

Week 11: Distributed consensus.

Week 12: Consensus in shared-memory systems.

Week 13: Knowledge and common knowledge.

Week 14: Project presentations.

Questionnaire

Assignment 1: Applications and programs

Assignment 2: Programming exercises

Assignment 3: State of the art

Exercises in class
...

Readings
...

Project report

Project presentation

Interactive Site of This Course, for students in the class

Computer Science Department Windows Computing Facilities

This course is an advanced topics course, for both undergraduate and graduate students, but you do not need to have taken any advanced courses or graduate courses; the most important prerequisites are knowledge of algorithms and data structures, programming skills, and motivation for studying methods for developing correct and efficient algorithms and programs.

You should learn all information on the course homepage. Check the homepage periodically for announcements and other dynamic contents.

Do all course work. The homeworks and projects provide concrete experiences with the basic concepts and methods covered in the lectures.

Academic Integrity: All assignments, quizzes, and exams must be done individually, unless specified otherwise; you may discuss ideas with others and look up references, but you must write up your solutions independently and credit all sources that you used. Any plagiarism or other forms of cheating discovered will have a permanent consequence in your university record.

Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Faculty are required to report any suspected instances of academic dishonesty to the Academic Judiciary. For more comprehensive information on academic integrity, including categories of academic dishonesty, please refer to the academic judiciary website at http://www.stonybrook.edu/uaa/academicjudiciary/

Americans with Disabilities Act: If you have a physical, psychological, medical or learning disability that may impact your course work, please contact Disability Support Services, ECC(Educational Communications Center) Building, Room 128, (631)632-6748. They will determine with you what accommodations, if any, are necessary and appropriate. All information and documentation is confidential.

Critical Incident Management: Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of University Community Standards any disruptive behavior that interrupts their ability to teach, compromises the safety of the learning environment, or inhibits students' ability to learn. Further information about most academic matters can be found in the Undergraduate Bulletin, the Undergraduate Class Schedule, and the Faculty-Employee Handbook.