Concurrent and Distributed Systems | Department of Computer Science and Technology skip to content Study at Cambridge About the University Research at Cambridge Search site Home Study at Cambridge Undergraduate Courses Applying Events and open days Fees and finance Student blogs and videos Postgraduate Why Cambridge Course directory How to apply Fees Funding Frequently asked questions International students Continuing education Executive and professional education Courses in education About the University How the University and Colleges work History Visiting the University Term dates and calendars Map For media Video and audio Find an expert Publications International Cambridge News Events Public engagement Jobs Giving to Cambridge Research at Cambridge For staff For current students For alumni For business Colleges & departments Libraries & facilities Museums & collections Email & phone search Department of Computer Science and Technology Log in with Raven Home The department About People People overview Faculty Research staff PhD students Professional services staff Fellows Affiliated lecturers Visitors News Seminars Seminars overview Weekly timetable Wednesday seminars Wednesday seminar recordings ➥ Wheeler lectures Computer Laboratory 75th anniversary ➥ women@CL 10th anniversary ➥ Job vacancies ➥ History Facilities Reception Food Cycling Maps and directions How to find us William Gates Building Contact information Initiatives Accelerate Programme for Scientific Discovery Accelerate Programme for Scientific Discovery overview Contacts Data for Science Residency FAQs News Data Trusts Initiative Data Trusts Initiative overview News People Pilot Funding FAQs Research Funding FAQs Cambridge Ring Cambridge Ring overview Ring News Ring Events Hall of Fame Hall of Fame Awards FAQ Hall of Fame - Nominations The Supporters' Club The Supporters' Club overview Members Industrial Collaboration Annual Recruitment Fair Annual Recruitment Fair overview Archive Graduate Opportunities Summer internships Technical Talks Supporter Events and Competitions How to join Collaborate with Us Cambridge Centre for Carbon Credits (4C) Equality and Diversity Equality and Diversity overview Athena SWAN E&D Committee Support and Development Targeted funding LGBTQ+@CL LGBTQ+@CL overview Events Links and resources Queer Library women@CL women@CL overview About Us About Us overview Friends of women@CL Friends of women@CL overview Past members Past Student Members News Calendar Tech Events Social Events Mentoring Students' experiences Contact Contact overview Mailing lists Useful information Scholarships Initiatives Support Dignity Policy FAQ Outreach Raspberry Pi Tutorials ➥ Wiseman prize Research Research overview Research themes Algorithms and Complexity Computer Architecture Graphics, Vision and Imaging Science Human-Centred Computing Machine Learning and Artificial Intelligence Mobile Systems, Robotics and Automation Natural Language Processing Programming Languages, Semantics and Verification Security Systems and Networking Technical Reports Admissions Admissions information Undergraduate admissions Undergraduate admissions overview Open days and events Undergraduate course overview Undergraduate course overview overview Year 1 Year 2 Year 3 Year 4 Making your application Admissions FAQs MPhil in Advanced Computer Science MPhil in Advanced Computer Science overview Applications Course structure Funding competitions Prerequisites PhD in Computer Science PhD in Computer Science overview Application forms Research Proposal Funding competitions and grants Premium Research Studentship Current students Current students overview Part IA Part IB Part IB overview Part IB group projects Part IB group projects overview Important dates Design briefs Moodle course ➥ Learning objectives and assessment Course structure Technical considerations After the project Behaviour Part II Part II overview Part II projects Part II projects overview Important dates Part II project suggestions Overseer groups Project proposal Advice on running the project Progress report and presentation The dissertation Submission Assessment Supervisor briefing notes Overseer Briefing Notes Past overseer groups ➥ Part II sign-up dates Part II units of assessment Part II supervisions overview Continuing to Part III Part III of the Computer Science Tripos Masters courses Overview Overview overview Resources Information for current Masters students ACS Forms Part III and ACS projects Part III and ACS projects overview Submission of project reports ACS projects ACS projects overview Guidance for ACS projects Part III projects Part III projects overview Guidance for Part III projects Project suggestions Induction for M.Phil and Part III students Preparation Registration Induction - Masters students PhD students PhD resources PhD resources overview Deadlines for PhD applications Protocol for Graduate Advisers for PhD students Guidelines for PhD supervisors Induction information Induction information overview Important Dates Who is here to help Exemption from University Composition Fees The basics Being a research student Researcher Development Progression Third Year Report: Progress Statement Fourth Year: writing up and completion Fourth Year: writing up and completion overview PhD thesis formatting Writing up and word count Submitting your dissertation CPGS First Year Report: the PhD Proposal Second Year Report: Dissertation Schedule Papers and conferences Leave to work away, holidays, and intermission List of PhD students ➥ PAT, recycling, and Building Services Freshers Freshers overview Cambridge University Freshers' Events Course material 2021/22 ➥ Course material 2020/21 Course material 2020/21 overview Part IA Part IB CST 75% Part IB CST 50% Part II CST 75% Part II CST 50% Part III MPhil ACS MPhil ACS overview Advanced Graphics and Image Processing Advanced Operating Systems Advanced Topics in Computer Architecture Advanced Topics in Computer Systems Advanced Topics in Mobile Systems and Mobile Data Machine Learning Advanced topics in machine learning or natural language processing Affective Computing Algebraic Path Problems Automated Reasoning Category Theory Computer Security: Principles and Foundations Computer Vision Cybercrime Data Science: principles and practice Digital Signal Processing Distributed Ledger Technologies: Foundations and Applications Hardware Security Practicals Interaction with machine learning Interactive Formal Verification Introduction to Natural Language Syntax and Parsing Large-scale data processing and optimisation Machine Learning and the Physical World Machine Learning for Language Processing Mobile Robot Systems Multicore Semantics and Programming Network Architectures Overview of Natural Language Processing Principles of Machine Learning Systems Probabilistic Machine Learning Research Skills Programme Technology, law and society Exams Exams overview Examination dates Examination results ➥ Examiners' reports ➥ Part III Assessment MPhil Assessment Past exam papers ➥ Examinations Guidance 2021-22 Head of Department's Announcements Part IA Part IB Part II Part III Marking Scheme and Classing Convention Guidance on Plagiarism and Collusion Purchase of calculators Examinations Data Retention Policy Guidance on deadlines Student Complaint Procedure Lecture timetables Lecture timetables overview Understanding the short form timetable Supervisions Supervisions overview Part II supervisions overview ➥ Part II sign-up dates ➥ Notes on supervising Supervisor support Directors of studies list Exchanges and internships Academic exchanges Advice for visiting students taking Part IB CST UROP internships Undergraduate student guidance Resources for students Resources for students overview Online services MATLAB Managed Cluster Service (MCS) Microsoft Software for personal use Installing Linux Part III and MPhil Machines Transferable skills Lecture feedback and student representation Lecture feedback and student representation overview Providing lecture feedback Fast feedback hotline Staff-Student Consultative Forum Graduate Students' Forum ➥ Breaking the silence ➥ Student administration offices Intranet Concurrent and Distributed Systems Principal lecturer: Dr David Greaves Dr. Martin Kleppmann Students: Part IB CST 50%, Part IB CST 75% Term: Michaelmas term Course code: ConcDisSys Prerequisite course: Object-Oriented Programming Operating Systems This course is a prerequisite for: Cloud Computing Distributed Ledger Technologies: Foundations and Applications Mobile and Sensor Systems Hours: 16 Suggested hours of supervisions: 4 Aims This course considers two closely related topics, Concurrent Systems and Distributed Systems, over 16 lectures. The aim of the first half of the course is to introduce concurrency control concepts and their implications for system design and implementation. The aims of the latter half of the course are to study the fundamental characteristics of distributed systems, including their models and architectures; the implications for software design; some of the techniques that have been used to build them; and the resulting details of good distributed algorithms and applications. Lectures: Concurrency Introduction to concurrency, threads, and mutual exclusion. Introduction to concurrent systems; threads; interleaving; preemption; parallelism; execution orderings; processes and threads; kernel vs. user threads; M:N threads; atomicity; mutual exclusion; and mutual exclusion locks (mutexes). Automata Composition. Synchronous and asynchronous parallelism; sequential consistency; rendezvous. Safety, liveness and deadlock; the Dining Philosophers; Hardware foundations for atomicity: test-and-set, load-linked/store-conditional and fence instructions. Lamport bakery algorithm. Common design patterns: semaphores, producer-consumer, and MRSW. Locks and invariants; semaphores; condition synchronisation; N-resource allocation; two-party and generalised producer-consumer; Multi-Reader, Single-Write (MRSW) locks. CCR, monitors, and concurrency in practice. Conditional critical regions (CCR); monitors; condition variables; signal-wait vs. signal-continue semantics; concurrency in practice (kernels, pthreads, Java). Deadlock and liveness guarantees Offline vs. online; model checking; resource allocation graphs; lock order checking; deadlock prevention, avoidance, detection, and recovery; livelock; priority inversion; priority inheritance. Concurrency without shared data; transactions. Active objects; message passing; tuple spaces; CSP; and actor models. Composite operations; transactions; ACID; isolation; and serialisability. Further transactions History graphs; good and bad schedules; isolation vs. strict isolation; 2-phase locking; rollback; timestamp ordering (TSO); and optimistic concurrency control (OCC). Crash recovery, lock-free programming, and transactional memory. Write-ahead logging, checkpoints, and recovery. Lock-free programming. Hardware and software transactional memories. Lectures: Distributed Systems Introduction to distributed systems; RPC. Avantages and challenges of distributed systems; unbounded delay and partial failure; network protocols; transparency; client-server systems; remote procedure call (RPC); marshalling; interface definition languages (IDLs). System models and faults. Synchronous, partially synchronous, and asynchronous network models; crash-stop, crash-recovery, and Byzantine faults; failures, faults, and fault tolerance; two generals problem. Time, clocks, and ordering of events. Physical clocks; UTC; clock synchronisation, drift, and compensation; Network Time Protocol (NTP). Logical time; happens-before relation; Lamport clocks; vector clocks. Replication. Fault tolerance; leader-based, multi-leader, and leaderless replication; quorum systems; replica consistency; linearizability; CAP theorem; eventual consistency; session guarantees. Middleware and protocols. Process groups; FIFO, causal order, and total order broadcast; message-oriented and object-oriented middleware; distributed mutual exclusion. Consensus and distributed transactions. Leader elections; consensus; the FLP result; Paxos and Raft; state machine replication; distributed transactions; atomic commit protocols; 2-phase commit. Case studies. Network File System (NFS); Amazon’s Dynamo; Google datacentre technologies (e.g. MapReduce, Spanner); cloud computing services. Advanced topics. Conflict-free Replicated Data Types (CRDTs); Byzantine fault tolerance; peer-to-peer systems; distributed systems security. Objectives At the end of Concurrent Systems portion 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 they can be implemented, and how their performance can be optimised based on optimistic assumptions; understand how the persistence properties of transactions are addressed through logging; and have a high-level understanding of the evolution of software use of concurrency in the operating-system kernel case study. At the end of the Distributed Systems portion of the course, students should: understand the difference between shared-memory concurrency and distributed systems; understand the fundamental properties of distributed systems and their implications for system design; understand notions of time, including logical clocks, vector clocks, and physical time synchronisation; be familiar with various approaches to data and service replication, as well as the concept of data consistency; understand the effects of large scale on the provision of fundamental services and the tradeoffs arising from scale; appreciate the implications of individual node and network communications failures on distributed computation; be aware of a variety of programming models and abstractions for distributed systems, such as RPC, middleware, and total order broadcast; be familiar with a range of distributed algorithms, such as consensus and two-phase commit; be familiar with a number of case studies in distributed-system design including the Network File System (NFS), the Network Time Protocol (NTP), Amazon's Dynamo, and Google’s MapReduce and Spanner systems. Recommended reading Bacon, J. and Harris, T. (2003). Operating systems: distributed and concurrent software design. Addison-Wesley. Bacon, J. (1997). Concurrent systems. Addison-Wesley. Kleppmann, M. (2017). Designing data-intensive applications. O’Reilly. Tanenbaum, A.S. and van Steen, M. (2017). Distributed systems, 3rd edition. available online. Cachin, C., Guerraoui, R. and Rodrigues, L. (2011) Introduction to Reliable and Secure Distributed Programming. Springer (2nd edition). Concurrent and Distributed Systems Related links Course materials Information for supervisors Contact us William Gates Building JJ Thomson Avenue Cambridge. CB3 0FD Information provided by pagemaster@cst.cam.ac.uk Privacy policy Social media Facebook Twitter YouTube © 2022 University of Cambridge University A-Z Contact the University Accessibility Freedom of information Terms and conditions Study at Cambridge Undergraduate Postgraduate International students Continuing education Executive and professional education Courses in education About the University How the University and Colleges work Visiting the University Map News Events Jobs Giving to Cambridge Research at Cambridge News Features Discussion Spotlight on... About research at Cambridge
