Abstract
Chandy et al. proposed the methodology of “self-similar algorithms” for distributed computation in dynamic environments. We further characterize the class of functions computable by such algorithms by showing that self-similarity induces an additive relationship among the level-sets of such functions. Angluin et al. introduced the population protocol model for computation in mobile sensor networks and characterized the class of predicates computable in a standard population. We define and characterize the class of self-similar predicates and show when they are computable by a population protocol.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Spyropoulos, T., Psounis, K., Raghavendra, C.: Efficient routing in intermittently connected mobile networks: The single-copy case. IEEE/ACM Trans. on Networking 16(1) (2008)
Grossglauser, M., Tse, D.: Mobility increases the capacity of adhoc wireless networks. IEEE/ACM Transactions on Networking 10(4), 477–486 (2002)
Chatzigiannakis, I.: Design and Analysis of Distributed Algorithms for Basic Communication in Ad-hoc Mobile Networks. Computer science and engineering, Dept. of Computer Engineering and Informatics, University of Patras (2003)
Gnawali, O., Greenstein, B., Jang, K.Y., Joki, A., Paek, J., Vieira, M., Estrin, D., Govindan, R., Kohler, E.: The TENET Architecture for Tiered Sensor Networks. In: ACM Conference on Embedded Networked Sensor Systems (Sensys), Boulder, Colorado (2006)
Palchaudhari, S., Wagner, R., Baraniuk, R.G., Johnson, D.B.: COMPASS: An adaptive sensor network architecture for multi-scale communication. IEEE Wireless Communications (submitted, 2008)
Giridhar, A., Kumar, P.R.: Computing and communicating functions over sensor networks. IEEE Journal on Selected Areas in Communications 23(4), 755–764 (2005)
Giridhar, A., Kumar, P.R.: Towards a theory of in-network computation in wireless sensor networks. IEEE Communications Magazine 44(4), 98–107 (2006)
Chandy, K.M., Charpentier, M.: Self-similar algorithms for dynamic distributed systems. In: 27th International Conference on Distributed Computing Systems (ICDCS 2007) (2007)
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distributed Computing 18(4), 235–253 (2006)
Angluin, D., Aspnes, J., Eisenstat, D., Ruppert, E.: The computational power of population protocols. Distributed Computing 20(4), 279–304 (2007)
Aspnes, J., Ruppert, E.: An introduction to population protocols. Bulletin of the European Association for Theoretical Computer Science 93, 98–117 (2007)
Bhatia, S., Bartoš, R.: Self-similar functions and population protocols: a characterization and a comparison. Technical Report UNH-TR-08-01, University of New Hampshire (2008)
Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bhatia, S., Bartoš, R. (2008). Self-similar Functions and Population Protocols: A Characterization and a Comparison. In: Garg, V., Wattenhofer, R., Kothapalli, K. (eds) Distributed Computing and Networking. ICDCN 2009. Lecture Notes in Computer Science, vol 5408. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92295-7_32
Download citation
DOI: https://doi.org/10.1007/978-3-540-92295-7_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92294-0
Online ISBN: 978-3-540-92295-7
eBook Packages: Computer ScienceComputer Science (R0)