本次澳洲代写是一个分布式计算相关的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 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
whole cycle and return to its starting position.

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
cycle and return to its starting position.

Algorithms for which there is a robot traversal using no more energy than
the length of the graph are called energy optimal.