We study the Undecided-State Dynamics (USD), a fundamental consensus process in which each vertex holds one of k decided opinions or the undecided state. We consider both the gossip model and the population protocol model. Prior work established tight bounds on the consensus time of this process only for the regime k=O(n/(log⁡n)2) (for the population protocol model) and k = O((n/log n)1/3) (for the gossip model), often under restrictive assumptions on the initial configuration.

The discrete incremental voting process (DIV), introduced by Cooper, Radzik, and Shiraga [OPODIS '23], operates on an undirected graph where each node has an integer opinion. In one step a randomly selected node interacts with its randomly selected neighbor and changes its opinion by 1 towards the neighbor's opinion. The final consensus opinion has expectation equal to the degree-weighted average of the initial opinions. We show that for graphs with n nodes, conductance Φ, and the ratio of the average to smallest degree γ, if the maximal difference between initial opinions is K, then the expected convergence time is O(n (K log(Kn) + γn)/Φ2). This bound is essentially optimal for graphs of bounded expansion. We also show that for regular graphs, if the second largest eigenvalue (in absolute value) is o(1/log2 n) and K is o(n/log2 n), then w.h.p. DIV converges to the rounded initial average opinion.

Given a graph G , and an ordering π of its vertices, a permutation forest F ( G , π ) is a spanning forest of G whose components are obtained as follows. For each vertex v , connect v to its first neighbour w in G that appears after v in the ordering π . If we regard this edge ( v , w ) as directed forward, from v to w , then each vertex has at most one forward edge, and the components of F ( G , π ) are arborescences. The roots of the components formed by this process are those vertices of G with no forward edge in the ordering π . This paper shows that the permutation forests of the random graphs G n , p have a threshold for the emergence of a linear size component around p = 1 / n . In contrast to the w.h.p. emergence of a unique giant in G n , p , the permutation forest process has the unusual property that, with positive probability, a number of linear size components occur within the threshold window.

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 v1, v2, v3 uniformly at random with replacement and takes the majority opinion held by the three, where ties are broken in favor of the opinion of v3. 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.

We consider the single-machine time-dependent scheduling problem with linearly deteriorating jobs arriving over time. Each job i is associated with a release time ri and a processing time pi(si)=αi+βisi, where αi,βi>0 are parameters and si is the job's start time. In this setting, the approximability of both single-machine minimum makespan and total completion time problems remains open. We develop new bounds and approximation results for the special case of the problems with uniform deterioration, i.e. βi=β, for each i. The main contribution is a O(1+1/β)-approximation algorithm for the makespan problem and a O(1+1/β2) approximation algorithm for the total completion time problem. Further, we propose greedy constant-factor approximation algorithms for instances with β=O(1/n) and β=Ω(n), where n is the number of jobs. Our analysis is based on an approach for comparing computed and optimal schedules via bounding pseudomatchings.

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.

We consider two simple asynchronous opinion dynamics on arbitrary graphs where every node u of the graph has an initial value ξu(0). In the first process, which we call the NodeModel, at each time step t ≥ 0, a random node u and a random sample of k of its neighbours υ1, υ2, ... , υk are selected. Then, u updates its current value ξu(t) to [EQUATION], where α ∈ (0, 1) and k ≥ 1 are parameters of the process. In the second process, called the EdgeModel, at each step a random pair of adjacent nodes (u, υ) is selected, and then node u updates its value equivalently to the NodeModel with k = 1 and υ as the selected neighbour.

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.

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]$.

Abstract Population protocols are a model for distributed computing that is focused on simplicity and robustness. A system of n identical agents (finite state machines) performs a global task like electing a unique leader or determining the majority opinion when each agent has one of two opinions. Agents communicate in pairwise interactions with randomly assigned communication partners. Quality is measured in two ways: the number of interactions to complete the task and the number of states per agent. We present protocols for the majority problem that allow for a trade-off between these two measures. Compared to the only other trade-off result (Alistarh et al. in Proceedings of the 2015 ACM symposium on principles of distributed computing, Donostia-San Sebastián, 2015), we improve the number of interactions by almost a linear factor. Furthermore, our protocols can be made uniform (working correctly without any information on the population size n), yielding the first uniform majority protocols that stabilize in a subquadratic number of interactions.

We consider the problem of counting the population size in the population model. In this model, we are given a distributed system of n identical agents which interact in pairs with the goal to solve a common task. In each time step, the two interacting agents are selected uniformly at random. In this paper, we consider so-called uniform protocols, where the actions of two agents upon an interaction may not depend on the population size n. We present two population protocols to count the size of the population: protocol Approximate, which computes with high probability either [log n] or [log n], and protocol CountExact, which computes the exact population size in optimal O(log n) interactions, using Õ (n) states. Both protocols can also be converted to stable protocols that give a correct result with probability 1 by using an additional multiplicative factor of O(log n) states.

We consider the classical broadcast problem in ad-hoc (that is, unknown topology) directed radio networks with no collision detection, under the additional assumption that at most h transmissions (shots) are available per node. We focus on adaptive deterministic protocols for small values of h. We provide asymptotically matching lower and upper bounds for the cases h=2 and h=3. While for h=2 our bound is quadratic, similar to the bound obtained for oblivious protocols, for h=3 we prove a sub-quadratic bound of Theta(n^2 log log n / log n), where n is the number of nodes in the network. The latter is the first result showing an adaptive algorithm which is asymptotically faster than oblivious h-shot broadcast protocols, for which a tight quadratic bound is known for every constant h. Our upper bound for h=3 is constructive, making use of constructions of graphs with large girth. We also show an improved upper bound of O(n^(1+alpha/sqrt{h})) for h >= 4, where alpha is an absolute constant independent of h. Our upper bound for h >= 4 is non-constructive.

A population protocol can be viewed as a sequence of pairwise interactions of $n$ agents (nodes). During one interaction, two agents selected uniformly at random update their states by applying a specified deterministic transition function. In a long run, the whole system should stabilize at the correct output property. The main performance objectives in designing population protocols are small number of states per agent and fast stabilization time. We present a fast population protocol for the exact-majority problem which uses $Θ(\log n)$ states (per agent) and stabilizes in $O(\log^{5/3} n)$ parallel time (i.e., $O(n\log^{5/3} n)$ interactions) in expectation and with high probability. Alistarh et al. [SODA 2018] showed that any exact-majority protocol which stabilizes in expected $O(n^{1-ε})$ parallel time, for any constant $ε> 0$, requires $Ω(\log n)$ states. They also showed an $O(\log^2 n)$-time protocol with $O(\log n)$ states, the currently fastest exact-majority protocol with polylogarithmic number of states. The standard design framework for majority protocols is based on $O(\log n)$ phases and requires that all nodes are well synchronized within each phase, leading naturally to upper bounds of the order of at least $\log^2 n$ because of $Θ(\log n)$ synchronization time per phase. We show how this framework can be tightened with {\em weak synchronization} to break the $O(\log^2 n)$ upper bound of previous protocols.

We consider the model of population protocols, which can be viewed as a sequence of random pairwise interactions of n agents (nodes). During each interaction, two agents v and w selected uniformly at random update their states on the basis of their current states, and the whole system should in long run converge towards a desired global final configuration. We study population protocols for two problems: the leader election and the exact majority voting. Both protocols use Θ(log2 n) states per agent and run in O(log2 n) rounds (the number of interactions divided by n), w.h.p. and in expectation, improving on the running time of the Θ(log2 n)-state protocols proposed recently by Alistarh et al. [SODA 2017]. Our protocols are based on the idea of agents counting their local interactions and rely on the probabilistic fact that the uniform random selection would limit the divergence of the individual counts.

We present improved bounds on the cover time of the coalescing-branching random walk process COBRA. The COBRA process, introduced in [Dutta et al., SPAA 2013], can be viewed as spreading a single item of information throughout an undirected graph in synchronised rounds. In each round, each vertex which has received the information in the previous round (possibly simultaneously from more than one neighbour and possibly not for the first time), 'pushes' the information to b randomly selected neighbours. The COBRA process is typically studied for integer branching rates b \ge 2 (with the case b=1 corresponding to a random walk). The aim of the process is to propagate the information quickly, but with a limited number of transmissions per vertex per round.

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.

Information propagation on graphs is a fundamental topic in distributed computing. One of the simplest models of information propagation is the push protocol in which at each round each agent independently pushes the current knowledge to a random neighbour. In this paper we study the so-called coalescing-branching random walk (COBRA), in which each vertex pushes the information to k randomly selected neighbours and then stops passing information until it receives the information again. The aim of COBRA is to propagate information fast but with a limited number of transmissions per vertex per step. In this paper we study the cover time of the COBRA process defined as the minimum time until each vertex has received the information at least once. Our main result says that if G is an n-vertex r-regular graph whose transition matrix has second eigenvalue λ, then the COBRA cover time of G is O(log n), if 1-λ is greater than a positive constant, and O((log n)/(1-λ)3)), if 1-λ >> √log (i>n)/n}. These bounds are independent of r and hold for 3 ≤ r ≤ n-1. They improve the previous bound of O(log2 n) for expander graphs [Dutta et al., SPAA 2013].

In a coalescing random walk, a set of particles make independent discrete-time random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, which then continues a random walk through the graph. Let $G=(V,E)$ be an undirected and connected graph with $n$ vertices and $m$ edges. The coalescence time, $C(n)$, is the expected time for all particles to coalesce, when initially one particle is located at each vertex. We study the problem of bounding the coalescence time for general connected graphs and prove that $C(n) = O\big(\frac{1}{1-\lambda_2}\big(\log^{4} n + \frac{n}{\nu}\big)\big)$. Here $\lambda_2$ is the second eigenvalue of the transition matrix of the random walk. To avoid problems arising from, e.g., lack of coalescence on bipartite graphs, we assume the random walk can be made lazy if required. The value of $\nu$ is given by $\nu= \sum_{v\in V} d^2(v)/(d^2n)$, where $d(v)$ is the degree of vertex $v$, and $d=2m/n$ is the average degree. The parameter $\nu$ is an indicator of the variability of vertex degrees: $1 \le \nu = O(n)$, with $\nu=1$ for regular graphs. Our general bound on $C(n)$ holds for all connected graphs. This implies, for example, that $C(n)=O(n/(1-\lambda_2))$ for $d$-regular graphs with expansion parameterized by the eigenvalue gap $1-\lambda_2$. The bound on $C(n)$ given above is sublinear for some classes of graphs with skewed degree distributions. In the voter model, initially each vertex has a distinct opinion, and at each step each vertex changes its opinion to that of a random neighbor. Let ${\mathbf{E}} (C_{{\mbox{\boldmath$v$}}})$ be the expected time for voting to complete, that is, for a unique opinion to emerge. A system of coalescing particles, where initially one particle is located at each vertex, corresponds to the voter model in that $\mathbf{E}(C_{{\mbox{\boldmath$v$}}})=C(n)$. Thus our result stated above for $C(n)$ also gives general bounds for $\mathbf{E}(C_{{\mbox{\boldmath$v$}}})$.

In a coalescing random walk, a set of particles make independent discrete-time random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, which then continues the random walk through the graph. Coalescing random walks can be used to achieve consensus in distributed networks, and is the basis of the self-stabilizing mutual exclusion algorithm of Israeli and Jalfon [14].

We consider the task of network exploration by a mobile agent (robot) with small memory. The agent has to traverse all nodes and edges of a network (represented as an undirected connected graph), and return to the starting node. Nodes of the network are unlabeled and edge ports are locally labeled at each node. The agent has no a priori knowledge of the topology of the network or of its size, and cannot mark nodes in any way. Under such weak assumptions, cycles in the network may prevent feasibility of exploration, hence we restrict attention to trees. We present an algorithm to accomplish tree exploration (with return) using O (log n )-bit memory for all n -node trees. This strengthens the result from Diks et al. [2004], where O (log 2 n )-bit memory was used for tree exploration, and matches the lower bound on memory size proved there. We also extend our O (log n )-bit memory traversal mechanism to a weaker model in which ports at each node are ordered in circular manner, however, the explicit values of port numbers are not available.

We consider the following marking process (rw-rand) made by a random walk on an undirected graph G. Upon arrival at a vertex v, it marks v if unmarked and otherwise it marks a randomly chosen unmarked neighbor of v. We also consider a variant of this process called rw-r-rank. Here each vertex is assigned a global random rank first and then in each step, the walk marks the lowest ranked unmarked neighbor of the currently visited vertex. Depending on the degree and the expansion of the graph, we prove several upper bounds on the time required by these processes to mark all vertices. For instance, if G is a hypercube or random graph, our processes mark all vertices in time O(n), significantly speeding up the Θ(n log n)-cover time of standard random walks.

We study properties of multiple random walks on a graph under various assumptions of interaction between the particles. To give precise results, we make the analysis for random regular graphs. The cover time of a random walk on a random r-regular graph was studied in [C. Cooper and A. Frieze, SIAM J. Discrete Math., 18 (2005), pp. 728–740], where it was shown with high probability (whp) that for $r\geq3$ the cover time is asymptotic to $\theta_r n\ln n$, where $\theta_r=(r-1)/(r-2)$. In this paper we prove the following (whp) results, arising from the study of multiple random walks on a random regular graph G. For k independent walks on G, the cover time $C_G(k)$ is asymptotic to $C_G/k$, where $C_G$ is the cover time of a single walk. For most starting positions, the expected number of steps before any of the walks meet is $\theta_r n/\binom{k}{2}$. If the walks can communicate when meeting at a vertex, we show that, for most starting positions, the expected time for k walks to broadcast a single piece of information to each other is asymptotic to $\frac{2\ln k}{k}\theta_r n$ as $k,n\rightarrow\infty$. We also establish properties of walks where there are two types of particles, predator and prey, or where particles interact when they meet at a vertex by coalescing or by annihilating each other. For example, the expected extinction time of k explosive particles (k even) tends to $(2\ln2)\theta_r n$ as $k\rightarrow\infty$. The case of n coalescing particles, where one particle is initially located at each vertex, corresponds to a voter model defined as follows: Initially each vertex has a distinct opinion, and at each step each vertex changes its opinion to that of a random neighbor. The expected time for a unique opinion to emerge is the same as the expected time for all the particles to coalesce, which is asymptotic to $2\theta_r n$. Combining results from the predator-prey and multiple random walk models allows us to compare expected detection times of all prey in the following scenarios: Both the predator and the prey move randomly, the prey moves randomly and the predators stay fixed, and the predators move randomly and the prey stays fixed. In all cases, with k predators and $\ell$ prey the expected detection time is $\theta_r H_{\ell}n/k$, where $H_{\ell}$ is the $\ell$th harmonic number.

Abstract A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is the task of locating all black holes in a network, through the exploration of its nodes by a set of mobile agents. In this article we consider the problem of designing the fastest Black Hole Search, given the map of the network, the starting node and a subset of nodes of the network initially known to be safe. We study the version of this problem that assumes that there is at most one black hole in the network and there are two agents, which move in synchronized steps. We prove that this problem is not polynomial‐time approximable within any constant factor less than$389 \over 388$ (unlessP=NP). We give a 6‐approximation algorithm, thus improving on the 9.3‐approximation algorithm from (Czyzowicz et al., Fundamenta Informaticae 71 (2006), 229–242). We also prove APX‐hardness for a restricted version of the problem, in which only the starting node is initially known to be safe. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

We consider the generalized network flow problem. Each arc e in the network has a gain factor /spl gamma/(e). If f(e) units of flow enter arc e, then f(e)/spl gamma/(e) units arrive at the other end of e. The generalized network flow problem is to maximize the net flow into one specific node, the sink. We give an algorithm which solves this problem in O/spl tilde/(m/sup 2/(m+nloglog B)log B) time, where B is the largest integer used to represent the gain factors, the capacities, and the initial supplies at the nodes. If m is O(n/sup (4/3/-/spl epsiv/) and B is not extremely large, then our bound improves the previous best bound O(m/sup 1.5/n/sup 2/log B) given by P.M. Vaidya (1989). Our algorithm is an approximation scheme which in each iteration reduces by a constant factor the difference between the current net flow into the sink and the optimal one. The solution which is within a factor of 1+/spl xi/ from the optimum can be computed in O/spl tilde/(m/sup 2/n+min{m/sup 2/n, m(m+nloglog B)}log(1//spl xi/)) time. This improves the previous bounds on the approximate generalized flow problem.>

The authors considers Newton's method for the linear fractional combinatorial optimization. He proves a strongly polynomial bound on the number of iterations for the general case. He considers the maximum mean-weight cut problem, which is a special case of the linear fractional combinatorial optimization. This problem is closely related to the parametric flow problem and the flow problem when the maximum arc cost is being minimised. He proves that Newton's method runs in O(m) iterations for the maximum mean-weight cut problem. One iteration is dominated by the maximum flow computation. This gives the best known strongly polynomial bound of O(m/sup 2/n) for all three problems mentioned.>