Algorithms-1 10

Breaking symmetry

Let there be players. Our goal is to choose one (or rather let each player decide whether he is to be chosen or not). Let each player follow the exact same algorithm. Clearly, this algorithm cannot be deterministic, as all players will either all choose themselves or all not choose themselves. A possible solution is to let each player perform a trial with chance of success . We’d like only one player to succeed, to choose him.

LOCAL model of distributed computation

Let there be a distributed computation network graph with vertices. Each vertex is a computer and each edge is a connection. Each vertex has no unique ID and performs the exact same algorithm. The runtime is defined as the number of “rounds” Each round contains the following:

• Each vertex performs the local algorithms computation, we do not care about the cost of that algorithm. All computations are done in parallel.
• Each vertex can send messages of arbitrary size to its neighbors
• Each vertex can receive messages from its neighbors, but can only react in the next round(!)

What are the challenges?

• Vertices have no IDs, so they can’t pass a list of their neighbors to other vertices
• Vertex is unaware of what happens outside of its immediate state
• Vertices need to be synchronized somehow

LOCAL Random choice

Let each vertex choose an ID from What is the probability that there exist two vertices with the same ID?

What can we do? We can enlarge the interval! Let each vertex choose an ID from for some constant

Graph coloring problem

An iterative greedy algorithm can find a coloring of any graph in colors Let us examine a distributed algorithm that can color a graph in colors

---

Let us now calculate the probability that algorithm does terminate after iterations for