1 Search Results for "Varloot, R�mi"

Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2017.59
Brief Announcement: Rapid Mixing of Local Dynamics on Graphs

Authors: Laurent Massoulié and Rémi Varloot

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
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.
Cite as

Laurent Massoulié and Rémi Varloot. Brief Announcement: Rapid Mixing of Local Dynamics on Graphs. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 59:1-59:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{massoulie_et_al:LIPIcs.DISC.2017.59,
  author =	{Massouli\'{e}, Laurent and Varloot, R\'{e}mi},
  title =	{{Brief Announcement: Rapid Mixing of Local Dynamics on Graphs}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{59:1--59:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.59},
  URN =		{urn:nbn:de:0030-drops-79649},
  doi =		{10.4230/LIPIcs.DISC.2017.59},
  annote =	{Keywords: Markov chains, Mixing time, Dynamic graphs, Local dynamics}
}
  • Refine by Author
  • 1 Massoulié, Laurent
  • 1 Varloot, Rémi

  • Refine by Classification

  • Refine by Keyword
  • 1 Dynamic graphs
  • 1 Local dynamics
  • 1 Markov chains
  • 1 Mixing time

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact