# BEST代写-线上编程学术专家

Best代写-最专业靠谱代写IT | CS | 留学生作业 | 编程代写Java | Python |C/C++ | PHP | Matlab | Assignment Project Homework代写

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

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

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 2

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 identi ers to the nodes for which O(n2
) messages are sent. Draw a picture of the assignment and prove your claim.

2. Give an assignment of identi ers to the nodes for which only O(n)
messages are sent. Draw a picture of the assignment and prove your
claim.

2 [10 pts]Consider robots which can move in a cycle of unit length. The robots may
move anywhere and in any direction. If robot r with energy e moves distance
x it will consume energy equal to x and its energy will be reduced from e to
e x. Robots with 0 energy cannot move. Robots can exchange and transfer
any amount of their available energy to each other.

1. [5 pts] Assume two mobile robots r0; r1 are placed at arbitrary loca-
tions anywhere on a cycle of unit length. Robot ri initially possesses
energy ei, where ei  0. The total energy of the two robots is e0 + e1.
Show that if e0 + e1  1 then one of the two robots can traverse the

2. [5 pts] Extend the previous result to three robots. I.e., assume three
mobile robots r0; r1; r2 are placed at arbitrary locations anywhere on
a cycle of unit length. Robot ri initially possesses energy ei, where
ei  0. The total energy of the three robots is e0 + e1 + e2. Show that
if e0 + e1 + e2  1 then one of the three robots can traverse the whole 