Symmetry Breaking - Meeting in a Ring - Management Assignment Help

Assignment Task:

Task:

Problem 1. (1 + )?-Colouring (10 Marks)
This is a simplification of the homework assignment problem on distributed (? + 1)- colouring. Recall that ? refers to the maximum degree of the network graph. Consider the (?+1)-colouring algorithm (in the CONGEST model) discussed in class but without the sleeping step, i.e., all vertices are awake in every step and pick a tentative colour uniformly at random from its list of colours. Additionally, each node starts with a colour palette of (1 + )? colours, where  > 0 is a fixed small constant.

Part 1.
Prove that this (1+)?-colouring algorithm (without the sleep step) will terminate (whp) within O(log n) rounds.

Problem 2. Meeting in a Ring (10 Marks)
Consider a ring comprising n ≥ 2 vertices, n being even. The vertices in the ring do not have any identifying feature. Each vertex has two ports marked clockwise and anticlock- wise leading to respective neighbouring vertices. There are two identical mobile agents placed at vertices that are at diametrically opposite ends; these agents do not have IDs or other uniquely identifiable feature. These two agents need to “meet” each other (i.e., reach the same vertex at the same time). At each round, the agents can take at most one step, i.e., either take one clockwise step or one anticlockwise step or stay in the current vertex. When they both land on the same vertex, they will know that they have met. When they cross each other on an edge, they will be able to sense that they have crossed each other, but note that they have not yet met.

Part 1.
Deterministic approaches with knowledge of n and distance oracle. For the moment, let us simplify the problem in the following ways. Both agents know the value of n. Moreover, at the end of each round, an oracle reveals to both agents the distance between them. Does there exist a deterministic algorithm? If yes, describe and analyse it. Otherwise, prove that a deterministic algorithm does not exist.

Page 4 of 6

Problem 2. Meeting in a Ring (10 Marks) (continued)

Part 2.
Randomized algorithm with knowledge of n and distance oracle. Let us continue for now with the assumptions that n is known to both agents and there is a distance oracle. Provide a randomized algorithm that ensures that the two agents meet (whp) within n + o(n) rounds.

Part 3.
Randomization with knowledge of n but no distance oracle. Now suppose there is no oracle informing the agents of the distance between them, but the agents do know the value of n. Design and analyse a randomized algorithm that ensures that the two agents meet within O(n log n) rounds (whp). Your algorithm must be very simple to state and analyse.

Part 4.
Randomization without knowledge of n and no distance oracle. Finally, we consider the case where the agents don’t know n and there is no oracle giving them distance information. Design and analyse a randomized algorithm that ensures that the two agents meet within O(n log n) rounds (whp).

Problem 3. Leader Election and MIS with Light Sig-nals (10 Marks)

Consider nodes that come with lights and light sensors, i.e., they can emit light and also detect if some neighbouring node is emitting light. The nodes operate in synchronous rounds. The following sequence of events occur within each round at every node. First, the node performs some local computation and decides whether to turn on the light or not. If it decides to turn on the light, it turns it on for a brief moment and simultaneously senses whether any of its neighbours turned on their lights. At the end of the round, all lights are turned off. Note that the sensors can detect whether some other node turned its light on or not, but it cannot decipher which nodes turned on their lights or even how many neighbours turned their lights on.

Problem 3. Leader Election and MIS with Light Signals (10 Marks) (continued)
Part 1.
Leader Election in a Complete Network. Consider n nodes that are all neighbours of each other. The nodes do not know the value of n. We wish to design an algorithm to elect a leader implicitly. Specifically, exactly one node must know that it is the leader and other must know that they are not leaders. What is the fastest algorithm to solve this leader election problem? Provide the algorithm and analyse its correctness and running time.

Part 2.
Max Independent Set (MIS) on an arbitrary network. Now suppose the network graph G is some arbitrary network. Design a fast MIS algorithm such that at the end every node knows whether it is in the MIS or not in the MIS. What is the fastest algorithm to solve this MIS problem? Provide the algorithm and analyse its correctness and running time.

This Management Assignment has been solved by our Management  Experts at My Uni Papers. Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+ Students in Australia, UK & US by helping them to score HD in their academics. Our Experts are well trained to follow all marking rubrics & referencing style.

Be it a used or new solution, the quality of the work submitted by our assignment experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed that you could choose one between the two and acquire an HD either way. You could choose a new assignment solution file to get yourself an exclusive, plagiarism (with free Turnitin file), expert quality assignment or order an old solution file that was considered worthy of the highest distinction.