Computer Laboratory > Teaching > Course material 2009–10 > Computer Science Tripos Syllabus and Booklist 2009-2010 > Concurrent and Distributed Systems

Next: Group Project Up: Michaelmas Term 2009: Part Previous: Further Java   Contents

Concurrent and Distributed Systems

Lecturer: Professor Jean Bacon and Dr Ken Moody

No. of lectures: 16

Prerequisite course: Operating Systems

Aims

The aim of the course is to introduce concurrency control and distribution concepts and their implications for system design and implementation.

Lectures on Concurrency

• Introduction; thread models. Overview of properties of distributed and concurrent systems. Software system structure. Occurrence of concurrency in systems. Recap of scheduling and preemption. Thread models.

• Classical concurrency control. Shared data and critical regions. Mutual exclusion and condition synchronisation. Semaphores. Implementation of concurrency control.

• Classical problems using semaphores. Bounded cyclic buffer (producer(s) and consumer(s)), multiple readers and writers. Problems arising in semaphore programming.

• Concurrency support in programming languages. Shared data: monitors, pthreads, Java. No shared data: occam, Ada active objects, Erlang, Kilim, tuple spaces. Lock-free programming.

• Concurrent composite operations. Composite operations in main memory and persistent memory. Dynamic resources allocation and deadlock. Dining philosophers program. Deadlock detection and avoidance.

• Transactions. ACID properties. Concurrency control and crash recovery. Definition of conflicting operations. Serialisation. Cascading aborts.

• Database concurrency control. Pessimistic concurrency control: two-phase locking, timestamp ordering. Optimistic concurrency control.

• Database recovery and summary of ``Concurrency''. Write ahead log, undo/redo. Points to take forward.

Lectures on Distributed Systems

• Introduction, Evolution, Architecture. Fundamental properties. Evolution from LANs. Introduction to the need for naming, authentication, policy specification and enforcement. Examples of multi-domain systems.

• Time and event ordering. Time, clocks and event ordering. Earth time, computer clocks, clock drift, clock synchronisation. Order imposed by inter-process communication. Timestamps point/interval. Event composition; uncertainty of ordering, failure and delay.
  

  Process groups: open/closed, structured/unstructured. Message delivery ordering: arrival order; causal order (vector clocks); total order. Physical causality from real-world examples.

  
  
• Consistency and commitment. Strong and weak consistency. Replica management. Quorum assembly. Distributed transactions. Distributed concurrency control: two-phase locking, timestamp ordering. Atomic commitment; two-phase commit protocol. Distributed optimistic concurrency control and commitment.
  

  Some algorithm outlines: Election of a leader. Distributed mutual exclusion.

  
  
• Middleware 2L. Synchronous:RPC, object-orientated. Asynchronous: message orientated, publish/subscribe, peer-to-peer. Event-based systems. Examples of some simple distributed programs in Java. How to get started.

• Naming and name services. Unique identifiers, pure and impure names. Name spaces, naming domains, name resolution. Large scale name services: DNS, X.500/LDAP, GNS. Use of replication. Consistency-availability tradeoffs. Design assumptions and future issues.

• Access control for multi-domain distributed systems. Requirements from healthcare, police, emergency services, globally distributed companies.. ACLs, capabilities, Role-Based Access Control (RBAC). Context aware access control. Examples: OASIS, CBCL OASIS, Microsoft Healthvault, Authentication and authorisation: Raven, Shibboleth, OpenID.

• Distributed storage services. Summary and roundup. Network-based storage services. Naming and access control. Peer-to-peer protocols. Content distribution. Summary and roundup. Open problems for future years: transactional main memory; multicore concurrency control; untrusted components. Byzantine failure.

Objectives

At the end of the course students should

• understand the need for concurrency control in operating systems and applications, both mutual exclusion and condition synchronisation;

• understand how multi-threading can be supported and the implications of different approaches;

• be familiar with the support offered by various programming languages for concurrency control and be able to judge the scope, performance implications and possible applications of the various approaches;

• be aware that dynamic resource allocation can lead to deadlock

• understand the concept of transaction; the properties of transactions, how concurrency control can be assured and how transactions can be distributed;

• understand the fundamental properties of distributed systems and their implications for system design;

• understand the effects of large scale on the provision of fundamental services and the tradeoffs arising from scale;

• be familiar with a range of distributed algorithms.

Recommended reading

* Bacon, J. & Harris, T. (2003). Operating systems: distributed and concurrent software design. Addison-Wesley.
Bacon, J. (1997). Concurrent Systems. Addison-Wesley.
Tanenbaum, A.S. & van Steen, M. (2002). Distributed systems. Prentice Hall.
Coulouris, G.F., Dollimore, J.B. & Kindberg, T. (2005, 2001). Distributed systems, concepts and design. Addison-Wesley (4th, 3rd eds.).

---

---

Next: Group Project Up: Michaelmas Term 2009: Part Previous: Further Java   Contents