程序代写 Exercise 1 – cscodehelp代写

Exercise 1
6CCS3AIN – Week 9
Part B: Voter Model Exercises and Solutions (version 1.0)
Find a graph for which the voter model protocol may never reach consensus, i.e., the process may encounter a deadlock.
Solution to Exercise 1
An undirected graph G = (V, E) allows for deadlocks if and only if G is bipartite. G is bipartite if and only if V can be divided in two parts, V1 and V2, such that any edge in E connects a node in V1 to a node in V2. In other words, no edge is ¡°inside¡± V1 or V2.
Note that this is only true for connected graphs.
It is an interesting exercise to prove that processes on non-bipartite graphs cannot reach a deadlocks. A more general solution for this problem (for directed graphs) is proven in Lemma 1 of this paper: http: //www.tafa-workshop.org/tafa-17/papers/TAFA-17_paper_16.pdf
Exercise 2
Consider a consensus process between colours blue e purple taking place in the graph depicted in Figure 1.
a) Determine P r(Send = purple | S0 = s).
b) Assume you are an external agent trying to influence this game in order for blue to be (strictly) more likely to win than not. You power is to magically flip the colour of one or more nodes. This change would happen before the process start, i.e., before any decision is made. What is the minimum number of purple nodes that need to be changed to blue take makes blue more than 50% likely to win? Which node(s) should be changed?
Solution to Exercise 2
a) The probability we are looking for the given by the sum of the number of edges connected to purple nodes in this initial round divided by the sum of all degrees.
Pr(Send =purple|S0 =s)= 3+3+2+4+3 = 15 24 24
b) It is enough to flip the colour of v6 from purple to blue for the probability of blue to win be given by 4+5+4 = 13 > 50%
24 24
1

v3
v4
v2 v5 v6
v7
v1
Figure 1: An initial configuration S0 = s.
2