CSE592 (Spring'09)
Protocol Design and Analysis

[ General Information | Lectures | Handouts | Other Pointers | Requirements ]
[ Announcements ]

General Information

Course description: This course is for students interested in design and analysis of algorithms for solving problems in multi-agent applications, including concurrent and distributed applications and multi-player games. We refer to such algorithms as "protocols". In addition to learning about the algorithms, we will aim to study methods for systematically developing them, similar to methods for developing efficient algorithms for single-agent applications. We will also learn about methods for reasoning about knowledge and uncertainty in multi-agent environments. | Course work: Weekly problem-solving exercises in class, several reading 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 multi-agent applications and develop frameworks for solving them, or take on other tasks that exploit or extend the methods studied. Grading will emphasize explanations of how problems and solutions come up, not just what problems and solutions are. | 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: 632-8463.

Hours: Wed 10:30AM-12:50PM, in Computer Science 1441 | Office hours: Tue 9:50-11:20AM, Fri 3:30-5:00PM, after class, by appointment (send email), or stop by any time I'm around.

Textbook: There is no textbook for the 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, assigned readings, and a course project, each worth 20%, 40%, and 40% of the grade, respectively (full scores on exercises and readings for any one who does them all, whether problems are solved or not:-)). Homework is always due in class the following Wednesday. Reduced credit for late submissions, 20% per day.

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

Lectures Outline

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).

¶  We will start with an overview of problems and challenges from applications, as well as frameworks and methods for solutions. We will also look at specific applications, role-based access control and trust management, and discuss powerful languages, Python with multi-threading, and Erlang message passing for concurrent and distributed programming.

¶  We will study mutual exclusion as the first example problem, because it is the most studied and most fundamental problem. We will discuss best algorithms (and why they are best and how they could be designed systematically), in both shared memory and message passing frameworks (though more the former traditionally), including a more recent result where hundreds of new algorithms were automatically generated.

¶  We will then study algorithms in two categories.

  • The first category consists of algorithms for problems that inherently require the use of the message passing paradigm, such as algorithms for the well-known leader election problem and various distributed algorithms.

  • The second category consists of algorithms for problems that inherently require the use of the shared memory paradigm, such as non-blocking algorithms for synchronized queues and various concurrent data structures.

    ¶  We will study consensus as the last example problem, because it is the most fundamental problem in multi-agent systems where failures or arbitrary attacks may occur. We will again discuss algorithms in both shared memory and message passing frameworks (though more the latter traditionally), including important impossibility results.

    ¶  We will finally study logics and methods for reasoning about knowledge and common knowledge, as well as uncertainty, in multi-agent systems, using a number of logic problems and puzzles as examples.


    Handout Q: Questionnaire

    ANSI Standard for Role-Based Access Control, ANSI INCITS 359-2004, 2004.

    Making Specifications Simpler and Clearer: A Case Study of Role-Based Access Control, by Y.A. Liu and S.D. Stoller. (This is a slightly revised version of Role-Based Access Control: A Corrected and Simplified Specification, In Department of Defense Sponsored Information Security Research: New Methods for Protecting Against Cyber Threats, pages 425-439, John Wiley & Sons, 2007.)

    Other Pointers

    Core RBAC executable specification in Python

    Python (Documentation: Tutorial, Standard Library, Language Reference)
    Python 2.6 Quick Reference

    Python multi-threading
    Erlang message passing

    Slides on mutual exclusion using atomic registers, chapter on basic topics by Taubenfeld


    This course is officially an advanced graduate level course, but you do not need to have taken other graduate-level courses; the most important prerequisites are programming skills, knowledge of algorithms and data structures, and motivation for studying a systematic method for developing correct and efficient algorithms and programs.

    You should learn all information on the course homepage. Check the homepage periodically for Announcements.

    Do all course work. The homeworks and projects are integral parts of the course as they provide concrete experiences with the basic concepts and methods covered in the class.

    Your handins, whether on paper or in electronic form, should include the following information at the top: your name, student id, course number, assignment number, and due date.

    Your work should be submitted in a neat and organized fashion; for handins on papers, if your handwriting is hard to read, then your work needs to be typed.

    Your approach to solving problems is as important as your final solutions; you need to show how you arrived at your solutions and include appropriate explanations.

    If you feel your grade was assigned incorrectly, please bring it up no later than two weeks after the assignment was returned to the class.

    Academic honesty: Homeworks and projects must be done individually, unless specified otherwise; you may discuss 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. For more comprehensive information on academic integrity, please refer to the academic judiciary website at http://www.stonybrook.edu/uaa/academicjudiciary/

    Disability: If you have a physical, psychological, medical or learning disability that may have an impact on your ability to carry out assigned course work, please contact the staff in the Disabled Student Services office (DSS), Room 133 Humanities, 632-6748/TDD. DSS will review your concerns and determine with you what accommodations are necessary and appropriate. All information and documentation of disability are confidential.

    Annie Liu