Source author record

Bernadette Charron-Bost

Bernadette Charron-Bost appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Distributed, Parallel, and Cluster Computing Discrete Mathematics Systems and Control math.CO Multiagent Systems

Catalog footprint

What is connected

10works

5topics

3close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Self-Stabilizing Clock Synchronization in Dynamic Networks

We consider the fundamental problem of clock synchronization in a synchronous multi-agent system. Each agent holds a clock with an arbitrary initial value, and clocks must eventually indicate the same value. Previous algorithms worked in static networks with drastic connectivity properties and assumed that global information is available at each agent. In this paper, we propose different solutions for time-varying topologies that require neither strong connectivity nor any global knowledge on the network. First, we study the case of unbounded clocks, and propose a self-stabilizing $MinMax$ algorithm that works if, in each sufficiently long but bounded period of time, there is an agent, called a root, that can send messages, possibly indirectly, to all other agents. Such networks are highly dynamic in the sense that roots may change arbitrarily over time. Moreover, the bound on the time required for achieving this rootedness property is unknown to the agents. Then we present a finite-state algorithm that synchronizes periodic clocks in dynamic networks that are strongly connected over bounded period of time. Here also, the bound on the time for achieving strong connectivity exists, but is not supposed to be known. Interestingly, our algorithm unifies several seemingly different algorithms proposed previously for static networks. Next, we show that strong connectivity is actually not required: our algorithm still works when the network is just rooted over bounded period of time with a set of roots that becomes stable. Finally, we study the time and space complexities of our algorithms, and discuss how initial timing information allows for more efficient solutions.

preprint2020arXiv

Geometric Bounds for Convergence Rates of Averaging Algorithms

We develop a generic method for bounding the convergence rate of an averaging algorithm running in a multi-agent system with a time-varying network, where the associated stochastic matrices have a time-independent Perron vector. This method provides bounds on convergence rates that unify and refine most of the previously known bounds. They depend on geometric parameters of the dynamic communication graph such as the normalized diameter or the bottleneck measure. As corollaries of these geometric bounds, we show that the convergence rate of the Metropolis algorithm in a system of $n$ agents is less than $1-1/4n^2$ with any communication graph that may vary in time, but is permanently connected and bidirectional. We prove a similar upper bound for the EqualNeighbor algorithm under the additional assumptions that the number of neighbors of each agent is constant and that the communication graph is not too irregular. Moreover our bounds offer improved convergence rates for several averaging algorithms and specific families of communication graphs. Finally we extend our methodology to a time-varying Perron vector and show how convergence times may dramatically degrade with even limited variations of Perron vectors.

preprint2016arXiv

Multidimensional Asymptotic Consensus in Dynamic Networks

We study the problem of asymptotic consensus as it occurs in a wide range of applications in both man-made and natural systems. In particular, we study systems with directed communication graphs that may change over time. We recently proposed a new family of convex combination algorithms in dimension one whose weights depend on the received values and not only on the communication topology. Here, we extend this approach to arbitrarily high dimensions by introducing two new algorithms: the ExtremePoint and the Centroid algorithm. Contrary to classical convex combination algorithms, both have component-wise contraction rates that are constant in the number of agents. Paired with a speed-up technique for convex combination algorithms, we get a convergence time linear in the number of agents, which is optimal. Besides their respective contraction rates, the two algorithms differ in the fact that the Centroid algorithm's update rule is independent of any coordinate system while the ExtremePoint algorithm implicitly assumes a common agreed-upon coordinate system among agents. The latter assumption may be realistic in some man-made multi-agent systems but is highly questionable in systems designed for the modelization of natural phenomena. Finally we prove that our new algorithms also achieve asymptotic consensus under very weak connectivity assumptions, provided that agent interactions are bidirectional.

preprint2015arXiv

A Proof of the Convergence of the Hegselmann-Krause Dynamics on the Circle

In this note, we give a complete proof that Hegselmann-Krause systems converge on the circle following the proof strategy developed by Hegarty, Martinsson, and Wedin.

preprint2015arXiv

Amortized Averaging Algorithms for Approximate Consensus

We introduce a new class of distributed algorithms for the approximate consensus problem in dynamic rooted networks, which we call amortized averaging algorithms. They are deduced from ordinary averaging algorithms by adding a value-gathering phase before each value update. This allows their decision time to drop from being exponential in the number $n$ of processes to being linear under the assumption that each process knows $n$. In particular, the amortized midpoint algorithm, which achieves a linear decision time, works in completely anonymous dynamic rooted networks where processes can exchange and store continuous values, and under the assumption that the number of processes is known to all processes. We then study the way amortized averaging algorithms degrade when communication graphs are from time to time non rooted, or with a wrong estimate of the number of processes. Finally, we analyze the amortized midpoint algorithm under the additional constraint that processes can only store and send quantized values, and get as a corollary that the 2-set consensus problem is solvable in linear time in any rooted dynamic network model when allowing all decision values to be in the range of initial values.

preprint2014arXiv

An Overview of Transience Bounds in Max-Plus Algebra

We survey and discuss upper bounds on the length of the transient phase of max-plus linear systems and sequences of max-plus matrix powers. In particular, we explain how to extend a result by Nachtigall to yield a new approach for proving such bounds and we state an asymptotic tightness result by using an example given by Hartmann and Arguelles.

preprint2014arXiv

Approximate Consensus in Highly Dynamic Networks: The Role of Averaging Algorithms

In this paper, we investigate the approximate consensus problem in highly dynamic networks in which topology may change continually and unpredictably. We prove that in both synchronous and partially synchronous systems, approximate consensus is solvable if and only if the communication graph in each round has a rooted spanning tree, i.e., there is a coordinator at each time. The striking point in this result is that the coordinator is not required to be unique and can change arbitrarily from round to round. Interestingly, the class of averaging algorithms, which are memoryless and require no process identifiers, entirely captures the solvability issue of approximate consensus in that the problem is solvable if and only if it can be solved using any averaging algorithm. Concerning the time complexity of averaging algorithms, we show that approximate consensus can be achieved with precision of $\varepsilon$ in a coordinated network model in $O(n^{n+1} \log\frac{1}{\varepsilon})$ synchronous rounds, and in $O(Δn^{nΔ+1} \log\frac{1}{\varepsilon})$ rounds when the maximum round delay for a message to be delivered is $Δ$. While in general, an upper bound on the time complexity of averaging algorithms has to be exponential, we investigate various network models in which this exponential bound in the number of nodes reduces to a polynomial bound. We apply our results to networked systems with a fixed topology and classical benign fault models, and deduce both known and new results for approximate consensus in these systems. In particular, we show that for solving approximate consensus, a complete network can tolerate up to 2n-3 arbitrarily located link faults at every round, in contrast with the impossibility result established by Santoro and Widmayer (STACS '89) showing that exact consensus is not solvable with n-1 link faults per round originating from the same node.

preprint2013arXiv

Orientation and Connectivity Based Criteria for Asymptotic Consensus

In this article, we establish orientation and connectivity based criteria for the agreement algorithm to achieve asymptotic consensus in the context of time-varying topology and communication delays. These criteria unify and extend many earlier convergence results on the agreement algorithm for deterministic and discrete-time multiagent systems.

preprint2012arXiv

New Transience Bounds for Long Walks

Linear max-plus systems describe the behavior of a large variety of complex systems. It is known that these systems show a periodic behavior after an initial transient phase. Assessment of the length of this transient phase provides important information on complexity measures of such systems, and so is crucial in system design. We identify relevant parameters in a graph representation of these systems and propose a modular strategy to derive new upper bounds on the length of the transient phase. By that we are the first to give asymptotically tight and potentially subquadratic transience bounds. We use our bounds to derive new complexity results, in particular in distributed computing.

preprint2011arXiv

On the Transience of Linear Max-Plus Dynamical Systems

We study the transients of linear max-plus dynamical systems. For that, we consider for each irreducible max-plus matrix A, the weighted graph G(A) such that A is the adjacency matrix of G(A). Based on a novel graph-theoretic counterpart to the number-theoretic Brauer's theorem, we propose two new methods for the construction of arbitrarily long paths in G(A) with maximal weight. That leads to two new upper bounds on the transient of a linear max-plus system which both improve on the bounds previously given by Even and Rajsbaum (STOC 1990, Theory of Computing Systems 1997), by Bouillard and Gaujal (Research Report 2000), and by Soto y Koelemeijer (PhD Thesis 2003), and are, in general, incomparable with Hartmann and Arguelles' bound (Mathematics of Operations Research 1999). With our approach, we also show how to improve the latter bound by a factor of two. A significant benefit of our bounds is that each of them turns out to be linear in the size of the system in various classes of linear max-plus system whereas the bounds previously given are all at least quadratic. Our second result concerns the relationship between matrix and system transients: We prove that the transient of an NxN matrix A is, up to some constant, equal to the transient of an A-linear system with an initial vector whose norm is quadratic in N. Finally, we study the applicability of our results to the well-known Full Reversal algorithm whose behavior can be described as a min-plus linear system.