The Computational Power of Beeps

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9363
• 期：1
• 页码：31-46
• 全文大小：227 KB
• 参考文献：1. Afek, Y., Alon, N., Bar-Joseph, Z., Cornejo, A., Haeupler, B., Kuhn, F.: Beeping a maximal independent set. In: Peleg, D. (ed.) Distributed Computing. LNCS, vol. 6950, pp. 32–50. Springer, Heidelberg (2011) CrossRef
  2.Afek, Y., Alon, N., Bar-Joseph, Z., Cornejo, A., Haeupler, B., Kuhn, F.: Beeping a maximal independent set. Distributed Computing 26(4), 195–208 (2013)MATH CrossRef
  3.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–185 (2011)MATH MathSciNet CrossRef
  4.Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distributed Computing 18(4), 235–253 (2006)MATH CrossRef
  5.Angluin, D., Aspnes, J., Eisenstat, D.: Stably computable predicates are semilinear. In: Proceedings of the Symposium on Principles of Distributed Computing (PODC), pp. 292–299 (2006)
  6.Angluin, D., Aspnes, J., Eisenstat, D.: Fast computation by population protocols with a leader. Distributed Computing 21(3), 183–199 (2008)MATH CrossRef
  7.Angluin, D., Aspnes, J., Eisenstat, D.: A simple population protocol for fast robust approximate majority. Distributed Computing 21(2), 87–102 (2008)MATH CrossRef
  8.Angluin, D., Aspnes, J., Eisenstat, D., Ruppert, E.: The computational power of population protocols. Distributed Computing 20(4), 279–304 (2007)MATH CrossRef
  9. Chatzigiannakis, I., Spirakis, P.G.: The dynamics of probabilistic population protocols. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol. 5218, pp. 498–499. Springer, Heidelberg (2008) CrossRef
  10. Cornejo, A., Kuhn, F.: Deploying wireless networks with beeps. In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol. 6343, pp. 148–162. Springer, Heidelberg (2010) CrossRef
  11.Degesys, J., Nagpal, R.: Towards desynchronization of multi-hop topologies. In: Proceedings of the International Conference on Self-Adaptive and Self-Organizing Systems (SASO 2008) (2008)
  12.Degesys, J., Rose, I., Patel, A., Nagpal, R.: Desync: self-organizing desynchronization and tdma on wireless sensor networks. In: Proceedings of the International Conference on Information Processing in Sensor Networks (2007)
  13.Emek, Y., Wattenhofer, R.: Stone age distributed computing. In: Proceedings of the Symposium on Principles of Distributed Computing (PODC) (2013)
  14. Förster, K.-T., Seidel, J., Wattenhofer, R.: Deterministic leader election in multi-hop beeping networks - (extended abstract). In: Kuhn, F. (ed.) DISC 2014. LNCS, vol. 8784, pp. 212–226. Springer, Heidelberg (2014)
  15.Gilbert, S., Newport, C.: The computational power of beeps. Full version available online at. http://​people.​cs.​georgetown.​edu/​~cnewport/​pubs/​Beeps-Full.​pdf (arXiv)
  16.Lenzen, C., Lynch, N., Newport, C., Radeva, T.: Trade-offs between selection complexity and performance when searching the plane without communication. In: Proceedings of the Symposium on Principles of Distributed Computing (PODC) (2014)
  17.Minsky, M.L.: Computation: finite and infinite machines. Prentice-Hall (1967)
  18.Motskin, A., Roughgarden, T., Skraba, P., Guibas, L.J.: Lightweight coloring and desynchronization for networks. In: Proceedings of the of the Conference on Computer Communication (INFOCOM) (2009)
  19.Navlakha, S., Bar-Joseph, Z.: Distributed information processing in biological and computational systems. Communications of the ACM 58(1), 94–102 (2014)CrossRef
  20.Scott, A., Jeavons, P., Xu, L.: Feedback from nature: an optimal distributed algorithm for maximal independent set selection. In: Proceedings of the Symposium on Principles of Distributed Computing (PODC) (2013)
  
• 作者单位：Seth Gilbert (14)
  Calvin Newport (15)
  
  14. National University of Singapore, Singapore, Singapore
  15. Georgetown University, Washington, D.C, USA
  
• 丛书名：Distributed Computing
• ISBN：978-3-662-48653-5
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

We study the quantity of computational resources (state machine states and/or probabilistic transition precision) needed to solve specific problems in a single hop network where nodes communicate using only beeps. We begin by focusing on randomized leader election. We prove a lower bound on the states required to solve this problem with a given error bound, probability precision, and (when relevant) network size lower bound. We then show the bound tight with a matching upper bound. Noting that our optimal upper bound is slow, we describe two faster algorithms that trade some state optimality to gain efficiency. We then turn our attention to more general classes of problems by proving that once you have enough states to solve leader election with a given error bound, you have (within constant factors) enough states to simulate correctly, with this same error bound, a logspace TM with a constant number of unary input tapes: allowing you to solve a large and expressive set of problems. These results identify a key simplicity threshold beyond which useful distributed computation is possible in the beeping model.