Objectives and outcomes
Introduction to design concepts and principles in the construction of concurrent and distributed systems. Upon completion of the course, students are able to demonstrate knowledge and understanding of various models of concurrent systems, as well as models and architectures of distributed systems. They understand the concepts and principles of designing concurrent and distributed systems. They can design and implement software in a distributed environment.
Lectures
Terminology and classification. Mutual exclusion. Concurrent objects. Concurrency and correctness. Consistency models. Spin-Locks. Test-and-Set (TAS) and Test-and-Test-and-Set. Exponential back off. CLH and MSC Queue locks. Composite keys. Clusters and hierarchical keys. Monitors. Semaphores. Barriers. Sense-reversing barrier. Combining tree barrier. Static tree barrier. Termination detection barrier. Transactional memory. Transactions and atomicity. Software and hardware transactional memory. Multiprocessor scheduling. Model of distributed executions. Hardware and software concepts. Network communication models. Global state of a distributed model. Logical time. Clock synchronisation. Algorithms for FIFO and non-FIFO channels. Basic distributed algorithms. Synchronisers. Message ordering and group communication. Distributed mutual exclusion algorithms. Distributed shared memory. Consensus and agreement. Failure detection.
Practical classes
Implementations of synchronisation primitives. Creating and controlling the operation of threads. Concurrent tools. Synchronisation. Producer – consumer. Readers and writers. Critical sections. Peterson’s algorithm. Filtering algorithm. Lamport’s bakery algorithm. Spin-Lock and conflict. Semaphores and barriers. Interruption and mutual thread blocking. GUI – examples of concurrency. Distributed systems and broadcast. Implementation of vector clocks. Differential technique. Direct dependency technique. Adaptive technique. 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. Algorithms for distributed mutual exclusion. Lamport’s algorithm. Ricart–Agrawala and Singhal algorithm. DHT and Chord.