Course outline: COMP3152/COMP9152 Comparative Concurrency Semantics (Session 1, 2008)
Instructors: Prof. Ron van der Meyden
Prerequisites: The
official prerequisites are COMP2011 or COMP2711 or COMP291.
However, prior exposure to concurrent systems and/or
logic will enhance your appreciation of the material.
Credit value, Mode of Instruction: 6UOC, 3L
Text: Reasoning about Knowledge,
Ronald Fagin, Joseph Y. Halpern, Yoram Moses and Moshe Y. Vardi,
plus selected readings from the literature.
Course Aims
This edition of the course will focus on reasoning about
knowledge, a branch of modal logic for concurrent systems.
It aims to give students an introduction to this area
and a working facility with its basic concepts.
The idea
that system components have states of "knowledge" is ubiquitous in
informal discussions of distributed algorithms, robotics, multi-agent
systems and reasoning about computer security. The modal logic of knowledge is an
approach to making such intuitions mathematically precise, so that
they form the basis for rigorous reasoning about such systems.
Of particular interest is the question of how knowledge changes over time, as information is
communicated in the system. That this is a subtle matter is well-known to
players of card games...
The course will be of interest to students
wishing to study distributed computing,
artificial intelligence or computer security.
Student Learning outcomes
At the end of the course you will have a good understanding of how
logical tools may be applied to the study of information flow in
concurrent and multi-agent systems. The course contributes in particular to the
following UNSW graduate attributes:
- an in-depth engagement with the relevant disciplinary
knowledge in its interdisciplinary context
- the capacity for analytical and critical thinking and for
creative problem-solving
- the ability to engage in independent and reflective learning
- the skills required for collaborative and multidisciplinary work
The course contents represent an interdiscplinary area of knowledge, drawing on
computer science, philosophical logic and economics. Homework
will develop analytical reasoning and problem solving skills.
Topics covered
- Semantic modelling of distributed/multi-agent systems
- Knowledge, common knowledge, distributed knowledge
- Linear and branching time temporal logic
- Logics of knowledge and time: completeness, complexity and model checking
- Knowledge-based programs
- Applications to distributed algorithms: agreement and concensus
algorithms
- Applications to computer security. Security protocols (BAN logic) and
noninterference.
- The logic of knowledge and probability
- Connections to economics: epistemic game theory
The area of the course is one that is being actively pursued in research
at UNSW --- see (R. van
der Meyden, publications by area) and (The MCK model checker) --- and
the course will open up opportunities for honours and postgraduate
research projects in the area.
Assessment:
Written Homework, due weeks 2,4,6,8,10,12.
Final grade to be computed from best 5/6 homeworks, each worth 20% of the final grade.
Academic Honesty and Plagiarism
Assignment solutions submitted must be your own work.
Students are reminded that they are bound by the
CSE Yellow form
policies concerning plagiarism, special consideration and supplementary assessment.
Course Schedule & Resources for Students
See schedule of lectures and
recommended reading.
Course Evaluation and Development
Student survey results collected at the end of this course
will be taken into consideration for future editions.