We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring.
- Authors
Jeavons, Peter; Scott, Alex; Xu, Lei
- Abstract
We propose distributed algorithms for two well-established problems that operate efficiently under extremely harsh conditions. Our algorithms achieve state-of-the-art performance in a simple and novel way. Our algorithm for maximal independent set selection operates on a network of identical anonymous processors. The processor at each node has no prior information about the network. At each time step, each node can only broadcast a single bit to all its neighbours, or remain silent. Each node can detect whether one or more neighbours have broadcast, but cannot tell how many of its neighbours have broadcast, or which ones. We build on recent work of Afek et al. (Science 331(6014):183-185, 2011) which was inspired by studying the development of a network of cells in the fruit fly. However we incorporate for the first time another important feature of the biological system: varying the probability value used at each node based on local feedback from neighbouring nodes. Given any n-node network, our algorithm achieves with high probability the optimal time complexity of $$O(\log n)$$ rounds and the optimal expected message complexity of O(1) single-bit messages broadcast by each node. We also show that the previous approach, without feedback, cannot achieve better than $$\varOmega (\log ^2 n)$$ time complexity with high probability, whatever global scheme is used to choose the probabilities. Our algorithm for distributed greedy colouring works under similar harsh conditions: each identical node has no prior information about the network, can only broadcast a single message to all neighbours at each time step representing a desired colour, and can only detect whether at least one neighbour has broadcast each colour value. We show that with high probability our algorithm has a time complexity of $$O(\Delta +\log n)$$ , where $$\Delta $$ is the maximum degree of the network, and also has an expected message complexity of O(1) messages broadcast by each node.
- Subjects
DISTRIBUTED algorithms; BROADCAST data systems; MESSAGE processing (Telecommunication); COMPUTATIONAL complexity; PROBABILITY theory
- Publication
Distributed Computing, 2016, Vol 29, Issue 5, p377
- ISSN
0178-2770
- Publication type
Article
- DOI
10.1007/s00446-016-0269-8