Department of Computer Science and Technology – Course pages 2020–21: Concurrent and Distributed Systems skip to primary navigationskip 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 Graduate Why Cambridge Course directory How to apply Fees and 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 Global Cambridge News Events Public engagement Jobs Give to Cambridge Research at Cambridge For staff For current students For alumni For business Colleges & departments Libraries & facilities Museums & collections Email & phone search Computer Laboratory Teaching Courses 2020–21 Concurrent and Distributed Systems Department of Computer Science and Technology Undergraduate Home The department Overview People Overview Academic staff Support staff Contract researchers Fellows & affiliates PhD students Visitors Seminars Overview Wednesday Seminar Series Wheeler Lectures women@cl 10th Anniversary Computer Laboratory 75th Anniversary History Facilities Overview Reception Food Shopping and leisure Cycling Library Overview Library induction Library guides Catalogues Coronavirus resources Electronic resources Local services Lab technical reports External technical reports Resource lists Reading lists Reprographics equipment Archives Maps and directions Contact information Research Overview Artificial Intelligence Overview People Group Meetings Project ideas for current students Computer Architecture Overview Projects and research topics ACS & Part II/III Project Suggestions People Selected Publications Open source components Group Meetings Contact Details Digital Technology Graphics & Interaction Overview Research Members Projects Applying to do a PhD Project suggestions Other information Reading Club Natural Language Processing Overview People Publications Projects Postgraduate opportunities Resources Programming, Logic, Semantics Security Overview People Publications Projects and topics Security Seminar Series Meetings Courses Posters Journals Mailing lists blog Systems Overview Research Projects Members Seminars Student Projects Research support Overview Research grants Fellowships Meetings & Travel Industrial Collaboration Commercialisation Writing a proposal Impact statements Collaborating with the Computer Lab Making your work public Admissions Overview Undergraduate Computer Science at Cambridge Overview Course Open Days Apply CSAT FAQ Contact MPhil ACS Overview Modules PhD applications Research Graduate Admissions Prospectus Funding deadlines PhD degree Overview Research Graduate Admissions Prospectus Funding deadlines MPhil in Advanced Computer Science CPGS Premium Research Studentship Student Administration Teaching Overview Part IA Part IB Part II Masters courses Overview Induction for M.Phil and Part III students ACS Forms Part III and ACS projects PhD students Freshers Courses 2020–21 Overview Part IA CST Part IB CST 75% Part IB CST 50% Part II CST 75% Part II CST 50% Part III MPhil ACS Lecturer index Instructions for lecturers Undergraduate Courses 2021–22 Overview Part IA CST Part IB CST Part II CST 75% Part II CST 50% Part III MPhil ACS Lecturer index Instructions for lecturers Exams Overview Examination dates Examination results Examiners' reports Plagiarism and collusion Purchase of calculators Data Retention Policy Past exam papers Guidance on deadlines Part III Assessment MPhil Assessment Student Complaint Procedure Lecture timetables Overview Short form timetable Supervisions Overview Part II supervisions overview Part II sign-up dates Notes on supervising Supervisor support Academic exchanges Overview Advice for students visiting Cambridge UROP internships Part IB group projects Overview Timetable Photos Previous years Part II projects Overview Briefing document (Pink Book) Important dates Overseers Phase 1 report Back-up advice Resources Declaration Studies Involving Human Participants Failure to submit proposal Selection Tips Declaration of originality Submission of dissertation IP ownership Diploma model projects Older project suggestions Supervising Notes Overseer Briefing Notes Directors of Studies Resources Overview Managed Cluster Service Part III and MPhil machines Online services Installing Linux MATLAB Microsoft Azure for Education Membership Miscellaneous Overview News Honours Obituaries Overview Neil Wiseman, 1934–1995 Roger Needham, 1935–2003 David Wheeler, 1927–2004 Karen Spärck Jones, 1935–2007 Judith Ann Bailey, 1934–2008 Robin Milner, 1934–2010 Sir Maurice Wilkes, 1913–2010 Michael JC Gordon, 1948–2017 Richard Gibbens, 1962–2018 Internal information Overview New arrivals Overview An introduction to our computing facilities Information for new PhD students Information for new staff Information for visitors Information for hosts of visitors General information Induction Guidelines Specialist resources System administration Overview Email Printing and scanning Filespace The CL network SSH access to the CL systems Supported platforms Generic Unix/Linux information Web servers and sites The RT ticketing system Specialist resources Lecture theatre AV Sitemap Frequently asked questions Roles and responsibilities Overview People History Information for staff Overview Accounting Parking Cycling Departmental policies Information for hosts of visitors Meeting rooms Personnel information Reception Staff training Stores UROP internships Wiseman prize Health and safety Overview Emergency First aid General health and safety Environment Fitness H&S policies & committees Risk assessment Laser safety Useful links Index of Health & Safety pages Committee PhD resources Overview Induction PhD supervisors Graduate Advisers CPGS First Year Report: PhD Proposal Second Year Report: Dissertation Schedule Third Year Report: Progress Statement Fourth Year Report: the last year Papers and conferences Writing up Thesis formatting Submitting your dissertation Exemption from University Composition Fees Leave to work away, holidays and intermission Researcher Development Application deadlines List of PhD thesis Graduate Students' Forum PAT, recycling and Building Services Typographic resources Overview Thesis formatting Preparing Tripos exam questions in LaTeX Teaching resources Overview Information for CST examiners Information for Directors of Studies ACS module definition Providing advice to incoming ACS students ACS interviewing and admissions Outreach material Committees Overview Faculty Board Degree Committee Graduate Education Tripos Management Outreach Health & Safety IT Strategy Equality and Diversity Research Staff Staff–Student Directors of Studies Workload Wellbeing Graduate Students Ethics Buildings and Environment Selection External Discontinued committees William Gates Building Overview Building Services Access and security Care of the WGB Facilities in offices Energy & Environment Meeting rooms Stores West Cambridge Site Leaving the department Course pages 2020–21 Concurrent and Distributed Systems Syllabus Course materials Recordings Information for supervisors Principal lecturers: Dr David Greaves, Dr Martin Kleppmann Taken by: Part IB CST 50%, Part IB CST 75% Hours: 16 Suggested hours of supervisions: 4 Prerequisites: Object-Oriented Programming, Operating Systems This course is a prerequisite for: Cloud Computing, Distributed Ledger Technologies: Foundations and Applications, Mobile and Sensor Systems Past exam questions 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). © 2021 Department of Computer Science and Technology, University of Cambridge Information provided by Dr David Greaves – edit page University A-Z Contact the University Accessibility Freedom of information Terms and conditions Study at Cambridge Undergraduate Graduate 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 Give to Cambridge Research at Cambridge News Features Discussion Spotlight on... About research at Cambridge
