Lecturer	Gavin Lowe
Degrees	Schedule S1(3rd years) — Computer Science Schedule B1 — Computer Science Schedule B1(M&CS) — Mathematics and Computer Science Schedule A — MSc in Advanced Computer Science
Term	Hilary Term 2010  (16 lectures)

Overview

Many challenges arise during the design and implementation of concurrent and distributed programs. The aim of this course is to understand those challenges, and to see techniques for tackling them. The main paradigm to be considered is message passing concurrency, where independent processes, with private variables, interact by passing messages.

Learning outcomes

At the end of the course students are expected to understand:

• The conceptual foundations of concurrent programming, and
• A variety of effective ways of structuring concurrent and distributed programs.

Prerequisites

Students should have an understanding of CSP, e.g. as taught in the Concurrency course. Students should also have a good understanding of Object Oriented Programming, e.g. as taught in the Michaelmas Term OOP course. Students who have learnt either CSP or OOP elsewhere should discuss their experience with the lecturer before taking this course.

The course will have a number of practicals, to allow students to gain experience with concurrent programming. These practicals will use Scala; background reading on the language will be suggested.

Synopsis

• Introduction: reasons for concurrency; processes, threads; concurrent architectures; concurrent computing paradigms; safety and liveness; challenges of concurrent computing.
• Message passing concurrency; deadlock; piplines; fine-grained concurrency.
• Example: numerical integration using workers and a controller; bag of tasks.
• Alternation: syntax, semantics, examples.
• Client-server architectures.
• Interacting peers: patterns of interaction: centralised, fully-connected, ring and tree topologies.
• Synchronous data parallel computation.
• Monitors: syntax and semantics; examples.
• Patterns of concurrent computation: recursive parallel, bag of tasks with replacement, competition parallel, task parallel, map/reduce, revision of other patterns.
• Semaphores: syntax and semantic; examples; passing the baton.

Syllabus

Reasons for concurrency; processes, threads; concurrent architectures; safety and liveness. Message passing concurrency; deadlock. Clients and servers. Interacting peers.  Synchronous parallel computation.  Patterns of concurrent programming: data parallel; bag of tasks; recursive parallel; task parallel.  Low-level concurrency controls: monitors; semaphores.

 

Reading list

• Course textbook: Foundations of Multithreaded, Parallel, and Distributed Programming, Gregory R. Andrews, Addison-Wesley, 2000.
• Essential background reading:
  • A Brief Scala tutorial, http://www.scala-lang.org/sites/default/files/linuxsoft_archives/docu/files/ScalaTutorial.pdf;
  • Scala by Example, http://www.scala-lang.org/sites/default/files/linuxsoft_archives/docu/files/ScalaByExample.pdf
• Alternatives: Principle of Concurrent and Distributed Programming, M. Ben-Ari, Prentice Hall, 1990.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.