Las Vegas randomized algorithms in distributed consensus problems

We consider distributed consensus problems from the viewpoint of probabilistic algorithms. In particular, we provide an overview on some specific problems where randomization is critical in achieving consensus among multiple agents. Further, we show that the randomized algorithms which are used in this setting are the so-called Las Vegas randomized algorithms (e.g. [24]). This class is different from that of Monte Carlo type, which has been recently successfully employed for various computationally difficult problems in systems and control. The objective of this paper is therefore to show the link between various distributed consensus problems and randomized algorithms for systems and control.