DISTRIBUTED COMPUTING
COMP 4001
September 11, 2021
Solve the problems below. Your answers do not have to be long, but
they should be complete, precise, concise and clear. Write the solutions on
your own and acknowledge your sources in case you used “library” material.
Look in the course web page on how to avoid plagiarism and for submis-
sion details (where/when/how). Exercises marked with (?) are usually more
challenging. NB: some of the exercises may require material that will be
covered in forthcoming lectures while others marked with (?) may involve
additional material not covered in class. It is preferred that you type your
work using your favourite software package but you submit only in pdf. At
the discretion of the TA a 10% bonus will be added if carefully typed and
rigorously explained. Two excellent and free packages are LATEX (for type-
setting mathematics) and Ipe (for drawing pictures).
Assignment 1
1 [10 pts]
Consider networks of n nodes labeled 1, 2, . . . , n. In each of the graphs below
describe the triple N = (V, P, p), of vertices V , vertex-port pairs P , and port
function p that define the networks.
1. Unidirectional Ring
2. Bidirectional Ring
In each case draw a picture indicating the ports at the nodes.
1
2 [10 pts]
This exercise is related to the colouring algorithm discussed in class. The
vertices of a linear unit disk graph G are unit length intervals (i.e., of length
1) placed in arbitrary positions on an infinite line. Two nodes (i.e., intervals)
are adjacent iff they overlap. The clique number of G, denoted by ω(G), is
the size of the largest number of paitwise overlapping intervals.
1. [2 pts] Apply the greedy sequential coloring algorithm discussed in
class to such an interval unit disk graph. In the pseudo-code place the
vertices in order of their left endpoint,
2. [4 pts] Give an algorithm to compute the clique number ω(G).
3. [4 pts] Now assume ω(G) is known. Consider the following sequential
algorithm. When a new interval I is presented whose left endpoint aI ,
it uses a color in {1, . . . , ω(G)} if the floor baIc of aI is even, and uses a
color in {ω(G)+1, . . . , 2ω(G)} if the floor baIc of aI is odd. Prove that
the algorithm colors the graph correctly. What is the competitive ratio
of the algorithm? (By competitive ratio we mean the ratio achieved by
our algorithm divided by the optimal one.)
3 [10 pts]
In these two exercises we illustrate what “distributed thinking” might mean.
1. [5 pts] First we illustrate how a sequence of interactions can help to
identify a user. A man and a woman are standing in front of a shop.
“I am a man” said the one with black hair. “I am a woman”, said the
one with brown hair. If at least one of them is lying, then which one is
which?
2. Next we illustrate why some information exchange can help you make
a decision. “Fred has more than a thousand dollars”, said Anthony.
“He does not,” said George. “He has less than that.” “Surely he has at
least one dollar,” said Henry. If only one statement is true, then how
much money does Fred have?
2
4 [10 pts]
Two robots are placed at arbitrary positions on the interval [L,R], where
L < R. They can move with respective constant speeds 1 and v, where
v > 1. The robots know only their own speed (and if they meet they can
compare speeds) and the initial positions of the robots are unknown to them.
1. [2 pts] Draw picture of all the possible robot configurations.
2. [8 pts] A package is placed at L. Give an optimal distributed algorithm
which delivers the package from L to R; write the pseudocode and
prove it delivers the package in optimal time. Note that the robots can
recognize L and R.
5 [10 pts] (?)
A lazy professor gave two tests A and B to a class of n students and assigned
marks Ai and Bi, respectively, to student i, for i = 1, 2, . . . , n, uniformly
and independently at random with values from the set of possible grades
1, 2, . . . , k. For example, the values of grades could be chosen from
A+, A,A−, B+, B,B−, C+, C, C−, D+, D.D−, F,
in which case k = 13. Derive a formula for the probability that some student
receives the same grade in both tests. Is it likely that this could happen
in the present the Distributed Computing class which has n = 91 students
registered, for k = 13?
6 [10 pts]
These two questions are about ring graphs.
1. A ring consists of n nodes. Each node has a unique ID and holds a
value known only to itself. The nodes are synchronous and the links
bidirectional. Design an efficient single-initiator protocol (i.e., a single
node initiates the algorithm and the rest react) to find the minimum
value in a ring. Write the pseudocode and prove its correctness and
analyze its costs.
3
2. [5 pts] (?) Assume that n chicks 0, 1, . . . , n − 1 sit around a circle.
Suddenly, each chick randomly pecks the chick immediately to its left
or right each with probability 1
2
. What is the expected number of
unpecked chicks?
7 [10 pts]
The way IDs are assigned can make a difference in the performance of a
distributed algorithm as this is measured by its termination time. Consider
the clockwise leader election algorithm in the ring topology (graph).
1. Give an assignment of identifiers to the nodes for which O(n2) messages
are sent.
2. Give an assignment of identifiers to the nodes for which only O(n)
messages are sent.
Prove your claims.
8 [10 pts]
Consider a line graph with n vertices arranged consecutively on a line; for
example the graph below has n = 9
On each vertex add one of the arrows ← or →, arbitrariliy. For example, if
we assign arrows to the graph above we get the configuration,
On this last configuration flip the direction of the arrows by applying the
following flipping rule: (→←) =⇒ (←→).
1. [4 pts] Trace all the steps of the flipping rule in the line graph above and
draw a sequence of pictures of the transformations until termination.
2. [6 pts] (?) Show that for any line graph and any initial arrangement
of arrows the application of the flipping rule results in a terminating
arrangement. In particular,give a general proof which is valid for any
line graph of size n. Analyze its running time as a function of n.
4