[ General Information
| Lectures
| Handouts
| Other Pointers
| Requirements
]
[ Announcements
]
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
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.
¶ 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.
Handouts
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
Requirements
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.
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.