Exam 2 topics

This is intended to give you a sense of what I think is important from the course so far, and what I will be thinking of when creating the exam.

I hate disclaimers, but here are some anyway. This is not a contract. I may have inadvertently left something off this list that ends up in an exam question. I make no guarantees that the exam will be 100% limited to items listed below. Moreover, I will not be able to test all of this material given the time limitations of the exam. I will have to pick and choose some subset of it.

You are permitted one 8.5 x 11 sheet of paper with notes (both sides) for use as a reference during the exam.

Students should be able to…

• look at pseudocode of the style presented in the warmups to Dekker's algorithm, and be able to assess whether critical sections satisfy mutual exclusion, deadlock freedom, and starvation freedom. The arguments for Dekker's algorithm itself get pretty complex and might not make for great exam questions, but simpler arguments of its type would be reasonable. (Reading: see Moodle page, "The Critical Section Problem")
• describe and evaluate variations for these parallel linked list approaches: (Reading: see Moodle page, "Linked Lists: The Role of Locking")
  • Coarse-grained synchronization
  • Fine-grained synchronization (hand-over-hand)
  • Optimistic synchronization
  • (Lazy synchronization and non-blocking synchronization are awesome but won't be on the exam)
• evaluate tradeoffs for synchronous vs asynchronous replication, as well as primary vs no-primary replication. Analyze with respect to strong vs eventual consistency vs weak consistency. (Reading: see Moodle page, "An Intro to Distributed Systems")
• describe and answer analytical questions regarding 2-phase commit process for distributed systems. (Reading: see Moodle page, "An Intro to Distributed Systems")
• interpret MPI code as well as write pseudocde in the style of MPI to solve a particular problem (Reading: see Moodle page, "MPI (Wikipedia)"
• evaluate technical issues that arise regarding remote procedure calls that distinguish them from traditional procedure calls (Reading: see Moodle page, "[Remote procedure calls] Distributed Systems Ch.2 Communication")
• interpret Hadoop MapReduce code as well as write pseudocode in the style of Hadoop to solve a particular problem (Reading: various Hadoop references on Moodle)
• distinguish MapReduce, HDFS, YARN, and describe their roles within Hadoop (Reading: various Hadoop references on Moodle)
• compare and contrast clock synchronization methods, specifically: (Reading: see Moodle page, [Clock synchronization] Distributed Systems: Concepts and Design, Chapters 10.1-10.4 and 11.2 URL)
  • Cristian's method
  • Berkeley algorithm
  • Network Time Protocol (at least, its main ideas)
• describe Byzantine Generals problem, justify the interactive consistency conditions, address impossibility of a 3 general solution with a single traitor (Reading: see Moodle page, "Byzantine Generals")