The midterm exam for CS:5620 "Distributed Systems and Algorithms" will be held on Oct 11th (Tue) from 6:30 pm to 8:30 pm in 105 Seashore Hall (SSH).

During the exam you can use any written/printed material you bring, including books, lecture notes and solutions, handwritten/typed notes, etc. Make sure you bring everything that you feel you will need to the exam because you will not be allowed to share or borrow material with classmates during the exam. You will have to turn off and remove from your vicinity all electronic devices including cell phones, lap tops, calculators, dictionaries, etc.

The exam is worth 250 points, which is 25% of your final grade. Here is a brief description of the structure of the exam. The first three problems are worth 60 points each and the last problem will be worth 70 points.

• Problem 1. You will be asked to hand-execute one or more distributed algorithms and show the algorithm's output after each round. The algorithms you will be asked about may be algorithms we have already discussed in class (e.g., the Cole-Vishkin 3-coloring algorithm on oriented trees, Distributed Dijkstra's algorithm in the asynchronous setting, etc.) or they may be algorithms that I describe as part of the problem. Alternately, you may be asked to construct inputs for which the distributed algorithm exhibits certain specific behavior. For example, can you construct an input graph for which it takes the Distributed Kruskal's algorithm exactly n + d - 2 rounds before all the MST edges reaches the root of the BFS tree?

• Problem 2. In class, we have discussed randomized distributed algorithms such as Luby's coloring and MIS algorithms. In this problem, you will be given specific inputs and asked to calculate the probabilities of certain events or the expectations of certain random variables describing the behavior of specific randomized distributed algorithms (e.g., Problem 2 in HW 2). Alternately, you may be asked to construct inputs for which the randomized algorothm exhibits certain specific probabilistic behavior. For example, can you describe an input graph and a node v in that graph for which the probability that v's status is determined in the first round of Luby's MIS algorithm is less than 1/100.

• Problem 3. This question is meant to test your understanding of proofs of algorithm correctness (e.g., the proof of correctness of Distributed Kruskal's algorithm), lower bound proofs (e.g., Linial's Omega(log^* n) lower bound on 3-coloring oriented cycles), round complexity analysis (e.g., showing that a constant fraction of edges are expected to become inactive in each round of Luby's MIS algorithm). You will not be required to reproduce any proofs/analyses fully, but you will be asked about specific parts of these proofs/analyses (e.g., Problem 1 in HW 3 asks about k-ary c-coloring functions that appear in Linial's lower bound proof).

• Problem 4. You will be given a problem and asked to design a distributed algorithm for it, possibly running in a specified number of rounds. You might also be asked to prove correctness of your algorithm or analyze the round complexity or message complexity of your algorithm. Most homework problems have been of this type, but given that you have limited amount of time to solve this problem in the exam, I will lead you through the design of the algorithm and also its analysis/proof of correctness.