本次澳洲代写是一个分布式计算相关的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 identiers 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 identiers 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.