2026-07-20T05:38:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7964 2024-03-06T10:41:45Z ddc:004 open_access

Brief Announcement: Rapid Mixing of Local Dynamics on Graphs Massoulié, Laurent Varloot, Rémi Markov chains Mixing time Dynamic graphs Local dynamics In peer-to-peer networks, it is desirable that the logical topology of connections between the constituting nodes make a well-connected graph, i.e., a graph with low diameter and high expansion. At the same time, this graph should evolve only through local modifications. These requirements prompt the following question: are there local graph dynamics that i) create a well-connected graph in equilibrium, and ii) converge rapidly to this equilibrium? In this paper we provide an affirmative answer by exhibiting a local graph dynamic that mixes provably fast. Specifically, for a graph on N nodes, mixing has occurred after each node has performed O(polylog(N)) operations. This is in contrast with previous results, which required at least Omega(N polylog(N)) operations per node before the graph had properly mixed. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Laurent Massoulié and Rémi Varloot 2017 Is Part Of LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2017.59 urn:nbn:de:0030-drops-79649 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.59 eng https://creativecommons.org/licenses/by/3.0/legalcode