Exercise 1
6CCS3AIN – Week 9
Part B: Voter Model Exercises (version 1.0)
Find a graph for which the voter model protocol may never reach consensus, i.e., the process may encounter a deadlock.
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?
v3
v4
v2 v5 v6
v7
v1
Figure 1: An initial configuration S0 = s.
1