We study simple dynamics in the population protocol model, in which n agents start with totally ordered initial opinions x1, x2, …, xn and, in each round, a randomly chosen agent changes its opinion as a function of the opinion of other randomly chosen agents. Such dynamics often converge to consensus on a single fixation value X^. This paper asks how to control the distribution of X^ as a randomised choice among the initial opinions by designing suitable simple dynamics. Writing the sorted initial values as x(1) ≤ … ≤ x(n), we design two protocols that realise natural target laws over order statistics.

We study the plurality consensus problem in distributed systems where a population of extremely simple agents, each initially holding one of k opinions, aims to agree on the initially most frequent one. In this setting, h-Majority is arguably the simplest and most studied protocol, in which each agent samples the opinion of h neighbors uniformly at random and updates its opinion to the most frequent value in the sample.

A randomized distributed algorithm called RAES was introduced in [Becchetti et al., 2020] to extract a bounded-degree expander from a dense n-vertex expander graph G = (V, E). The algorithm relies on a simple threshold-based procedure. A key assumption in [Becchetti et al., 2020] is that the input graph G is static - i.e., both its vertex set V and edge set E remain unchanged throughout the process - while the analysis of raes in dynamic models is left as a major open question. In this work, we investigate the behavior of RAES under a dynamic graph model induced by a streaming node-churn process (also known as the sliding window model), where, at each discrete round, a new node joins the graph and the oldest node departs. This process yields a bounded-degree dynamic graph 𝒢 = {G_t = (V_t, E_t) : t ∈ ℕ} that captures essential characteristics of peer-to-peer networks - specifically, node churn and threshold on the number of connections each node can manage. We prove that every snapshot G_t in the dynamic graph sequence has good expansion properties with high probability. Furthermore, we leverage this property to establish a logarithmic upper bound on the completion time of the well-known PUSH and PULL rumor spreading protocols over the dynamic graph 𝒢.

Boczkowski et al. (2018) considered the noisy PULL(h) model on the complete graph, where in each parallel round, every agent passively receives observations of the messages held by h randomly chosen agents, and where each message can be viewed as any other message in the alphabet ∑ with probability δ. The authors proved that in this model, the basic task of propagating a bit value from a single source to the whole population requires [EQUATION] rounds. The current work shows that the aforementioned lower bound is almost tight. We present two simple and efficient protocols that remain effective even in the presence of multiple conflicting sources, and quickly converge to their plurality opinion. Our first protocol operates with any alphabet of size at least two. Our second protocol, while slightly less efficient and requiring an alphabet of size four, is self-stabilizing. Overall, our results demonstrate how increasing the sample size can compensate for the lack of communication structure by linearly accelerating information spread.

We present the first upper bound on the convergence time to consensus of the well-known $h$-majority dynamics with $k$ opinions, in the synchronous setting, for $h$ and $k$ that are both non-constant values. We suppose that, at the beginning of the process, there is some initial additive bias towards some plurality opinion, that is, there is an opinion that is supported by $x$ nodes while any other opinion is supported by strictly fewer nodes. We prove that, with high probability, if the bias is $ω(\sqrt{x})$ and the initial plurality opinion is supported by at least $x = ω(\log n)$ nodes, then the process converges to plurality consensus in $O(\log n)$ rounds whenever $h = ω(n \log n / x)$. A main corollary is the following: if $k = o(n / \log n)$ and the process starts from an almost-balanced configuration with an initial bias of magnitude $ω(\sqrt{n/k})$ towards the initial plurality opinion, then any function $h = ω(k \log n)$ suffices to guarantee convergence to consensus in $O(\log n)$ rounds, with high probability. Our upper bound shows that the lower bound of $Ω(k / h^2)$ rounds to reach consensus given by Becchetti et al. (2017) cannot be pushed further than $\widetildeΩ(k / h)$. Moreover, the bias we require is asymptotically smaller than the $Ω(\sqrt{n\log n})$ bias that guarantees plurality consensus in the $3$-majority dynamics: in our case, the required bias is at most any (arbitrarily small) function in $ω(\sqrt{x})$ for any value of $k \ge 2$.

With the advent and the growing usage of Machine Learning as a Service (MLaaS), cloud and network systems are now offering the possibility to deploy ML tasks on heterogeneous clusters. Then, network and cloud operators have to schedule these tasks, determining both when and on which devices to execute them. In parallel, several solutions, such as neural network compression, were proposed to build small models which can run on limited hardware. These solutions allow choosing the model size at inference time for any targeted processing time without having to re-train the network.In this work, we consider the Deadline Scheduling with Compressible Tasks (DSCT) problem: a novel scheduling problem with task deadlines where the tasks can be compressed. Each task can be executed with a certain compression, presenting a trade-off between its compression level (and, its processing time) and its obtained utility. The objective is to maximize the tasks utilities. We propose an approximation algorithm with proved guarantees to solve the problem. We validate its efficiency with extensive simulation, obtaining near optimal results. As application scenario, we study the problem when the tasks are Deep Learning classification jobs, and the objective is to maximize their global accuracy, but we believe that this new framework and solutions apply to a wide range of application cases.

Considerable research efforts have recently been made to show that a random neural network $N$ contains subnetworks capable of accurately approximating any given neural network that is sufficiently smaller than $N$, without any training. This line of research, known as the Strong Lottery Ticket Hypothesis (SLTH), was originally motivated by the weaker Lottery Ticket Hypothesis, which states that a sufficiently large random neural network $N$ contains sparse subnetworks that can be trained efficiently to achieve performance comparable to that of training the entire network $N$. Despite its original motivation, results on the SLTH have so far not provided any guarantee on the size of subnetworks. Such limitation is due to the nature of the main technical tool leveraged by these results, the Random Subset Sum (RSS) Problem. Informally, the RSS Problem asks how large a random i.i.d. sample $\Omega$ should be so that we are able to approximate any number in $[-1,1]$, up to an error of $ \epsilon$, as the sum of a suitable subset of $\Omega$. We provide the first proof of the SLTH in classical settings, such as dense and equivariant networks, with guarantees on the sparsity of the subnetworks. Central to our results, is the proof of an essentially tight bound on the Random Fixed-Size Subset Sum Problem (RFSS), a variant of the RSS Problem in which we only ask for subsets of a given size, which is of independent interest.

The average properties of the well-known Subset Sum Problem can be studied by means of its randomised version, where we are given a target value z, random variables X_1, …, X_n, and an error parameter ε > 0, and we seek a subset of the X_is whose sum approximates z up to error ε. In this setup, it has been shown that, under mild assumptions on the distribution of the random variables, a sample of size 𝒪(log(1/ε)) suffices to obtain, with high probability, approximations for all values in [-1/2, 1/2]. Recently, this result has been rediscovered outside the algorithms community, enabling meaningful progress in other fields. In this work, we present an alternative proof for this theorem, with a more direct approach and resourcing to more elementary tools.

The Strong Lottery Ticket Hypothesis (SLTH) states that randomly-initialised neural networks likely contain subnetworks that perform well without any training. Although unstructured pruning has been extensively studied in this context, its structured counterpart, which can deliver significant computational and memory efficiency gains, has been largely unexplored. One of the main reasons for this gap is the limitations of the underlying mathematical tools used in formal analyses of the SLTH. In this paper, we overcome these limitations: we leverage recent advances in the multidimensional generalisation of the Random Subset-Sum Problem and obtain a variant that admits the stochastic dependencies that arise when addressing structured pruning in the SLTH. We apply this result to prove, for a wide class of random Convolutional Neural Networks, the existence of structured subnetworks that can approximate any sufficiently smaller network. This result provides the first sub-exponential bound around the SLTH for structured pruning, opening up new avenues for further research on the hypothesis and contributing to the understanding of the role of over-parameterization in deep learning.

We revisit the planning problem in the blocks world, and we implement a known heuristic for this task. Importantly, our implementation is biologically plausible, in the sense that it is carried out exclusively through the spiking of neurons. Even though much has been accomplished in the blocks world over the past five decades, we believe that this is the first algorithm of its kind. The input is a sequence of symbols encoding an initial set of block stacks as well as a target set, and the output is a sequence of motion commands such as "put the top block in stack 1 on the table". The program is written in the Assembly Calculus, a recently proposed computational framework meant to model computation in the brain by bridging the gap between neural activity and cognitive function. Its elementary objects are assemblies of neurons (stable sets of neurons whose simultaneous firing signifies that the subject is thinking of an object, concept, word, etc.), its commands include project and merge, and its execution model is based on widely accepted tenets of neuroscience. A program in this framework essentially sets up a dynamical system of neurons and synapses that eventually, with high probability, accomplishes the task. The purpose of this work is to establish empirically that reasonably large programs in the Assembly Calculus can execute correctly and reliably; and that rather realistic --- if idealized --- higher cognitive functions, such as planning in the blocks world, can be implemented successfully by such programs.

Motivated by the Lévy foraging hypothesis -- the premise that various animal species have adapted to follow Lévy walks to optimize their search efficiency -- we study the parallel hitting time of Lévy walks on the infinite two-dimensional grid. We consider k independent discrete-time Lévy walks, with the same exponent α ∈(1,∞), that start from the same node, and analyze the number of steps until the first walk visits a given target at distance ℓ. % We show that for any choice of k and ℓ from a large range, there is a unique optimal exponent α_k,∈ (2,3), for which the hitting time is Õ(ℓ2/k) w.h.p., while modifying the exponent by any constant term ε>0 increases the hitting time by a factor polynomial in ℓ, or the walks fail to hit the target almost surely. % Based on that, we propose a surprisingly simple and effective parallel search strategy, for the setting where k and ℓ are unknown: The exponent of each Lévy walk is just chosen independently and uniformly at random from the interval (2,3). This strategy achieves optimal search time (modulo polylogarithmic factors) among all possible algorithms (even centralized ones that know k). % Our results should be contrasted with a line of previous work showing that the exponent α = 2 is optimal for various search problems. In our setting of k parallel walks, we show that the optimal exponent depends on k and ℓ, and that randomizing the choice of the exponents works simultaneously for all k and ℓ.

Abstract The 2-Choices dynamics is a process that models voting behavior on networks and works as follows: Each agent initially holds either opinion blue or red; then, in each round, each agent looks at two random neighbors and, if the two have the same opinion, the agent adopts it. We study its behavior on a class of networks with core–periphery structure. Assume that a densely-connected subset of agents, the core, holds a different opinion from the rest of the network, the periphery. We prove that, depending on the strength of the cut between core and periphery, a phase-transition phenomenon occurs: Either the core’s opinion rapidly spreads across the network, or a metastability phase takes place in which both opinions coexist for superpolynomial time. The interest of our result, which we also validate with extensive experiments on real networks, is twofold. First, it sheds light on the influence of the core on the rest of the network as a function of its connectivity toward the latter. Second, it is one of the first analytical results which shows a heterogeneous behavior of a simple dynamics as a function of structural parameters of the network.

Consensus and Broadcast are two fundamental problems in distributed computing, whose solutions have several applications. Intuitively, Consensus should be no harder than Broadcast, and this can be rigorously established in several models. Can Consensus be easier than Broadcast? In models that allow noiseless communication, we prove a reduction of (a suitable variant of) Broadcast to binary Consensus, that preserves the communication model and all complexity parameters such as randomness, number of rounds, communication per round, etc., while there is a loss in the success probability of the protocol. Using this reduction, we get, among other applications, the first logarithmic lower bound on the number of rounds needed to achieve Consensus in the uniform GOSSIP model on the complete graph. The lower bound is tight and, in this model, Consensus and Broadcast are equivalent. We then turn to distributed models with noisy communication channels that have been studied in the context of some bio-inspired systems. In such models, only one noisy bit is exchanged when a communication channel is established between two nodes, and so one cannot easily simulate a noiseless protocol by using error-correcting codes. An Ω(ε^{-2} n) lower bound is proved by Boczkowski et al. [PLOS Comp. Bio. 2018] on the convergence time of binary Broadcast in one such model (noisy uniform PULL), where ε is a parameter that measures the amount of noise). We prove an O(ε^{-2} log n) upper bound on the convergence time of binary Consensus in such model, thus establishing an exponential complexity gap between Consensus versus Broadcast. We also prove our upper bound above is tight and this implies, for binary Consensus, a further strong complexity gap between noisy uniform PULL and noisy uniform PUSH. Finally, we show a Θ(ε^{-2} n log n) bound for Broadcast in the noisy uniform PULL.

It follows from the Marcus-Spielman-Srivastava proof of the Kadison-Singer conjecture that if G = (V, E) is a Δ-regular dense expander then there is an edge-induced subgraph H = (V, Eh) of G of constant maximum degree which is also an expander. As with other consequences of the MSS theorem, it is not clear how one would explicitly construct such a subgraph. We show that such a subgraph (although with quantitatively weaker expansion and near-regularity properties than those predicted by MSS) can be constructed with high probability in linear time, via a simple algorithm. Our algorithm allows a distributed implementation that runs in O(log n) rounds and does O(n) total work with high probability. The analysis of the algorithm is complicated by the complex dependencies that arise between edges and between choices made in different rounds. We sidestep these difficulties by following the combinatorial approach of counting the number of possible random choices of the algorithm which lead to failure. We do so by a compression argument showing that such random choices can be encoded with a non-trivial compression. Our algorithm bears some similarity to the way agents construct a communication graph in a peer-to-peer network, and, in the bipartite case, to the way agents select servers in blockchain protocols.

We study parallel Load Balancing protocols for a client-server distributed model defined as follows. There is a set C of n clients and a set S of n servers where each client has (at most) a constant number d ≥ 1 of requests that must be assigned to some server. The client set and the server one are connected to each other via a fixed bipartite graph: the requests of client v can only be sent to the servers in its neighborhood N(v). The goal is to assign every client request so as to minimize the maximum load of the servers.

Given an underlying graph, we consider the following dynamics: Initially, each node locally chooses a value in $\{-1,1\}$, uniformly at random and independently of other nodes. Then, in each consecutive round, every node updates its local value to the average of the values held by its neighbors, at the same time applying an elementary, local clustering rule that only depends on the current and the previous values held by the node. We prove that the process resulting from this dynamics produces a clustering that exactly or approximately (depending on the graph) reflects the underlying cut in logarithmic time, under various graph models that exhibit a sparse balanced cut, including the stochastic block model. We also prove that a natural extension of this dynamics performs community detection on a regularized version of the stochastic block model with multiple communities. Rather surprisingly, our results provide rigorous evidence for the ability of an extremely simple and natural dynamics to perform community detection, a computational problem which is nontrivial even in a centralized setting.

We investigate the behavior of a simple majority dynamics on networks of agents whose interaction topology exhibits a community structure. By leveraging recent advancements in the analysis of dynamics, we prove that, when the states of the nodes are randomly initialized, the system rapidly and stably converges to a configuration in which the communities maintain internal consensus on different states. This is the first analytical result on the behavior of dynamics for nonconsensus problems on non-complete topologies, based on the first symmetry-breaking analysis in such setting.Our result has several implications in different contexts in which dynamics are adopted for computational and biological modeling purposes. In the context of Label Propagation Algorithms, a class of widely used heuristics for community detection, it represents the first theoretical result on the behavior of a distributed label propagation algorithm with quasi-linear message complexity. In the context of evolutionary biology, dynamics such as the Moran process have been used to model the spread of mutations in genetic populations (Lieberman, Hauert, and Nowak 2005); our result shows that, when the probability of adoption of a given mutation by a node of the evolutionary graph depends super-linearly on the frequency of the mutation in the neighborhood of the node and the underlying evolutionary graph exhibits a community structure, there is a non-negligible probability for species differentiation to occur.

We study the following synchronous process that we call repeated balls-into-bins. The process is started by assigning n balls to n bins in an arbitrary fashion. In every subsequent round, one ball is extracted from each non-empty bin according to some fixed strategy (random, FIFO, etc), and re-assigned to one of the n bins uniformly at random. We define a configuration legitimate if its maximum load is $$\mathcal {O}(\log n)$$ . We prove that, starting from any configuration, the process converges to a legitimate configuration in linear time and then only takes on legitimate configurations over a period of length bounded by any polynomial in n, with high probability (w.h.p.). This implies that the process is self-stabilizing and that every ball traverses all bins within $$\mathcal {O}(n\log ^2 n)$$ rounds, w.h.p.

Error-correcting codes are efficient methods for handling noisy communication channels in the context of technological networks. However, such elaborate methods differ a lot from the unsophisticated way biological entities are supposed to communicate. Yet, it has been recently shown by Feinerman et al. (PODC 2014) that complex coordination tasks such as rumor spreading and majority consensus can plausibly be achieved in biological systems subject to noisy communication channels, where every message transferred through a channel remains intact with small probability $$\frac{1}{2}+\epsilon $$ , without using coding techniques. This result is a considerable step towards a better understanding of the way biological entities may cooperate. It has nevertheless been established only in the case of 2-valued opinions: rumor spreading aims at broadcasting a single-bit opinion to all nodes, and majority consensus aims at leading all nodes to adopt the single-bit opinion that was initially present in the system with (relative) majority. In this paper, we extend this previous work to k-valued opinions, for any constant $$k\ge 2$$ . Our extension requires to address a series of important issues, some conceptual, others technical. We had to entirely revisit the notion of noise, for handling channels carrying k-valued messages. In fact, we precisely characterize the type of noise patterns for which plurality consensus is solvable. Also, a key result employed in the bivalued case by Feinerman et al. is an estimate of the probability of observing the most frequent opinion from observing the mode of a small sample. We generalize this result to the multivalued case by providing a new analytical proof for the bivalued case that is amenable to be extended, by induction, and that is of independent interest.

Consider the following asynchronous, opportunistic communication model over a graph $G$: in each round, one edge is activated uniformly and independently at random and (only) its two endpoints can exchange messages and perform local computations. Under this model, we study the following random process: The first time a vertex is an endpoint of an active edge, it chooses a random number, say $\pm 1$ with probability $1/2$; then, in each round, the two endpoints of the currently active edge update their values to their average. We show that, if $G$ exhibits a two-community structure (for example, two expanders connected by a sparse cut), the values held by the nodes will collectively reflect the underlying community structure over a suitable phase of the above process, allowing efficient and effective recovery in important cases. In more detail, we first provide a first-moment analysis showing that, for a large class of almost-regular clustered graphs that includes the stochastic block model, the expected values held by all but a negligible fraction of the nodes eventually reflect the underlying cut signal. We prove this property emerges after a mixing period of length $\mathcal O(n\log n)$. We further provide a second-moment analysis for a more restricted class of regular clustered graphs that includes the regular stochastic block model. For this case, we are able to show that most nodes can efficiently and locally identify their community of reference over a suitable time window. This results in the first opportunistic protocols that approximately recover community structure using only polylogarithmic work per node. Even for the above class of regular graphs, our second moment analysis requires new concentration bounds on the product of certain random matrices that are technically challenging and possibly of independent interest.

Biological systems can share and collectively process information to yield emergent effects, despite inherent noise in communication. While man-made systems often employ intricate structural solutions to overcome noise, the structure of many biological systems is more amorphous. It is not well understood how communication noise may affect the computational repertoire of such groups. To approach this question we consider the basic collective task of rumor spreading, in which information from few knowledgeable sources must reliably flow into the rest of the population. In order to study the effect of communication noise on the ability of groups that lack stable structures to efficiently solve this task, we consider a noisy version of the uniform PULL model. We prove a lower bound which implies that, in the presence of even moderate levels of noise that affect all facets of the communication, no scheme can significantly outperform the trivial one in which agents have to wait until directly interacting with the sources. Our results thus show an exponential separation between the uniform PUSH and PULL communication models in the presence of noise. Such separation may be interpreted as suggesting that, in order to achieve efficient rumor spreading, a system must exhibit either some degree of structural stability or, alternatively, some facet of the communication which is immune to noise. We corroborate our theoretical findings with a new analysis of experimental data regarding recruitment in Cataglyphis Niger desert ants.

Biological systems can share and collectively process information to yield emergent effects, despite inherent noise in communication. While man-made systems often employ intricate structural solutions to overcome noise, the structure of many biological systems is more amorphous. It is not well understood how communication noise may affect the computational repertoire of such groups. To approach this question we consider the basic collective task of rumor spreading, in which information from few knowledgeable sources must reliably flow into the rest of the population. We study the effect of communication noise on the ability of groups that lack stable structures to efficiently solve this task. We present an impossibility result which strongly restricts reliable rumor spreading in such groups. Namely, we prove that, in the presence of even moderate levels of noise that affect all facets of the communication, no scheme can significantly outperform the trivial one in which agents have to wait until directly interacting with the sources-a process which requires linear time in the population size. Our results imply that in order to achieve efficient rumor spread a system must exhibit either some degree of structural stability or, alternatively, some facet of the communication which is immune to noise. We then corroborate this claim by providing new analyses of experimental data regarding recruitment in Cataglyphis niger desert ants. Finally, in light of our theoretical results, we discuss strategies to overcome noise in other biological systems.

We study consensus processes on the complete graph of n nodes. Initially, each node supports one up to n different opinions. Nodes randomly and in parallel sample the opinions of constantly many nodes. Based on these samples, they use an update rule to change their own opinion. The goal is to reach consensus, a configuration where all nodes support the same opinion.

Given an underlying graph, we consider the following dynamics: Initially, each node locally chooses a value in {-1,1}, uniformly at random and independently of other nodes. Then, in each consecutive round, every node updates its local value to the average of the values held by its neighbors, at the same time applying an elementary, local clustering rule that only depends on the current and the previous values held by the node. We prove that the process resulting from this dynamics produces a clustering that exactly or approximately (depending on the graph) reflects the underlying cut in logarithmic time, under various graph models that exhibit a sparse balanced cut, including the stochastic block model. We also prove that a natural extension of this dynamics performs community detection on a regularized version of the stochastic block model with multiple communities. Rather surprisingly, our results provide rigorous evidence for the ability of an extremely simple and natural dynamics to address a computational problem that is non-trivial even in a centralized setting. Distributed Algorithms, Averaging Dynamics, Community Detection, Spectral Analysis, Stochastic Block Models.

This paper considers the basic PULL model of communication, in which in each round, each agent extracts information from few randomly chosen agents. We seek to identify the smallest amount of information revealed in each interaction (message size) that nevertheless allows for efficient and robust computations of fundamental information dissemination tasks. We focus on the Majority Bit Dissemination problem that considers a population of n agents, with a designated subset of source agents. Each source agent holds an input bit and each agent holds an output bit. The goal is to let all agents converge their output bits on the most frequent input bit of the sources (the majority bit). Note that the particular case of a single source agent corresponds to the classical problem of Broadcast (also termed Rumor Spreading). We concentrate on the severe fault-tolerant context of self-stabilization, in which a correct configuration must be reached eventually, despite all agents starting the execution with arbitrary initial states. In particular, the specification of who is a source and what is its initial input bit may be set by an adversary. We first design a general compiler which can essentially transform any self-stabilizing algorithm with a certain property (called “the bitwise-independence property”) that uses ℓ-bits messages to one that uses only log ¿-bits messages, while paying only a small penalty in the running time. By applying this compiler recursively we then obtain a self-stabilizing Clock Synchronization protocol, in which agents synchronize their clocks modulo some given integer T, within Õ(log n log T) rounds w.h.p., and using messages that contain 3 bits only. We then employ the new Clock Synchronization tool to obtain a self-stabilizing Majority Bit Dissemination protocol which converges in Õ(log n) time, w.h.p., on every initial configuration, provided that the ratio of sources supporting the minority opinion is bounded away from half. Moreover, this protocol also uses only 3 bits per interaction.

We present KADABRA, a new algorithm to approximate betweenness centrality in directed and undirected graphs, which significantly outperforms all previous approaches on real-world complex networks. The efficiency of the new algorithm relies on two new theoretical contributions, of independent interest. The first contribution focuses on sampling shortest paths, a subroutine used by most algorithms that approximate betweenness centrality. We show that, on realistic random graph models, we can perform this task in time |E|^{1/2+o(1)} with high probability, obtaining a significant speedup with respect to the Theta(|E|) worst-case performance. We experimentally show that this new technique achieves similar speedups on real-world complex networks, as well. The second contribution is a new rigorous application of the adaptive sampling technique. This approach decreases the total number of shortest paths that need to be sampled to compute all betweenness centralities with a given absolute error, and it also handles more general problems, such as computing the k most central nodes. Furthermore, our analysis is general, and it might be extended to other settings, as well.

In the deterministic binary majority process we are given a simple graph where each node has one out of two initial opinions. In every round, each node adopts the majority opinion among its neighbors. It is known that this process always converges in O(|E|) rounds to a two-periodic state in which every node either keeps its opinion or changes it in every round. It has been shown by Frischknecht, Keller, and Wattenhofer (2013) that the O(|E|) bound on the convergence time of the deterministic binary majority process is even for dense graphs tight. However, in many graphs such as the complete graph the process converges in just a constant number of rounds from any initial opinion assignment. We show that it is NP-hard to decide whether there exists an initial opinion assignment for which it takes more than k rounds to converge to the two-periodic stable state, for a given integer k. We then give a new upper bound on the voting time of the deterministic binary majority process. Our bound can be computed in linear time by carefully exploiting the structure of the potential function by Goles and Olivos. We identify certain modules of a graph G to obtain a new graph G^Delta. This new graph G^Delta has the property that the worst-case convergence time of G^Delta is an upper bound on that of G. Our new bounds asymptotically improve the best known bounds for various graph classes.

This paper is motivated by the aspiration to identify the weakest computational models that allow for efficient, robust distributed computation. We focus on one of the most fundamental building-blocks in distributed computing, namely, Broadcast. In this problem, a unique source agent $s$ needs to disseminate a bit $b$ to the rest of the population. To account for unpredictability issues that may result from uncoordinated executions, we consider a self-stabilizing setting, in which a correct configuration must be reached eventually, despite processors starting the execution with arbitrary initial states (that do not violate the requirement for the existence of a unique source). Similarly to many works on broadcast, we consider a synchronous communication model on a complete anonymous network, in which in each round, each agent can extract information from two other agents, chosen uniformly at random. Our focus is on identifying the smallest message size that is required in order to achieve fast self-stabilizing broadcast. We first observe that with an extra bit added to the message-size and a small additive penalty to the running time, the self-stabilizing broadcast problem can be reduced to a self-stabilizing clock-synchronization problem, where agents aim to synchronize their clocks modulo some integer T. Our main technical contribution lies in solving the latter problem in poly-logarithmic time using only 3 bits per interaction. This allows for a self-stabilizing broadcast protocol that uses only 4 bits per interaction and converges in O log n time.

Error-correcting codes are efficient methods for handling noisy communication channels in the context of technological networks. However, such elaborate methods differ a lot from the unsophisticated way biological entities are supposed to communicate. Yet, it has been recently shown by Feinerman, Haeupler, and Korman [PODC 2014] that complex coordination tasks such as rumor spreading and majority consensus can ε plausibly be achieved in biological systems subject to noisy communication channels, where every message transferred through a channel remains intact with small probability 1 over 2 + ε, without using coding techniques. This result is a considerable step towards a better understanding of the way biological entities may cooperate. It has nevertheless been established only in the case of 2-valued opinions: rumor spreading aims at broadcasting a single-bit opinion to all nodes, and majority consensus aims at leading all nodes to adopt the single-bit opinion that was initially present in the system with (relative) majority. In this paper, we extend this previous work to k-valued opinions, for any constant k≥2.

We consider the following distributed consensus problem: Each node in a complete communication network of size n initially holds an opinion, which is chosen arbitrarily from a finite set Σ. The system must converge toward a consensus state in which all, or almost all nodes, hold the same opinion. Moreover, this opinion should be valid, i.e., it should be one among those initially present in the system. This condition should be met even in the presence of a malicious adversary who can modify the opinions of a bounded subset of nodes, adaptively chosen in every round. We consider the 3-majority dynamics: At every round, every node pulls the opinion from three random neighbors and sets his new opinion to the majority one (ties are broken arbitrarily). Let k be the number of valid opinions. We show that, if k ≤ nα, where α is a suitable positive constant, the 3-majority dynamics converges in time polynomial in k and log n with high probability even in the presence of an adversary who can affect up to nodes at each round. Previously, the convergence of the 3-majority protocol was known for |Σ| = 2 only, with an argument that is robust to adversarial errors. On the other hand, no anonymous, uniform-gossip protocol that is robust to adversarial errors was known for |Σ| > 2.

We study Plurality Consensus in the Model over a network of n anonymous agents. Each agent supports an initial opinion or color. We assume that at the onset, the number of agents supporting the plurality color exceeds that of the agents supporting any other color by a sufficiently-large bias, though the initial plurality itself might be very far from absolute majority. The goal is to provide a protocol that, with high probability, brings the system into the configuration in which all agents support the (initial) plurality color. We consider the Undecided-State Dynamics, a well-known protocol which uses just one more state (the undecided one) than those necessary to store colors. We show that the speed of convergence of this protocol depends on the initial color configuration as a whole, not just on the gap between the plurality and the second largest color community. This dependence is best captured by a novel notion we introduce, namely, the monochromatic distance md which measures the distance of the initial color configuration from the closest monochromatic one. In the complete graph, we prove that, for a wide range of the input parameters, this dynamics converges within O(md log n) rounds. We prove that this upper bound is almost tight in the strong sense: Starting from any color configuration , the convergence time is Ω(md). Finally, we adapt the Undecided-State Dynamics to obtain a fast, random walk-based protocol for plurality consensus on regular expanders. This protocol converges in O(md polylog(n)) rounds using only polylog(n) local memory. A key-ingredient to achieve the above bounds is a new analysis of the maximum node congestion that results from performing n parallel random walks on regular expanders. All our bounds hold with high probability.

We study the following synchronous process that we call repeated balls-into-bins. The process is started by assigning n balls to n bins in an arbitrary way. Then, in every subsequent round, one ball is chosen according to some fixed strategy (random, FIFO, etc) from each non-empty bin, and re-assigned to one of the n bins uniformly at random. This process corresponds to a non-reversible Markov chain and our aim is to study its self-stabilization properties with respect to the maximum(bin) load and some related performance measures. We define a configuration (i.e., a state) legitimate if its maximum load is O(log n). We first prove that, starting from any legitimate configuration, the process will only take on legitimate configurations over a period of length bounded by any polynomial in n, with high probability (w.h.p.). Further we prove that, starting from any configuration, the process converges to a legitimate configuration in linear time, w.h.p. This implies that the process is self-stabilizing w.h.p. and, moreover, that every ball traverses all bins in O(n log2 n) rounds, w.h.p. The latter result can also be interpreted as an almost tight bound on the cover time for the problem of parallel resource assignment in the complete graph.

We study a Plurality Consensus process in which each of n anonymous agents of a communication network supports an initial opinion (a colorchosen from a finite set [k]) and, at every time step, he can revise his color according to a random sample of neighbors.