COMP2310: Concurrent and Distributed Systems

(6 credit points) Group B
Second Semester

Thirty one-hour lectures and nine two-hour tutorial/laboratory sessions

Lecturer: Mr Richard Walker and Dr Malcolm Newey

Prerequisites

COMP2100 or COMP2300 or COMP2031; 12 credit points of 1000-level mathematics or mathematical statistics units.
Incompatible with COMP2029, COMP2032

Syllabus

This unit is concerned with the issues that arise when computational processes are supported in a computer system. The scope is broad enough to include discussion of all the layers of a computer system - from the hardware to large information systems applications, and all sizes of computer system - from systems as small as a single processor, to systems as large as the entire Internet. The principal areas of study are processes and process coordination, concurrency support in operating systems and high level languages, and distributed systems. The following topics are addressed: operating system structure, process management, interaction between system components (processes, devices and processors), mutual exclusion, concurrent programming, semaphores and monitors, inter-process communication, distributed systems, crash resilience and persistent data, deadlock, transaction processing.

Description

This course is an introduction to a broad sweep of issues across the concurrent and distributed systems landscape, from a variety of perspectives. Topics range from low-level primitives such as semaphores, through to high-level middleware packages such as CORBA. As such, this is one of the broadest courses taught by the department. As far as possible, theory is tied to practice; for example, all algorithms presented are held up to scrutiny: are the assumptions under which they work reasonable in real computer systems? Some common threads (e.g. transparency) are used to tie together topics that would otherwise appear unrelated.

Rationale

Concurrency is an essential feature of many computer systems. The ability to work effectively with operating systems, real-time systems, large databases, distributed information systems and even sophisticated user interfaces requires a good understanding of the problems that concurrency entails. Any system which operates as a set of separate processes which `communicate' by sending `messages' to each other is a distributed system. In practice, the high-level abstractions of distributed systems are used on hardware ranging from single-processor computers to multi-computers, networks of workstations, and large networks such as the Internet. The software engineer must be able to reason about concurrent and distributed systems and be able to apply available tools that help one solve the problems that concurrent and distributed computation can introduce. Distributed systems is one of the hottest topics in computing today, both in academia and industry, not least because of the impact of the Internet and web technologies. A sound knowledge of theory and practice is essential for computing professionals today and in the future.

Ideas

This unit will carry the main responsibility for:

presenting the main ideas associated with concurrent computation: processes, cooperation and interference, control of resources, communication;
presenting the main ideas associated with distributed computation: message passing, remote procedure call, client/server systems, atomic and idempotent operations;
providing an understanding of operating system structure;
developing experience with some techniques for achieving mutual exclusion and synchronization: semaphores and monitors;
teaching the ways that concurrency is realized in the Java programming language and under the Unix operating system.

The unit shares responsibility for teaching software design by providing an introduction to the techniques and tools in this area. It is one of several units that provide practical programming experience in an object-oriented framework. It will assume principal responsibility for training students in their second industrial strength object-oriented programming language.

Topics

The following topics will be covered:

a taxonomy of concurrent systems;
Unix processes;
Unix shells;
mutual exclusion;
semaphores;
monitors;
remote procedure call mechanisms;
operating systems overview;
process and thread management;
device management;
interprocess communication: messages, pipes, sockets, XTI;
atomic and idempotent operations;
persistent data;
distributed computation;
deadlock and livelock;
correctness and fairness properties;
transaction processing.

ACM KU's

AR7: Alternative Architectures (2 of 5)
OS1: History, Evolution, and Philosophy (3 of 3)
OS2: Tasking and Processes (2 of 2)
OS3: Process Coordination and Synchronization (4 of 4)
OS4: Scheduling and Dispatch (1 of 3)
OS6: Device Management (2 of 2) Different material from OS6.
OS9: Communications and Networking (2 of 3)
OS10: Distributed and Real-time Systems (2 of 3) Other material included.
PL12: Distributed and Parallel Programming Constructs (3 of 3)

Objectives

Upon completion of this unit, the student will be able to:

1.: enumerate and describe the concepts involved in the construction of concurrent and distributed systems (level in Biggs SOLO taxonomy: 3 ; generic graduate attributes: 1,3)
2.: write programs that create cooperating subtasks which are Unix processes, and write Java programs which use threads (level in Biggs SOLO taxonomy: 4 ; generic graduate attributes: 1,2)
3.: develop the components of a small distributed system in a teamwork setting (level in Biggs SOLO taxonomy: 4 ; generic graduate attributes: 1,2,4,6)
4.: select appropriate mechanisms and apply them to the solution of problems in concurrent and distributed systems (level in Biggs SOLO taxonomy: 4 ; generic graduate attributes: 4)

Assessment

The following assessment modes are used.

final examination: This tests objective 1.
programming exercises: Three graded programming tasks will be assigned, each of which will address one or more topics covered in lectures and laboratory work. For two assignments, each student will submit the completed program. One assignment will be done in pairs; each pair will submit the completed program(s). This tests objectives 2 and 3.
reports: Each programming assignment will be in the form of a `literate program' that contains elements of analysis and design (using appropriate notations and diagrams). This tests objectives 1 and 3.
problem solving: One of the assignments will also contain a number of small problems which address design and/or implementation issues covered in lectures. This tests objectives 1 and 4.

Technical Skills