Search Results

Documents authored by Cooper, Colin

Document
DOI: 10.4230/LIPIcs.OPODIS.2023.10
Discrete Incremental Voting

Authors: Colin Cooper, Tomasz Radzik, and Takeharu Shiraga

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
We consider a type of pull voting suitable for discrete numeric opinions which can be compared on a linear scale, for example, 1 ("disagree strongly"), 2 ("disagree"), …, 5 ("agree strongly"). On observing the opinion of a random neighbour, a vertex changes its opinion incrementally towards the value of the neighbour’s opinion, if different. For opinions drawn from a set {1,2,…,k}, the opinion of the vertex would change by +1 if the opinion of the neighbour is larger, or by -1, if it is smaller. It is not clear how to predict the outcome of this process, but we observe that the total weight of the system, that is, the sum of the individual opinions of all vertices, is a martingale. This allows us analyse the outcome of the process on some classes of dense expanders such as complete graphs K_n and random graphs G_{n,p} for suitably large p. If the average of the original opinions satisfies i ≤ c ≤ i+1 for some integer i, then the asymptotic probability that opinion i wins is i+1-c, and the probability that opinion i+1 wins is c-i. With high probability, the winning opinion cannot be other than i or i+1. To contrast this, we show that for a path and opinions 0,1,2 arranged initially in non-decreasing order along the path, the outcome is very different. Any of the opinions can win with constant probability, provided that each of the two extreme opinions 0 and 2 is initially supported by a constant fraction of vertices.
Cite as

Colin Cooper, Tomasz Radzik, and Takeharu Shiraga. Discrete Incremental Voting. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.OPODIS.2023.10,
  author =	{Cooper, Colin and Radzik, Tomasz and Shiraga, Takeharu},
  title =	{{Discrete Incremental Voting}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.10},
  URN =		{urn:nbn:de:0030-drops-195005},
  doi =		{10.4230/LIPIcs.OPODIS.2023.10},
  annote =	{Keywords: Random distributed processes, Pull voting}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.16
The Cover Time of a Biased Random Walk on a Random Cubic Graph

Authors: Colin Cooper, Alan Frieze, and Tony Johansson

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
We study a random walk that prefers to use unvisited edges in the context of random cubic graphs, i.e., graphs chosen uniformly at random from the set of 3-regular graphs. We establish asymptotically correct estimates for the vertex and edge cover times, these being n log n and 3/2 n log n respectively.
Cite as

Colin Cooper, Alan Frieze, and Tony Johansson. The Cover Time of a Biased Random Walk on a Random Cubic Graph. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.AofA.2018.16,
  author =	{Cooper, Colin and Frieze, Alan and Johansson, Tony},
  title =	{{The Cover Time of a Biased Random Walk on a Random Cubic Graph}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{16:1--16:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.16},
  URN =		{urn:nbn:de:0030-drops-89097},
  doi =		{10.4230/LIPIcs.AofA.2018.16},
  annote =	{Keywords: Random walk, random regular graph, cover time}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.13
Fast Plurality Consensus in Regular Expanders

Authors: Colin Cooper, Tomasz Radzik, Nicolás Rivera, and Takeharu Shiraga

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
In a voting process on a graph vertices revise their opinions in a distributed way based on the opinions of nearby vertices. The voting completes when the vertices reach consensus, that is, they all have the same opinion. The classic example is synchronous pull voting where at each step, each vertex adopts the opinion of a random neighbour. This very simple process, however, can be slow and the final opinion is not necessarily the one with the initial largest support. It was shown earlier that if there are initially only two opposing opinions, then both these drawbacks can be overcome by a synchronous two-sample voting, in which at each step each vertex considers its own opinion and the opinions of two random neighbours. If there are initially three or more opinions, a problem arises when there is no clear majority. One class of opinions may be largest (the plurality opinion), although its total size is less than that of two other opinions put together. We analyse the performance of the two-sample voting on d-regular graphs for this case. We show that, if the difference between the initial sizes A_1 and A_2 of the largest and second largest opinions is at least C n max{sqrt((log n)/A_1), lambda}, then the largest opinion wins in O((n log n)/A_1) steps with high probability. Here C is a suitable constant and lambda is the absolute second eigenvalue of transition matrix P=Adj(G)/d of a simple random walk on the graph G. Our bound generalizes the results of Becchetti et al. [SPAA 2014] for the related three-sample voting process on complete graphs. Our bound implies that if lambda = o(1), then the two-sample voting can consistently converge to the largest opinion, even if A_1 - A_2 = o(n). If lambda is constant, we show that the case A_1 - A_2 = o(n) can be dealt with by sampling using short random walks. Finally, we give a simple and efficient push voting algorithm for the case when there are a number of large opinions and any of them is acceptable as the final winning opinion.
Cite as

Colin Cooper, Tomasz Radzik, Nicolás Rivera, and Takeharu Shiraga. Fast Plurality Consensus in Regular Expanders. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.DISC.2017.13,
  author =	{Cooper, Colin and Radzik, Tomasz and Rivera, Nicol\'{a}s and Shiraga, Takeharu},
  title =	{{Fast Plurality Consensus in Regular Expanders}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.13},
  URN =		{urn:nbn:de:0030-drops-79778},
  doi =		{10.4230/LIPIcs.DISC.2017.13},
  annote =	{Keywords: Plurality consensus, Regular expanders}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.144
The Linear Voting Model

Authors: Colin Cooper and Nicolás Rivera

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We study voting models on graphs. In the beginning, the vertices of a given graph have some initial opinion. Over time, the opinions on the vertices change by interactions between graph neighbours. Under suitable conditions the system evolves to a state in which all vertices have the same opinion. In this work, we consider a new model of voting, called the Linear Voting Model. This model can be seen as a generalization of several models of voting, including among others, pull voting and push voting. One advantage of our model is that, even though it is very general, it has a rich structure making the analysis tractable. In particular we are able to solve the basic question about voting, the probability that certain opinion wins the poll, and furthermore, given appropriate conditions, we are able to bound the expected time until some opinion wins.
Cite as

Colin Cooper and Nicolás Rivera. The Linear Voting Model. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 144:1-144:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.ICALP.2016.144,
  author =	{Cooper, Colin and Rivera, Nicol\'{a}s},
  title =	{{The Linear Voting Model}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{144:1--144:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.144},
  URN =		{urn:nbn:de:0030-drops-62883},
  doi =		{10.4230/LIPIcs.ICALP.2016.144},
  annote =	{Keywords: Voter model, Interacting particles, Randomized algorithm, Probabilistic voting}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.145
Discordant Voting Processes on Finite Graphs

Authors: Colin Cooper, Martin Dyer, Alan Frieze, and Nicolás Rivera

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We consider an asynchronous voting process on graphs which we call discordant voting, and which can be described as follows. Initially each vertex holds one of two opinions, red or blue say. Neighbouring vertices with different opinions interact pairwise. After an interaction both vertices have the same colour. The quantity of interest is T, the time to reach consensus, i.e. the number of interactions needed for all vertices have the same colour. An edge whose endpoint colours differ (i.e. one vertex is coloured red and the other one blue) is said to be discordant. A vertex is discordant if its is incident with a discordant edge. In discordant voting, all interactions are based on discordant edges. Because the voting process is asynchronous there are several ways to update the colours of the interacting vertices. - Push: Pick a random discordant vertex and push its colour to a random discordant neighbour. - Pull: Pick a random discordant vertex and pull the colour of a random discordant neighbour. - Oblivious: Pick a random endpoint of a random discordant edge and push the colour to the other end point. We show that ET, the expected time to reach consensus, depends strongly on the underlying graph and the update rule. For connected graphs on n vertices, and an initial half red, half blue colouring the following hold. For oblivious voting, ET = (n^2)/4 independent of the underlying graph. For the complete graph Kn, the push protocol has ET = Theta(n*log(n)), whereas the pull protocol has ET = Theta(2^n). For the cycle C_n all three protocols have ET = Theta(n^2). For the star graph however, the pull protocol has ET = O(n^2), whereas the push protocol is slower with ET = Theta(n^2*log(n)). The wide variation in ET for the pull protocol is to be contrasted with the well known model of synchronous pull voting, for which ET = O(n) on many classes of expanders.
Cite as

Colin Cooper, Martin Dyer, Alan Frieze, and Nicolás Rivera. Discordant Voting Processes on Finite Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 145:1-145:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.ICALP.2016.145,
  author =	{Cooper, Colin and Dyer, Martin and Frieze, Alan and Rivera, Nicol\'{a}s},
  title =	{{Discordant Voting Processes on Finite Graphs}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{145:1--145:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.145},
  URN =		{urn:nbn:de:0030-drops-62898},
  doi =		{10.4230/LIPIcs.ICALP.2016.145},
  annote =	{Keywords: Distributed consensus, Voter model, Interacting particles, Randomized algorithm}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact