2023年11月25日

分布式计算算法代写 | COMP 4001 DISTRIBUTED COMPUTING

本次加拿大作业是一个分布式计算相关的算法代写assignment

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.

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 if 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 f1; : : : ; !(G)g if the oor baIc of aI is even, and uses a
color in f!(G)+1; : : : ; 2!(G)g if the oor 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?

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 con gurations.

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.