CS:5620 Midterm Announcement
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.