1.
Suppose you have a mesh network (see pg. 158 of the textbook) with n nodes where, in addition to the standard set of assumptions (bidirectional links,
total reliability, connectivity) there is orientation (i.e., the links are consistently labeled north, south,
east, west).
Design an algorithm to perform a wake-up with a unique initiator : all nodes are "asleep" except for the
initiator that is "awake"; all nodes must become "awake" within finite time;
any node could be the initiator).
IMPORTANT: your protocol must use exactly n-1 messages.
Describe the algorithm and write the pseudocode. Evaluate the message and time complexity,
and motivate your answer.
2.
Consider a ring network of n nodes, where each node has associated
a positive integer. At each node, one links is labeled left and the
other right.
Design an algorithm that, under the standard set of assumptions (bidirectional links,
total reliability, connectivity), determines the maximum
value in the ring assuming that there is a unique initiator.
Write the algorithm using the pseudo-code
seen in class. Derive its worst case message and time complexity.
PART II (group)
1. Collection Cost
The collection cost C(x) of node x in a tree T is the sum of
the distances from all the other nodes to x.
Given an arbitrary tree T with the standard set of assumptions (bidirectional links,
total reliability, connectivity) plus message ordering,
design an efficient algorithm to determine the node with smallest collection cost in T
and the corresponding collection cost.
Discuss the correctness of your algorithm and derive its message complexity.
(b) Identify the problem and all the restrictions (i.e. additional assumptions) used in the paper.
(c) Re-write the algorithm of the paper using the notation introduced in class (See Section 1.9.2 of
textbook).
(d) Write a report describing and explaining the context and the
content (i.e., the problems, the assumptions, the techniques,
the results) of the assigned paper (Beware: the paper might contain errors.).
Include the rewritten algorithm (point (c) above).
The report must contain all the descriptions, explanations, and details using the terminology seen in class.
Your assignment will be marked for clarity, accuracy, and
completeness in all aspects.