Objectives and outcomes
Introduction to design concepts and principles of concurrent and distributed systems.
Upon completion of the course, students are able to: demonstrate the knowledge and understanding of
different models of concurrent systems as well as models and architectures of distributed systems. They have
a basic knowledge of the concepts and principles of designing concurrent and distributed systems. They
design and use software in a distributed environment.
Lectures
Terminology and classification. Mutual exclusion. Concurrent objects. Concurrency and
correctness. Consistency models. Conditions for progress. Spinlock. Test-and-Set (TAS). TTAS.
Exponential Backoff. CLH and MSC Queue Lock. Composite key. Clusters and hierarchical keys.
Monitors. Semaphores. Barriers. Barriers with combination and static tree. Barriers with completion
detection. Transaction memory. Transactions and atomicity. Software and hardware transaction memory.
Multiprocessor scheduling. Load distribution. Distributed execution model. Communication network
models. The global state of the distributed system. Logical time.
Logical clock system. Scalar time. Vector time. Matrix time. Synchronisation of physical clocks. Global
state and algorithms for its recording. Algorithms for FIFO and non-FIFO channels. Finding consistent
global imagery. Basic distributed algorithms. Synchronises. Choice of leader. Message ordering and group
communication. Distributed mutual exclusion. Distributed shared memory. Agreement and consensus.
Failure detection.
Practical classes
Implementations of synchronisation primitives and keys. Creating and controlling thread operation.
Concurrent tools. Thread tanks. Synchronisation. Producer – consumer. Readers and writers. Critical
sections. Peterson’s algorithm. Filter algorithm. Lamport’s bakery algorithm. Spinlock and conflict. Semaphores and barriers. Interruption of work and mutual blocking of threads. GUI – examples of concurrency.
Distributed systems and broadcast. Implementation of vector clocks. Differential
technique. Direct dependence technique. Adaptive technique. Problems in recording the global state.
Algorithms for FIFO channels. Chandy – Lamport and Spezialetti – Kearns algorithm. Venkatesan
incremental algorithm. Helary wave synchronisation method. Algorithms for non-FIFO channels. Lai –
Yang and Li algorithm. Mattern’s algorithm. Distributed mutual exclusion algorithms. Lamport’s algorithm.
Ricart – Agrawala and Singhal algorithm. DHT and Chord.