Feedback from nature, an optimal distributed algorithm for \textsc{Maximal Independent Set} selection

DOI10.1145/2484239.2484247MaRDI QIDQ5176090zbMATH OpenOpenAlexFDO

Authors Alex Scott, P. Jeavons, Lei Xu

Publication date 2 March 2015

Published in Proceedings of the 2013 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.0235

zbMATH Keywords

beeping modelexpected complexityfeedbackintercellular signallingmessage complexitymisrandomised algorithms

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Randomized algorithms (68W20) Cell biology (92C37)

Abstract: Maximal Independent Set selection is a fundamental problem in distributed computing. A novel probabilistic algorithm for this problem has recently been proposed by Afek et al, inspired by the study of the way that developing cells in the fly become specialised. The algorithm they propose is simple and robust, but not as efficient as previous approaches: the expected time complexity is O(log^2 n). Here we first show that the approach of Afek et al cannot achieve better efficiency than this across all networks, no matter how the probability values are chosen. However, we then propose a new algorithm that incorporates another important feature of the biological system: adapting the probabilities used at each node based on local feedback from neighbouring nodes. Our new algorithm retains all the advantages of simplicity and robustness, but also achieves the optimal efficiency of O(log n) expected time.

Recommendations

• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
• \textsc{Maximal Independent Sets} in radio networks
• An optimal maximal independent set algorithm for bounded-independence graphs
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• An Improved Distributed Algorithm for Maximal Independent Set

Cited in

(9)

• Design patterns in beeping algorithms: examples, emulation, and analysis
• Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge
• Counting in one-hop beeping networks
• A biological solution to a fundamental distributed computing problem
• Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds
• Beeping a deterministic time-optimal leader election
• Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
• The \(k\)-observer problem on \(d\)-regular graphs
• Rounds vs. communication tradeoffs for maximal independent sets

This page was built for publication: Feedback from nature, an optimal distributed algorithm for \textsc{Maximal Independent Set} selection

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