Beeping a maximal independent set
详细信息 查看全文
- 作者：Yehuda Afek (1)
Noga Alon (2)
Ziv Bar-Joseph (3)
Alejandro Cornejo (4)
Bernhard Haeupler (4)
Fabian Kuhn (5) - 关键词：Maximal independent set ; Distributed ; Beeps ; Radio networks ; Asynchronous wakeup
- 刊名：Distributed Computing
- 出版年：2013
- 出版时间：August 2013
- 年：2013
- 卷：26
- 期：4
- 页码：195-208
- 全文大小：318KB
- 参考文献：1. Afek, Y., Alon, N., Barad, O., Hornstein, E., Barkai, N., Bar-Joseph, Z.: A biological solution to a fundamental distributed computing problem. Science 331(6014), 183鈥?85 (2011)
2. Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567鈥?83 (1986)
3. Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network decomposition and locality in distributed computation. In: Proc. of the 30th Symposium on Foundations of Computer Science (FOCS), pp. 364鈥?69 (1989)
4. Chlebus, B., Gasieniec, L., Gibbons, A., Pelc, A., Rytter, W.: Deterministic broadcasting in unknown radio networks. In: Prof. 11th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 861鈥?70 (2000)
5. Collier, J.R., Monk, N.A., Maini, P.K., Lewis, J.H.: Pattern formation by lateral inhibition with feedback: a mathematical model of delta-notch intercellular signalling. J. Theor. Biol. 183(4), 429鈥?46 (1996) CrossRef
6. Cornejo, A., Kuhn, F.: Deploying wireless networks with beeps. In: Proc. 24th Symposium on Distributed Computing (DISC), pp. 148鈥?62 (2010)
7. Degesys, J., Rose, I., Patel, A., Nagpal, R.: Desync: self-organizing desynchronization and TDMA on wireless sensor networks. In: Prof. 6th Conf. on Information Processing in Sensor Networks (IPSN), p. 20 (2007)
8. Flury, R., Wattenhofer, R.: Slotted programming for sensor networks. In: Proc. 9th Conference on Information Processing in Sensor Networks (IPSN) (2010)
9. Ilcinkas, D., Kowalski, D., Pelc, A.: Fast radio broadcasting with advice. Theor. Comput. Sci. 411, 14鈥?5 (2010) CrossRef
10. Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In: Proc. 19th International Symposium on, Distributed Computing (DISC鈥?5), pp. 273鈥?87 (2005)
11. Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proc. 23rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 300鈥?09 (2004)
12. Kuhn, F., Moscibroda, T., Wattenhofer R.: The price of being near-sighted. In: Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 980鈥?89 (2006)
13. Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 1036鈥?053 (1986) CrossRef
14. M茅tivier, Y., Michael Robson, J., Saheb-Djahromi, N., Zemmari, A.: An optimal bit complexity randomized distributed mis algorithm. Distrib. Comput. 23, 331鈥?40 (2011)
15. Moscibroda, T., Wattenhofer, R.: Efficient computation of maximal independent sets in structured multi-hop radio networks. In: Proc. of 1st International Conference on Mobile Ad Hoc Sensor Systems (MASS) (2004)
16. Moscibroda, T., Wattenhofer, R.: Maximal independent sets in radio networks. In: Proc. 24th Symposium on Principles of Distributed Computing (PODC) (2005)
17. Motskin, A., Roughgarden, T., Skraba, P., Guibas, L.: Lightweight coloring and desynchronization for networks. In: Proc. 28th IEEE Conf. on Computer Communications (INFOCOM) (2009)
18. Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. J. Algorithms 20(2), 581鈥?92 (1995)
19. Peleg, D.: Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, Philadelphia (2000) CrossRef
20. Scheideler, C., Richa, A., Santi, P.: An ${O}(\log n)$ dominating set protocol for wireless ad-hoc networks under the physical interference model. In: Proc. 9th Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC) (2008)
21. Schneider, J., Wattenhofer, R.: A Log-Star Maximal Independent Set Algorithm for Growth-Bounded Graphs. In: Proc. 28th Symposium on Principles of Distributed Computing (PODC) (2008)
22. Schneider, J., Wattenhofer, R.: What is the use of collision detection (in wireless networks)? In: Proc. of 24th Symposium on Distributed Computing (DISC) (2010)
23. Wan, P.J., Alzoubi, K.M., Frieder, O.: Distributed construction of connected dominating set in wireless ad hoc networks. Mobile Netw. Appl. 6343, 133鈥?47 (2004) - 作者单位：Yehuda Afek (1)
Noga Alon (2)
Ziv Bar-Joseph (3)
Alejandro Cornejo (4)
Bernhard Haeupler (4)
Fabian Kuhn (5)
1. The Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv, 69978, Israel
2. Sackler School of Mathematics, Tel Aviv University, Tel Aviv, 69978, Israel
3. School of Computer Science, Carnegie Mellon Univ., Pittsburgh, PA, 15213, USA
4. Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA
5. Department of Computer Science, University of Freiburg, Freiburg, 79110, Germany
文摘
We consider the problem of computing a maximal independent set (MIS) in an extremely harsh broadcast model that relies only on carrier sensing. The model consists of an anonymous broadcast network in which nodes have no knowledge about the topology of the network or even an upper bound on its size. Furthermore, it is assumed that an adversary chooses at which time slot each node wakes up. At each time slot a node can either beep, that is, emit a signal, or be silent. At a particular time slot, beeping nodes receive no feedback, while silent nodes can only differentiate between none of its neighbors beeping, or at least one of its neighbors beeping. We start by proving a lower bound that shows that in this model, it is not possible to locally converge to an MIS in sub-polynomial time. We then study four different relaxations of the model which allow us to circumvent the lower bound and find an MIS in polylogarithmic time. First, we show that if a polynomial upper bound on the network size is known, it is possible to find an MIS in $\mathcal O (\log ^3 n)$ time. Second, if we assume sleeping nodes are awoken by neighboring beeps, then we can also find an MIS in $\mathcal O (\log ^3 n)$ time. Third, if in addition to this wakeup assumption we allow sender-side collision detection, that is, beeping nodes can distinguish whether at least one neighboring node is beeping concurrently or not, we can find an MIS in $\mathcal O (\log ^2 n)$ time. Finally, if instead we endow nodes with synchronous clocks, it is also possible to find an MIS in $\mathcal O (\log ^2 n)$ time.