Search

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 v1, v2, ⋯ , vk 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, v) is selected, and then node u updates its value equivalently to the NodeModel with k = 1 and v as the selected neighbour.For both processes, the values of all nodes converge to the same value F, which is a random variable depending on the random choices made in each step. For the NodeModel and regular graphs, and for the EdgeModel and arbitrary graphs, the expectation of F is the average of the initial values [EQUATION]. For the NodeModel and non-regular graphs, the expectation of F is the degree-weighted average of the initial values.Our results are two-fold. We consider the concentration of F and show tight bounds on the variance of F for regular graphs. We show that when the initial values do not depend on the number of nodes, then the variance is negligible, and hence the nodes are able to estimate the initial average of the node values. Interestingly, this variance does not depend on the graph structure. For the proof we introduce a duality between our processes and a process of two correlated random walks. We also analyse the convergence time for both models and for arbitrary graphs, showing bounds on the time Tϵ required to make all node values 'ϵ-close' to each other. Our bounds are asymptotically tight under some assumptions on the distribution of the initial values.

We continue our study from Lynch and Mallmann-Trenn (Neural Networks, 2021), of how concepts that have hierarchical structure might be represented in brain-like neural networks, how these representations might be used to recognize the concepts, and how these representations might be learned. In Lynch and Mallmann-Trenn (Neural Networks, 2021), we considered simple tree-structured concepts and feed-forward layered networks. Here we extend the model in two ways: we allow limited overlap between children of different concepts, and we allow networks to include feedback edges. For these more general cases, we describe and analyze algorithms for recognition and algorithms for learning.

Prophet inequalities are a central object of study in optimal stopping theory. A gambler is sent values online, sampled from an instance of independent distributions, in an adversarial, random or selected order, depending on the model. When observing each value, the gambler either accepts it as a reward or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is maximising the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations. The model, in which the gambler selects the arrival order first, and then observes the values, is known as Order Selection. Recently it has been shown that in this model a ratio of $0.7251$ can be attained for any instance. If the gambler chooses the arrival order (uniformly) at random, we obtain the Random Order model. The worst case ratio over all possible instances has been extensively studied for at least $40$ years. Still, it is not known if carefully choosing the order, or simply taking it at random, benefits the gambler. We prove that, in the Random Order model, no algorithm can achieve a ratio larger than $0.7235$, thus showing for the first time that there is a real benefit in choosing the order., 36 pages, 2 figures

Coordination in a large number of networked robots is a challenging task, especially when robots are constantly moving around the environment and there are malicious attacks within the network. Various approaches in the literature exist for detecting malicious robots, such as message sampling or suspicious behavior analysis. However, these approaches require every robot to sample every other robot in the network, leading to a slow detection process that degrades team performance. This paper introduces a method that significantly decreases the detection time for legitimate robots to identify malicious robots in a scenario where legitimate robots are randomly moving around the environment. Our method leverages the concept of ``Dynamic Crowd Vetting" by utilizing observations from random encounters and trusted neighboring robots' opinions to quickly improve the accuracy of detecting malicious robots. The key intuition is that as long as each legitimate robot accurately estimates the legitimacy of at least some fixed subset of the team, the second-hand information they receive from trusted neighbors is enough to correct any misclassifications and provide accurate trust estimations of the rest of the team. We show that the size of this fixed subset can be characterized as a function of fundamental graph and random walk properties. Furthermore, we formally show that as the number of robots in the team increases the detection time remains constant. We develop a closed form expression for the critical number of time-steps required for our algorithm to successfully identify the true legitimacy of each robot to within a specified failure probability. Our theoretical results are validated through simulations demonstrating significant reductions in detection time when compared to previous works that do not leverage trusted neighbor information., 9 pages, 5 figures, extended version of paper submitted to the IEEE Conference on Decision and Control (CDC 2023)

We characterize the advantage of using a robot's neighborhood to find and eliminate adversarial robots in the presence of a Sybil attack. We show that by leveraging the opinions of its neighbors on the trustworthiness of transmitted data, robots can detect adversaries with high probability. We characterize a number of communication rounds required to achieve this result to be a function of the communication quality and the proportion of legitimate to malicious robots. This result enables increased resiliency of many multi-robot algorithms. Because our results are finite time and not asymptotic, they are particularly well-suited for problems with a time critical nature. We develop two algorithms, \emph{FindSpoofedRobots} that determines trusted neighbors with high probability, and \emph{FindResilientAdjacencyMatrix} that enables distributed computation of graph properties in an adversarial setting. We apply our methods to a flocking problem where a team of robots must track a moving target in the presence of adversarial robots. We show that by using our algorithms, the team of robots are able to maintain tracking ability of the dynamic target.

International audience; Motivated by crowdsourced computation, peergrading, and recommendation systems, Braverman, Mao and Weinberg [7] studied the query and round complexity of fundamental problems such as finding the maximum (max), finding all elements above a certain value (threshold-ν) or computing the top−k elements (Top-k) in a noisy environment.For example, consider the task of selecting papers for a conference. This task is challenging due to the crowdsourcing nature of peer reviews: the results of reviews are noisy and it is necessary to parallelize the review process as much as possible. We study the noisy value model and the noisy comparison model: In the noisy value model, a reviewer is asked to evaluate a single element: “What is the value of paper i?” (e.g., accept). In the noisy comparison model (introduced in the seminal work of Feige, Peleg, Raghavan and Upfal [17]) a reviewer is asked to do a pairwise comparison: “Is paper i better than paper j?”In this paper, we introduce new lower bound techniques for these classic problems. In comparison to previous work, our lower bounds are much more fine-grained: they focus on the interplay between round and query complexity and the dependency on the output size. In the setting of conference papers, this translates into a trade-off between number of reviews per paper and the number of review rounds necessary in order find the best 100 papers for the conference.We complement these results with simple algorithms which show that our lower bounds are almost tight.We then go beyond the worst-case and address the question of the importance of knowledge of the instance by providing, for a large range of parameters, instance-optimal algorithms with respect to the query complexity. We complement these results by showing that for some family of instances, no instance-optimal algorithm can exist.

International audience

International audience; Hierarchical clustering is a recursive partitioning of a dataset into clusters at an increasingly finer granularity. Motivated by the fact that most work on hierarchical clustering was based on providing algorithms, rather than optimizing a specific objective, Dasgupta framed similarity-based hierarchical clustering as a combinatorial optimization problem, where a “good” hierarchical clustering is one that minimizes a particular cost function [23]. He showed that this cost function has certain desirable properties: To achieve optimal cost, disconnected components (namely, dissimilar elements) must be separated at higher levels of the hierarchy, and when the similarity between data elements is identical, all clusterings achieve the same cost.We take an axiomatic approach to defining “good” objective functions for both similarity- and dissimilarity-based hierarchical clustering. We characterize a set of admissible objective functions having the property that when the input admits a “natural” ground-truth hierarchical clustering, the ground-truth clustering has an optimal value. We show that this set includes the objective function introduced by Dasgupta.Equipped with a suitable objective function, we analyze the performance of practical algorithms, as well as develop better and faster algorithms for hierarchical clustering. We also initiate a beyond worst-case analysis of the complexity of the problem and design algorithms for this scenario.

In the French flag problem, initially uncolored cells on a grid must differentiate to become blue, white or red. The goal is for the cells to color the grid as a French flag, i.e., a three-colored triband, in a distributed manner. To solve a generalized version of the problem in a distributed computational setting, we consider two models: a biologically-inspired version that relies on morphogens (diffusing proteins acting as chemical signals) and a more abstract version based on reliable message passing between cellular agents. Much of developmental biology research has focused on concentration-based approaches using morphogens, since morphogen gradients are thought to be an underlying mechanism in tissue patterning. We show that both our model types easily achieve a French ribbon - a French flag in the 1D case. However, extending the ribbon to the 2D flag in the concentration model is somewhat difficult unless each agent has additional positional information. Assuming that cells are are identical, it is impossible to achieve a French flag or even a close approximation. In contrast, using a message-based approach in the 2D case only requires assuming that agents can be represented as constant size state machines. We hope that our insights may lay some groundwork for what kind of message passing abstractions or guarantees, if any, may be useful in analogy to cells communicating at long and short distances to solve patterning problems. In addition, we hope that our models and findings may be of interest in the design of nano-robots.

We give a simple distributed algorithm for computing adjacency matrix eigenvectors for the communication graph in an asynchronous gossip model. We show how to use this algorithm to give state-of-the-art asynchronous community detection algorithms when the communication graph is drawn from the well-studied stochastic block model. Our methods also apply to a natural alternative model of randomized communication, where nodes within a community communicate more frequently than nodes in different communities. Our analysis simplifies and generalizes prior work by forging a connection between asynchronous eigenvector computation and Oja's algorithm for streaming principal component analysis. We hope that our work serves as a starting point for building further connections between the analysis of stochastic iterative methods, like Oja's algorithm, and work on asynchronous and gossip-type algorithms for distributed computation.

This thesis is devoted to the study of stochastic decentralized processes. Typical examples in the real world include the dynamics of weather and temperature, of traffic, the way we meet our friends, etc. We take the rich tool set from probability theoryfor the analysis of Markov Chains and employ it to study a wide range of such distributed processes: Forest Fire Model (social networks), Balls-into-Bins with Deleting Bins, and fundamental consensus dynamics and protocols such as the Voter Model, 2-Choices, and 3-Majority., Cette thèse est consacrée à l'étude des processus stochastiques décentralisés. Parmi les exemples typiques de ces processus figurent la dynamique météorologique, la circulation automobile, la façon dont nous rencontrons nos amis, etc. Dans cette thèse, nous exploitons une large palette d'outils probabilistes permettant d'analyser des chaînes de Markov afin d'étudier un large éventail de ces processus distribués : modèle des feux de forêt (réseaux sociaux), balls-into-bins avec suppression, et des dynamiques et protocoles de consensus fondamentaux tels que Voter Model, 2-Choices, et 3-Majority.

We consider the problem of estimating the graph size, where one is given only local access to the graph. We formally define a query model in which one starts with a \emph{seed} node and is allowed to make queries about neighbours of nodes that have already been seen. In the case of undirected graphs, an estimator of Katzir et al. (2014) based on a sample from the stationary distribution $\pi$ uses $O\left(\frac{1}{\|\pi\|_2} + \text{davg}\right)$ queries, we prove that this is tight. In addition, we establish this as a lower bound even when the algorithm is allowed to crawl the graph arbitrarily, the results of Katzir et al. give an upper bound that is worse by a multiplicative factor $t_\text{mix} \cdot \log(n)$. The picture becomes significantly different in the case of directed graphs. We show that without strong assumptions on the graph structure, the number of nodes cannot be predicted to within a constant multiplicative factor without using a number of queries that are at least linear in the number of nodes, in particular, rapid mixing and small diameter, properties that most real-world networks exhibit, do not suffice. The question of interest is whether any algorithm can beat breadth-first search. We introduce a new parameter, generalising the well-studied conductance, such that if a suitable bound on it exists and is known to the algorithm, the number of queries required is sublinear in the number of edges, we show that this is tight.

In the voter model, each node of a graph has an opinion, and in every round each node chooses independently a random neighbour and adopts its opinion. We are interested in the consensus time, which is the first point in time where all nodes have the same opinion. We consider dynamic graphs in which the edges are rewired in every round (by an adversary) giving rise to the graph sequence $G_1, G_2, \dots $, where we assume that $G_i$ has conductance at least $\phi_i$. We assume that the degrees of nodes don't change over time as one can show that the consensus time can become super-exponential otherwise. In the case of a sequence of $d$-regular graphs, we obtain asymptotically tight results. Even for some static graphs, such as the cycle, our results improve the state of the art. Here we show that the expected number of rounds until all nodes have the same opinion is bounded by $O(m/(d_{min} \cdot \phi))$, for any graph with $m$ edges, conductance $\phi$, and degrees at least $d_{min}$. In addition, we consider a biased dynamic voter model, where each opinion $i$ is associated with a probability $P_i$, and when a node chooses a neighbour with that opinion, it adopts opinion $i$ with probability $P_i$ (otherwise the node keeps its current opinion). We show for any regular dynamic graph, that if there is an $\epsilon>0$ difference between the highest and second highest opinion probabilities, and at least $\Omega(\log n)$ nodes have initially the opinion with the highest probability, then all nodes adopt w.h.p. that opinion. We obtain a bound on the convergences time, which becomes $O(\log n/\phi)$ for static graphs.

We consider \emph{plurality consensus} in a network of $n$ nodes. Initially, each node has one of $k$ opinions. The nodes execute a (randomized) distributed protocol to agree on the plurality opinion (the opinion initially supported by the most nodes). Nodes in such networks are often quite cheap and simple, and hence one seeks protocols that are not only fast but also simple and space efficient. Typically, protocols depend heavily on the employed communication mechanism, which ranges from sequential (only one pair of nodes communicates at any time) to fully parallel (all nodes communicate with all their neighbors at once) communication and everything in-between. We propose a framework to design protocols for a multitude of communication mechanisms. We introduce protocols that solve the plurality consensus problem and are with probability 1-o(1) both time and space efficient. Our protocols are based on an interesting relationship between plurality consensus and distributed load balancing. This relationship allows us to design protocols that generalize the state of the art for a large range of problem parameters. In particular, we obtain the same bounds as the recent result of Alistarh et al. (who consider only two opinions on a clique) using a much simpler protocol that generalizes naturally to general graphs and multiple opinions.

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, every node adopts the majority opinion among its neighbors. By using a potential argument first discovered by Goles and Olivos (1980), 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 indeed tight even for dense graphs. However, in many graphs such as the complete graph, from any initial opinion assignment, the process converges in just a constant number of rounds. By carefully exploiting the structure of the potential function by Goles and Olivos (1980), we derive a new upper bound on the convergence time of the deterministic binary majority process that accounts for such exceptional cases. We show that it is possible to identify certain modules of a graph $G$ in order to obtain a new graph $G^\Delta$ with the property that the worst-case convergence time of $G^\Delta$ is an upper bound on that of $G$. Moreover, even though our upper bound can be computed in linear time, we show that, given an integer $k$, 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 state., Comment: full version of brief announcement accepted at DISC'15

International audience; We study the deterministic binary majority process which is defined as fol- lows. We are given a graph G = (V,E) where each node has one out of two opinions. The process runs in discrete rounds where in every round each node computes and adopts the majority opinion among all of its neighbors.

In the Palindrome Problem one tries to find all palindromes (palindromic substrings) in a given string. A palindrome is defined as a string which reads forwards the same as backwards, e.g., the string "racecar". A related problem is the Longest Palindromic Substring Problem in which finding an arbitrary one of the longest palindromes in the given string suffices. We regard the streaming version of both problems. In the streaming model the input arrives over time and at every point in time we are only allowed to use sublinear space. The main algorithms in this paper are the following: The first one is a one-pass randomized algorithm that solves the Palindrome Problem. It has an additive error and uses $O(\sqrt n$) space. The second algorithm is a two-pass algorithm which determines the exact locations of all longest palindromes. It uses the first algorithm as the first pass. The third algorithm is again a one-pass randomized algorithm, which solves the Longest Palindromic Substring Problem. It has a multiplicative error using only $O(\log(n))$ space. We also give two variants of the first algorithm which solve other related practical problems.

We present and study a new model for energy-aware and profit-oriented scheduling on a single processor. The processor features dynamic speed scaling as well as suspension to a sleep mode. Jobs arrive over time, are preemptable, and have different sizes, values, and deadlines. On the arrival of a new job, the scheduler may either accept or reject the job. Accepted jobs need a certain energy investment to be finished in time, while rejected jobs cause costs equal to their values. Here, power consumption at speed $s$ is given by $P(s)=s^{\alpha}+\beta$ and the energy investment is power integrated over time. Additionally, the scheduler may decide to suspend the processor to a sleep mode in which no energy is consumed, though awaking entails fixed transition costs $\gamma$. The objective is to minimize the total value of rejected jobs plus the total energy. Our model combines aspects from advanced energy conservation techniques (namely speed scaling and sleep states) and profit-oriented scheduling models. We show that \emph{rejection-oblivious} schedulers (whose rejection decisions are not based on former decisions) have -- in contrast to the model without sleep states -- an unbounded competitive ratio w.r.t\text{.} the processor parameters $\alpha$ and $\beta$. It turns out that the worst-case performance of such schedulers depends linearly on the jobs' value densities (the ratio between a job's value and its work). We give an algorithm whose competitiveness nearly matches this lower bound. If the maximum value density is not too large, the competitiveness becomes $\alpha^{\alpha}+2e\alpha$. Also, we show that it suffices to restrict the value density of low-value jobs only. Using a technique from \cite{Chan:2010} we transfer our results to processors with a fixed maximum speed., Comment: An extended abstract of this paper has been accepted for publication in the proceedings of the 1st Mediterranean Conference on Algorithms

Hierarchical clustering is a recursive partitioning of a dataset into clusters at an increasingly finer granularity. Motivated by the fact that most work on hierarchical clustering was based on providing algorithms, rather than optimizing a specific objective, Dasgupta (2016) framed similarity-based hierarchical clustering as a combinatorial optimization problem, where a `good' hierarchical clustering is one that minimizes some cost function. He showed that this cost function has certain desirable properties, such as in order to achieve optimal cost disconnected components must be separated first and that in `structureless' graphs, i.e., cliques, all clusterings achieve the same cost. We take an axiomatic approach to defining `good' objective functions for both similarity and dissimilarity-based hierarchical clustering. We characterize a set of admissible objective functions (that includes the one introduced by Dasgupta) that have the property that when the input admits a `natural' ground-truth hierarchical clustering, the ground-truth clustering has an optimal value. Equipped with a suitable objective function, we analyze the performance of practical algorithms, as well as develop better and faster algorithms for hierarchical clustering. For similarity-based hierarchical clustering, Dasgupta (2016) showed that a simple recursive sparsest-cut based approach achieves an O(log^3/2 n)-approximation on worst-case inputs. We give a more refined analysis of the algorithm and show that it in fact achieves an O(√log n)-approximation. This improves upon the LP-based O(log n)-approximation of Roy and Pokutta (2016). For dissimilarity-based hierarchical clustering, we show that the classic average-linkage algorithm gives a factor 2 approximation, and provide a simple and better algorithm that gives a factor 3/2 approximation. This aims at explaining the success of this heuristics in practice. Finally, we consider `beyond-worst-case' scenario through a generalisation of the stochastic block model for hierarchical clustering. We show that Dasgupta's cost function also has desirable properties for these inputs and we provide a simple algorithm that for graphs generated according to this model yields a 1 + o(1) factor approximation.