Naming a Channel with Beeps

• Autorzy: Chlebus B. S. , De Marco G. , Talo M.

Identyfikatory

DOI

10.3233/FI-2017-1537

• Języki publikacji: EN

Abstrakty

EN

We consider a communication channel in which the only available mode of communication is transmitting beeps. A beep transmitted by a station attached to the channel reaches all the other stations instantaneously. Stations are anonymous, in that they do not have any individual identifiers. The algorithmic goal is to assign names to the stations in such a manner that the names make a contiguous segment of positive integers starting from 1. We develop a Las Vegas naming algorithm, for the case when the number of stations n is known, and a Monte Carlo algorithm, for the case when the number of stations n is not known. The given randomized algorithms are provably optimal with respect to the expected time O(n log n), the expected number of used random bits O(n log n), and the probability of error.

Słowa kluczowe

EN

anonymous network; beeping channel; Las Vegas algorithm; lower bound; Monte Carlo algorithm; randomized algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 153, nr 3
• Strony: 199--219
• Opis fizyczny: Bibliogr. 57 poz.

Twórcy

autor

Chlebus B. S.

• Department of Computer Science and Engineering, University of Colorado Denver, Denver, Colorado 80217, USA

autor

De Marco G.

• Dipartimento di Informatica, Università degli Studi di Salerno Fisciano, 84084 Salerno, Italy

autor

Talo M.

• Bilgisayar Mühendisliği, Munzur Üniversitesi 62000 Tunceli, Turkey

Bibliografia

• [1] Goussevskaia O, Pignolet YA, Wattenhofer R. Efficiency of Wireless Networks: Approximation Algorithms for the Physical Interference Model. Foundations and Trends in Networking, 2010;4(3):313–420. doi:10.1561/1300000019.
• [2] Jurdziński T, Kowalski DR. Distributed Randomized Broadcasting in Wireless Networks under the SINR Model. In: Kao MY (ed.), Encyclopedia of Algorithms. Springer US, 2014. doi:10.1007/978-1-4939-2864-4_604.
• [3] Schmid S, Wattenhofer R. Algorithmic models for sensor networks. In: Proceedings of the 20th International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2006 doi:10.1109/IPDPS.2006.1639417.
• [4] Afek Y, Alon N, Barad O, Hornstein E, Barkai N, Bar-Joseph Z. A Biological Solution to a Fundamental Distributed Computing Problem. Science, 2011;331(6014):183–185. doi:10.1126/science.1193210.
• [5] Navlakha S, Bar-Joseph Z. Distributed Information Processing in Biological and Computational Systems. Communications of the ACM, 2014;58(1):94–102. doi:10.1145/2678280.
• [6] Jeavons P, Scott A, Xu L. Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring. Distributed Computing, 2016;29(5):377–393. doi:10.1007/s00446-016-0269-8.
• [7] Angluin D, Aspnes J, Diamadi Z, Fischer MJ, Peralta R. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 2006;18(4):235–253. doi:10.1007/s00446-005-0138-3.
• [8] Angluin D, Aspnes J, Fischer MJ, Jiang H. Self-stabilizing population protocols. ACM Transactions on Autonomous and Adaptive Systems, 2008;3(4). doi:10.1145/1452001.1452003.
• [9] Aspnes J, Ruppert E. An Introduction to Population Protocols. Bulletin of the EATCS, 2007;93:98–117.
• [10] Michail O, Chatzigiannakis I, Spirakis PG. New Models for Population Protocols. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2011. doi:10.2200/S00328ED1V01Y201101DCT006.
• [11] Emek Y,Wattenhofer R. Stone Age Distributed Computing. In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC). 2013 pp. 137–146. doi:10.1145/2484239.2484244.
• [12] Cornejo A, Kuhn F. Deploying Wireless Networks with Beeps. In: Proceedings of the 24th International Symposium on Distributed Computing (DISC), volume 6343 of Lecture Notes in Computer Science. Springer, 2010 pp. 148–162. doi:10.1007/978-3-642-15763-9_15.
• [13] Degesys J, Rose I, Patel A, Nagpal R. DESYNC: self-organizing desynchronization and TDMA on wireless sensor networks. In: Proceedings of the 6th International Conference on Information Processing in Sensor Networks (IPSN). ACM, 2007 pp. 11–20. doi:10.1145/1236360.1236363.
• [14] Motskin A, Roughgarden T, Skraba P, Guibas LJ. Lightweight Coloring and Desynchronization for Networks. In: Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM). 2009 pp. 2383–2391. doi:10.1109/INFCOM.2009.5062165.
• [15] Flury R, Wattenhofer R. Slotted programming for sensor networks. In: Proceedings of the 9th International Conference on Information Processing in Sensor Networks (IPSN). ACM, 2010 pp. 24–34. doi:10.1145/1791212.1791216.
• [16] Afek Y, Alon N, Bar-Joseph Z, Cornejo A, Haeupler B, Kuhn F. Beeping a maximal independent set. Distributed Computing, 2013;26(4):195–208. doi:10.1007/s00446-012-0175-7.
• [17] Brandes P, Kardas M, Klonowski M, Pająk D,Wattenhofer R. Approximating the Size of a Radio Network in Beeping Model. In: Proceedings of the 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO), volume 9988 of Lecture Notes in Computer Science. Springer, 2016 pp. 358–373. doi:10.1007/978-3-319-48314-6_23.
• [18] Czumaj A, Davies P. Communicating with Beeps. In: Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS), volume 46 of LIPIcs. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015 pp. 30:1–30:16. doi:10.4230/LIPIcs.OPODIS.2015.30.
• [19] Hounkanli K, Pelc A. Asynchronous Broadcasting with Bivalent Beeps. In: Proceedings of the 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO), volume 9988 of Lecture Notes in Computer Science. Springer, 2016 pp. 291–306. doi:10.1007/978-3-319-48314-6_19.
• [20] Förster K, Seidel J, Wattenhofer R. Deterministic Leader Election in Multi-hop Beeping Networks-(Extended Abstract). In: Proceedings of the 28th International Symposium on Distributed Computing (DISC), volume 8784 of Lecture Notes in Computer Science. Springer, 2014 pp. 212–226. doi:10.1007/978-3-662-45174-8_15.
• [21] Gilbert S, Newport CC. The Computational Power of Beeps. In: Proceedings of the 29th International Symposium on Distributed Computing (DISC), volume 9363 of Lecture Notes in Computer Science. Springer, 2015 pp. 31–46. doi:10.1007/978-3-662-48653-5_3.
• [22] Huang B, Moscibroda T. Conflict Resolution and Membership Problem in Beeping Channels. In: Proceedings of the 27th International Symposium on Distributed Computing (DISC), volume 8205 of Lecture Notes in Computer Science. Springer, 2013 pp. 314–328. doi:10.1007/978-3-642-41527-2_22.
• [23] Yu J, Jia L, Yu D, Li G, Cheng X. Minimum connected dominating set construction in wireless networks under the beeping model. In: Proceedings of the 2015 IEEE Conference on Computer Communications (INFOCOM). 2015 pp. 972–980. doi:10.1109/INFOCOM.2015.7218469.
• [24] Chlebus BS. Randomized Communication in Radio Networks. In: Pardalos PM, Rajasekaran S, Reif JH, Rolim JDP (eds.), Handbook of Randomized Computing, volume I, pp. 401–456. Kluwer Academic Publishers, 2001.
• [25] Anta AF, Mosteiro MA, Muñoz JR. Unbounded Contention Resolution in Multiple-Access Channels. Algorithmica, 2013;67(3):295–314. doi:10.1007/s00453-013-9816-x.
• [26] Capetanakis J. Tree algorithms for packet broadcast channels. IEEE Transactions on Information Theory, 1979;25(5):505–515. doi:10.1109/TIT.1979.1056093.
• [27] Cidon I, Sidi M. Conflict multiplicity estimation and batch resolution algorithms. IEEE Transactions on Information Theory, 1988. 34(1):101–110. doi:10.1109/18.2608.
• [28] De Marco G, Kowalski DR. Towards Power-Sensitive Communication on a Multiple-Access Channel. In: Proceedings of the 2010 International Conference on Distributed Computing Systems (ICDCS). IEEE Computer Society, 2010 pp. 728–735. doi:10.1109/ICDCS.2010.50.
• [29] De Marco G, Kowalski DR. Contention Resolution in a Non-synchronized Multiple Access Channel. In: Proceedings of the 27th IEEE International Symposium on Parallel and Distributed Processing (IPDPS). 2013 pp. 525–533. doi:10.1109/IPDPS.2013.68.
• [30] De Marco G, Kowalski DR. Fast Nonadaptive Deterministic Algorithm for Conflict Resolution in a Dynamic Multiple-Access Channel. SIAM Journal on Computing, 2015;44(3):868–888. doi:10.1137/140982763.
• [31] Greenberg AG, Flajolet P, Ladner RE. Estimating the multiplicities of conflicts to speed their resolution in multiple access channels. Journal of the ACM, 1987;34(2):289–325. doi:10.1145/23005.23006.
• [32] Hayes JF. An Adaptive Technique for Local Distribution. IEEE Transactions on Communications, 1978;26(8):1178–1186. doi:10.1109/TCOM.1978.1094204.
• [33] Tsybakov BS, Mikhailov VA. Free synchronous packet access in a broadcast channel with feedback. Problems of Information Transmission, 1978;14(4):259–280.
• [34] De Marco G, Pellegrini M, Sburlati G. Faster deterministic wakeup in multiple access channels. Discrete Applied Mathematics, 2007;155(8):898–903. doi:10.1016/j.dam.2006.08.009.
• [35] Gąsieniec L, Pelc A, Peleg D. The Wakeup Problem in Synchronous Broadcast Systems. SIAM Journal on Discrete Mathematics, 2001;14(2):207–222. doi:10.1137/S0895480100376022.
• [36] Chlebus BS, Gąsieniec L, Kowalski DR, Radzik T. On the wake-up problem in radio networks. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), volume 3580 of Lecture Notes in Computer Science. Springer, 2005 pp. 347–359. doi:10.1007/11523468_29.
• [37] Chlebus BS, De Marco G, Kowalski DR. Scalable Wake-up of Multi-Channel Single-Hop Radio Networks. In: Proceedings of the 18th International Conference on Principles of Distributed Systems (OPODIS), volume 8878 of Lecture Notes in Computer Science. Springer, 2014 pp. 186–201. doi:10.1007/978-3-319-14472-6_13.
• [38] Chlebus BS, De Marco G, Kowalski DR. Scalable wake-up of multi-channel single-hop radio networks. Theoretical Computer Science, 2016;615:23–44. doi:10.1016/j.tcs.2015.11.046.
• [39] Ghaffari M, Haeupler B. Near Optimal Leader Election in Multi-Hop Radio Networks. In: Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2013 pp. 748–766. doi:10.1137/1.9781611973105.54.
• [40] Ghaffari M, Haeupler B, Khabbazian M. Randomized broadcast in radio networks with collision detection. Distributed Computing, 2015;28(6):407–422. doi:10.1007/s00446-014-0230-7.
• [41] Angluin D. Local and Global Properties in Networks of Processors (Extended Abstract). In: Proceedings of the 12th ACM Symposium on Theory of Computing (STOC). 1980 pp. 82–93. doi:10.1145/800141.804655.
• [42] Attiya H, Snir M, Warmuth MK. Computing on an anonymous ring. Journal of the ACM, 1988;35(4):845–875. doi:10.1145/48014.48247.
• [43] Kranakis E, Krizanc D. Distributed Computing on Anonymous Hypercube Networks. Journal of Algorithms, 1997;23(1):32–50. doi:10.1006/jagm.1996.0817.
• [44] Afek Y, Matias Y. Elections in Anonymous Networks. Information and Computation, 1994;113(2):312–330. doi:10.1006/inco.1994.1075.
• [45] Schieber B, Snir M. Calling Names on Nameless Networks. Information and Computation, 1994;113(1):80–101. doi:10.1006/inco.1994.1065.
• [46] Lipton RJ, Park A. The processor identity problem. Information Processing Letters, 1990;36(2):91–94. doi:10.1016/0020-0190(90)90103-5.
• [47] Eğecioğlu Ö, Singh AK. Naming symmetric processes using shared variables. Distributed Computing, 1994;8(1):19–38. doi:10.1007/BF02283568.
• [48] Panconesi A, Papatriantafilou M, Tsigas P, Vitányi PMB. Randomized Naming Using Wait-Free Shared Variables. Distributed Computing, 1998;11(3):113–124. doi:10.1007/s004460050045.
• [49] Kutten S, Ostrovsky R, Patt-Shamir B. The Las-Vegas Processor Identity Problem (How and When to Be Unique). Journal of Algorithms, 2000;37(2):468–494. doi:10.1006/jagm.2000.1110.
• [50] Buhrman H, Panconesi A, Silvestri R, Vitanyi P. On the importance of having an identity or, is consensus really universal? Distributed Computing, 2006;18(3):167–176. doi:10.1007/s00446-005-0121-z.
• [51] Chlebus BS, De Marco G, Talo M. Anonymous Processors with Synchronous Shared Memory. CoRR, 2015. abs/1507.02272.
• [52] Attiya H, Ellen F. Impossibility Results for Distributed Computing. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2014. doi:10.2200/S00551ED1V01Y201311DCT012.
• [53] Fich FE, Ruppert E. Hundreds of impossibility results for distributed computing. Distributed Computing, 2003;16(2-3):121–163. doi:10.1007/s00446-003-0091-y.
• [54] Yao AC. Probabilistic Computations: Toward a Unified Measure of Complexity. In: Proceedings of the 18th Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 1977 pp. 222–227. doi:10.1109/SFCS.1977.24.
• [55] Fich FE, Meyer auf der Heide F, Ragde P, Wigderson A. One, Two, Three. . . Infinity: Lower Bounds for Parallel Computation. In: Proceedings of the 17th ACM Symposium on Theory of Computing (STOC). 1985 pp. 48–58. doi:10.1145/22145.22151.
• [56] Motwani R, Raghavan P. Randomized Algorithms. Cambridge University Press, 1995.
• [57] Cover TM, Thomas JA. Elements of Information Theory. Wiley, 2nd edition, 2006.