Spanders: distributed spanning expanders

DOI10.1016/J.SCICO.2012.10.001MaRDI QIDQ395654zbMATHOpenAlexFDO

Authors Shlomi Dolev, Nir Tzachar

Publication date 29 January 2014

Published in Science of Computer Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.scico.2012.10.001

zbMATH Keywords

self-organizationdynamic networksrandom walksself-stabilizationexpanders

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Distributed systems (68M14)

Recommendations

• DEX: self-healing expanders
• A self-stabilizing distributed algorithm to construct an arbitrary spanning tree of a connected graph
• Expanders via Random Spanning Trees
• Self-spanner graphs
• Expanders via random spanning trees

Cites work

• scientific article; zbMATH DE number 878897 (Why is no real title available?)
• Distributed Computing: A Locality-Sensitive Approach
• Empire of colonies: Self-stabilizing and self-organizing distributed algorithm
• Expander graphs and their applications
• Graph spanners
• Many Random Walks Are Faster Than One
• Property testing in bounded degree graphs
• Self-Stabilizing and Self-Organizing Virtual Infrastructures for Mobile Networks
• Self-stabilization
• Self-stabilizing systems in spite of distributed control
• Spanders: distributed spanning expanders
• Testing the expansion of a graph
• Time, clocks, and the ordering of events in a distributed system

Cited in

(10)

• Xheal: a localized self-healing algorithm using expanders
• Physical expander in virtual tree overlay
• Spanning spiders and light-splitting switches
• Towards a universal approach for the finite departure problem in overlay networks
• Spanders: distributed spanning expanders
• Self-Stabilizing and Self-Organizing Virtual Infrastructures for Mobile Networks
• TTLed random walks for collaborative monitoring in mobile and social networks
• Towards a universal approach for the finite departure problem in overlay networks
• Practically stabilizing SWMR atomic memory in message-passing systems
• DEX: self-healing expanders

This page was built for publication: Spanders: distributed spanning expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q395654)