Description
1.(5 points) Consider the Chord DHT with an m-bit ID and n peers, that uses Finger Tables for lookup(·). A lookup(k)
is initiated at some peer with ID p, and the Finger Table at p says that a peer with ID q is the next peer to whom the
query should be forwarded. Suppose we use the operator “−” between two IDs to indicate the number of peers between
them in the ring.
Disprove the following claim: q − p ≥ (k − p)/2.
2.(5 points) In a Chord DHT:
(a) with Finger Tables, suppose we have n − 1 peers, and we insert a new, i.e., an n
th, peer. What is the worst-case
number of Finger Tables that need to be updated?
(b) without Finger Tables, i.e., in which each peer p maintains only a lookup table of one entry, succ(p + 1), what is
the worst-case number of lookup tables that need to be updated?
3.(5 points) Call a function f(m) linear in its input m if there exists a positive constant c1 and a constant c0 such that
f(m) = c1m + c0. For example, g(m) = 0.25m − 12 is linear in m. Suppose we denote a function that is linear in
m as Θ(m).
We have shown in the lecture that the number of hops to do lookup(k) for a key k in a Chord DHT which uses m-bit
identifiers is at most Θ(m).
Show that it is at least Θ(m), in the worst-case. That is, given any integer m ≥ 1, there exists an instance of a Chord
DHT, a peer p and a key k such that the number of hops incurred by lookup(k) at peer p is at least a linear function of
m.
4.(5 points) Suppose we have a 2-dimensional CAN in which peers and content are organized into an n×n grid. Each
peer/content has ID hi, ji. You want the peers and content to also be part of a Chord DHT. Give an invertible function
f: [1, n] × [1, n] −→ [0, n2 − 1] to map IDs to and from the Chord DHT.
5.(5 points) Consider an unstructured overlay network in which each node randomly chooses c neighbours. If P and
Q are both neighbours of R, what is the probability that they are neighbours of one another?
6.(5 points) Suppose we quantify communication-cost in the context of the Bully and Ring election algorithms as
follows. To send a constant-sized message from one process to another incurs a constant communication-cost.
In the Bully algorithm, assume that all the three messages, ELECTION, OK and COORDINATOR have constant-size.
In the Ring algorithm, assume that an ELECTION message with one process ID is constant-size, every process ID is
constant-size, and a COORDINATOR message is constant-size.
Suppose we have processes with IDs 1, 2, . . . , n, n + 1, and the process with ID n + 1 is the current coordinator. That
coordinator process crashes. What is the worst-case communication-cost in the Bully algorithm? What is it for the
Ring algorithm?
7.(5 points) In the Ring election algorithm, we could have multiple ELECTION messages going around the ring
simultaneously. This is wasteful. Give an algorithm that kills off an unnecessary message as early as possible, but still
maintains the correctness of the election.
