Skip to navigation | Skip to main content | Skip to footer
Menu
Menu

This is an archived syllabus from 2015-2016

COMP31212 Concurrency and Process Algebra syllabus 2015-2016

COMP31212 Concurrency and Process Algebra

Level 3
Credits: 10
Enrolled students: 61

Course lecturer: David Rydeheard


Additional staff: view all staff

Requisites

  • Pre-Requisite (Compulsory): COMP11111
  • Pre-Requisite (Compulsory): COMP11120
  • Pre-Requisite (Compulsory): MATH10111
  • Pre-Requisite (Compulsory): MATH10131
  • Pre-Requisite (Compulsory): MATH10212
  • Pre-Requisite (Compulsory): MATH10232
  • Pre-Requisite (Compulsory): MATH10662
  • Pre-Requisite (Compulsory): MATH10672

Additional requirements

  • Students who are not from the School of Computer Science must have permission from both Computer Science and their home School to enrol.

    Pre-requisites

    To enrol students are required to have taken one of the following:  COMP11120, COMP11111, MATH10111, MATH10131, MATH10212, MATH10232,  MATH10662, MATH10672.

Assessment methods

  • 100% Written exam
Timetable
SemesterEventLocationDayTimeGroup
Sem 2 Lecture 1.5 Fri 10:00 - 11:00 -
Sem 2 Lecture LF15 Mon 10:00 - 11:00 -
Themes to which this unit belongs
  • Rigorous Development

Overview

Concurrent or parallel execution of multiple programs holds out considerable potential in developing high-performance systems. However, developing correct concurrent programs, and subsequent testing, is extremely difficult as the interaction of programs brings new phenomena which are difficult to detect and analyse. This is a practical course in which we introduce a process algebraic modelling of concurrent systems and techniques for analysing correctness. An implementation is provided which allows us to prototype systems, and techniques for developing concurrent Java programs from the models are presented.

Aims

This course will provide a systematic treatment of concepts and issues in concurrency. The subject will be introduced via a small process algebra language, FSP, for specifying the concurrent behaviour of finite state processes. The Java language has built-in concurrency constructs and will be used to illustrate implementations of example specifications. Also the FSP language comes with software tools for animation and verification and these will be used in examples.

A wide variety of common concurrency problems will be investigated. Some of the underlying theory of the process algebra FSP and related algebras such as Milner's CCS and Hoare's CSP will be studied.

The course aims to:

  • Provide students with an understanding of concurrent systems, in particular how to model them using the process algebra FSP and how to implement them using Java.
  • Study techniques for the analysis of concurrent systems.
  • Introduce, via a set of case-studies, typical methods for solving concurrency problems.
  • Allow students to use a suite of tools for analysing FSP systems.

Syllabus

Introduction

Problems and challenges in concurrency (1 lecture).

Modelling processes and concurrency using FSP

Communicating processes, labelled transition systems (2 lectures).

Concurrency in Java

Threads, constructs, behaviour, interacting multiple threads (3 lectures).

From specification to implementation

Translating FSP to Java (1 lecture).

FSP

Semantics and equivalence (3 lectures).

Mutual exclusion, monitors, semaphores (3 lectures)

Properties

Deadlock, safety, liveness, fairness (4 lectures).

Applications

Readers/writers, message-passing, termination (4 lectures).

Extending the model

Other process algebras (CSP, CSS) (1 lecture).

Exercises/revision (2 lectures)

Teaching methods

Lectures

22, including exercise sessions

Feedback methods

Exercises are provided during the course with the opportunity for feedback on solutions, revision sessions are held and exam feedback is provided.

Study hours

  • Assessment written exam (2 hours)
  • Lectures (24 hours)

Employability skills

  • Analytical skills
  • Innovation/creativity
  • Problem solving

Learning outcomes

Programme outcomeUnit learning outcomesAssessment
A1 D6Have a knowledge and understanding, both practical and theoretical, of the FSP Process Algebra.
  • Examination
Have a knowledge and understanding of the difficulties involved in designing and implementing concurrent systems, and the limitations of the FSP modelling approach.
  • Examination
A2Have a knowledge and understanding of the behaviour of concurrent Java programs.
  • Examination
A5 B3Have a knowledge and understanding of solutions to a range of concurrency problems and be able to evaluate the effectiveness of these.
  • Examination
B1Be able to construct models for concurrent systems using FSP.
  • Examination
B1Be able to reason about FSP systems, including analysis of their behaviour, properties and equivalencies.
  • Examination
Understand how to use Java concurrency primitives.
  • Examination
C5Be able to translate FSP models to Java implementations for small problems.
  • Examination

Reading list

TitleAuthorISBNPublisherYearCore
Concurrency: state models and Java programs (2nd edition)Magee, Jeff and Jeff Kramer9780470093559Wiley2006

Additional notes

Course unit materials

Links to course unit teaching materials can be found on the School of Computer Science website for current students.