Arrow Research search

Author name cluster

Colin Cooper

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

20 papers
2 author rows

Possible papers

20

SODA Conference 2025 Conference Paper

Asynchronous 3-Majority Dynamics with Many Opinions

  • Colin Cooper
  • Frederik Mallmann-Trenn
  • Tomasz Radzik
  • Nobutaka Shimizu
  • Takeharu Shiraga

We consider 3-Majority, a probabilistic consensus dynamics on a complete graph with n vertices, each vertex starting with one of k initial opinions. At each discrete time step, a vertex u is chosen uniformly at random. The selected vertex u chooses three neighbors v 1, v 2, v 3 uniformly at random with replacement and takes the majority opinion held by the three, where ties are broken in favor of the opinion of v 3. The main quantity of interest is the consensus time, the number of steps required for all vertices to hold the same opinion. This asynchronous version turns out to be considerably harder to analyze than the synchronous version and so far results have only been obtained for k = 2. Even in the synchronous version the results for large k are far from tight. In this paper we prove that the consensus time is for all k. These are the first bounds for all k that are tight up to a polylogarithmic factor.

Details

UAI Conference 2022 Conference Paper

On early extinction and the effect of travelling in the SIR model

  • Petra Berenbrink
  • Colin Cooper
  • Cristina Gava
  • David Kohan Marzagão
  • Frederik Mallmann-Trenn
  • Tomasz Radzik

We consider a population protocol version of the SIR model. In every round, an individual is chosen uniformly at random. If the individual is susceptible, then it becomes infected w. p. $\beta I_t/N$, where $I_t$ is the number of infections at time $t$ and $N$ is the total number of individuals. If the individual is infected, then it recovers w. p. $\gamma$, whereas, if the individual is already recovered, nothing happens. We prove sharp bounds on the probability of the disease becoming pandemic vs extinguishing early (dying out quickly). The probability of extinguishing early, $\Pr{\mathcal{E}_{ext}}$, is typically neglected in prior work since most use (deterministic) differential equations. Leveraging on this, using $\Pr{\mathcal{E}_{ext}}$, we proceed by bounding the expected size of the population that contracts the disease $\mathbf{E}\left[R_\infty\right]$. Prior work only calculated $\mathbf{E}\left[R_\infty | \overline{\mathcal{E}_{ext}}\right]$, or obtained non-closed form solutions. We then study the two-country model also accounting for the role of $\Pr{\mathcal{E}_{ext}}$. We assume that both countries have different infection rates $\beta^{(i)}$, but share the same recovery rate $\gamma$. In this model, each round has two steps: First, an individual is chosen u. a. r. and travels w. p. $p_{travel}$ to the other country. Afterwards, the process continues as before with the respective infection rates. Finally, using simulations, we characterise the influence of $p_{travel}$ on the total number of infections. Our simulations show that, depending on the $\beta^{(i)}$, increasing $p_{travel}$ can decrease or increase the expected total number of infections $\mathbf{E}\left[R_\infty\right]$.

Details

SODA Conference 2019 Conference Paper

On the rank of a random binary matrix

  • Colin Cooper
  • Alan M. Frieze
  • Wesley Pegden

We study the rank of a random n × m matrix A n, m; k with entries from GF (2), and exactly k unit entries in each column, the other entries being zero. The columns are chosen independently and uniformly at random from the set of all ( n k ) such columns. We obtain an asymptotically correct estimate for the rank as a function of the number of columns m in terms of c, n, k, and where m = cn/k. The matrix A n, m; k forms the vertex-edge incidence matrix of a k -uniform random hypergraph H. The rank of A n, m; k can be expressed as follows. Let | C 2 | be the number of vertices of the 2-core of H, and | E ( C 2 )| the number of edges. Let m* be the value of m for which | C 2 | = | E ( C 2 )|. Then w. h. p. for m < m * the rank of A n, m; k is asymptotic to m, and for m ≥ m * the rank is asymptotic to m – | E ( C 2 )| + | C 2 |. In addition, assign i. i. d. U [0, 1] weights X i, i ∊ 1, 2, … m to the columns, and define the weight of a set of columns S as X ( S ) = ∑ j ∊ S X j. Define a basis as a set of n – 1 ( k even) linearly independent columns. We obtain an asymptotically correct estimate for the minimum weight basis. This generalises the well-known result of Frieze [On the value of a random minimum spanning tree problem, Discrete Applied Mathematics, (1985)] that, for k = 2, the expected length of a minimum weight spanning tree tends to ζ(3) ∼ 1. 202.

Details

I&C Journal 2017 Journal Article

Constructing self-stabilizing oscillators in population protocols

  • Colin Cooper
  • Anissa Lamani
  • Giovanni Viglietta
  • Masafumi Yamashita
  • Yukiko Yamauchi

We consider the population protocol (PP) model used to represent a collection of finite-state mobile agents that interact with each other to accomplish a common task. Motivated by the well-known BZ reaction, we address the problem of autonomously generating an oscillatory execution from any initial configuration (i. e. , in a self-stabilizing manner). For deterministic PPs under a deterministic scheduler, we show that the self-stabilizing leader election (SS-LE) problem and the self-stabilizing oscillation (SS-OS) problem are equivalent, in the sense that an SS-OS protocol is constructible from a given SS-LE protocol, and vice versa, which unfortunately implies that (1) resorting to a leader is inevitable (although we seek a decentralized solution), (2) n states are necessary to create oscillations of amplitude n, where n is the number of agents (although we seek a memory-efficient solution). Aiming at reducing the space complexity, we present some deterministic oscillatory PPs under a uniform random scheduler.

Details DOI

AAMAS Conference 2017 Conference Paper

Multi-Agent Flag Coordination Games

  • David Kohan Marzag&atilde; o
  • Nicol&aacute; s Rivera
  • Colin Cooper
  • Peter McBurney
  • Kathleen Steinh&ouml; fel

Many multi-agent coordination problems can be understood as autonomous local choices between a finite set of options, with each local choice undertaken simultaneously without explicit coordination between decision-makers, and with a shared goal of achieving a desired global state or states. Examples of such problems include classic consensus problems between nodes in a distributed computer network and the adoption of competing technology standards. We model such problems as a multi-round game between agents having flags of different colours to represent the finite choice options, and all agents seeking to achieve global patterns of colours through a succession of local colour-selection choices. We generalise and formalise the problem, proving results for the probabilities of achievement of common desired global states when these games are undertaken on bipartite graphs, extending known results for non-bipartite graphs. We also calculate probabilities for the game entering infinite cycles of non-convergence. In addition, we present a game-theoretic approach to the problem that has a mixed-strategy Nash equilibrium where two players can simultaneously flip the colour of one of the opponent’s nodes in the bipartite graph before or during a flag-coordination game.

PDF

TCS Journal 2013 Journal Article

The cover times of random walks on random uniform hypergraphs

  • Colin Cooper
  • Alan Frieze
  • Tomasz Radzik

Random walks in graphs have been applied to various network exploration and network maintenance problems. In some applications, however, it may be more natural, and more accurate, to model the underlying network not as a graph but as a hypergraph, and solutions based on random walks require a notion of random walks in hypergraphs. At each step, a random walk on a hypergraph moves from its current position v to a random vertex in a randomly selected hyperedge containing v. We consider two definitions of cover time of a hypergraph H. If the walk sees only the vertices it moves between, then the usual definition of cover time, C ( H ), applies. If the walk sees the complete edge during the transition, then an alternative definition of cover time, the inform time I ( H ) is used. The notion of inform time models passive listening which fits the following types of situations. The particle is a rumour passing between friends, which is overheard by other friends present in the group at the same time. The particle is a message transmitted randomly from location to location by a directional transmission in an ad-hoc network, but all receivers within the transmission range can hear. In this paper we give an expression for C ( H ) which is tractable for many classes of hypergraphs, and calculate C ( H ) and I ( H ) exactly for random r -regular, s -uniform hypergraphs. We find that for such hypergraphs, whp, C ( H ) / I ( H ) ∼ s ( r − 1 ) / r, if r s = O ( ( log log n ) 1 − ϵ ). For random r -regular, s -uniform multi-hypergraphs, constant r ≥ 2, and 3 ≤ s ≤ O ( n ϵ ), we also prove that, whp, I ( H ) = O ( ( n / s ) log n ), i. e. the inform time decreases directly with the edge size s.

Details DOI

TCS Journal 2010 Journal Article

Locating and repairing faults in a network with mobile agents

  • Colin Cooper
  • Ralf Klasing
  • Tomasz Radzik

We consider a fixed, undirected, known network and a number of “mobile agents” which can traverse the network in synchronised steps. Some nodes in the network may be faulty and the agents are to find the faults and repair them. The agents could be software agents, if the underlying network represents a computer network, or robots, if the underlying network represents some potentially hazardous physical terrain. Assuming that the first agent encountering a faulty node can immediately repair it, it is easy to see that the number of steps necessary and sufficient to complete this task is Θ ( n / k + D ), where n is the number of nodes in the network, D is the diameter of the network, and k is the number of agents. We consider the case where one agent can repair only one faulty node. After repairing the fault, the agent dies. We show that a simple deterministic algorithm for this problem terminates within O ( n / k + D log f / log log f ) steps, where f = min { n / k, n / D }, assuming that the number of faulty nodes is at most k / 2. We also demonstrate the worst-case asymptotic optimality of this algorithm by showing a network such that for any deterministic algorithm, there is a placement of k / 2 faults forcing the algorithm to work for Ω ( n / k + D log f / log log f ) steps.

Details DOI

TCS Journal 2009 Journal Article

Energy efficient randomised communication in unknown AdHoc networks

  • Petra Berenbrink
  • Colin Cooper
  • Zengjian Hu

This paper studies broadcasting and gossiping algorithms in random and general AdHoc networks. Our goal is not only to minimise the broadcasting and gossiping time, but also to minimise the energy consumption, which is measured in terms of the total number of messages (or transmissions) sent. We assume that the nodes of the network do not know the network, and that they can only send with a fixed power, meaning they can not adjust the area sizes that their messages cover. We believe that under these circumstances the number of transmissions is a very good measure for the overall energy consumption. For random networks, we present a broadcasting algorithm where every node transmits at most once. We show that our algorithm broadcasts in O ( log n ) steps, w. h. p. , where n is the number of nodes. We then present a O ( d log n ) ( d is the expected degree) gossiping algorithm using O ( log n ) messages per node. For general networks with known diameter D, we present a randomised broadcasting algorithm with optimal broadcasting time O ( D log ( n / D ) + log 2 n ) that uses an expected number of O ( log 2 n / log ( n / D ) ) transmissions per node. We also show a tradeoff result between the broadcasting time and the number of transmissions: we construct a network such that any oblivious algorithm using a time-invariant distribution requires Ω ( log 2 n / log ( n / D ) ) messages per node in order to finish broadcasting in optimal time. This demonstrates the tightness of our upper bound. We also show that no oblivious algorithm can complete broadcasting w. h. p. using o ( log n ) messages per node.

Details DOI

TCS Journal 2008 Journal Article

A randomized algorithm for the joining protocol in dynamic distributed networks

  • Colin Cooper
  • Ralf Klasing
  • Tomasz Radzik

We describe a randomized algorithm for assigning neighbours to vertices joining a dynamic distributed network. The aim of the algorithm is to maintain connectivity, low diameter and constant vertex degree. On joining each vertex donates a constant number of tokens to the network. These tokens contain the address of the donor vertex. The tokens make independent random walks in the network. A token can be used by any vertex it is visiting to establish a connection to the donor vertex. This allows joining vertices to be allocated a random set of neighbours although the overall vertex membership of the network is unknown. The network we obtain in this way is robust under adversarial deletion of vertices and edges and actively reconnects itself. One model we consider is a network constructed in this fashion, in which vertices join but never leave. If t is the size of the network, then the diameter of the network is O ( log t ) for all t, with high probability. As an example of the robustness of this model, suppose an adversary deletes edges from the network leaving components of size at least t 1 / 2 + δ. With high probability the network reconnects itself by replacing lost edges using tokens from the token pool.

Details DOI