[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Computation in networks of passively mobile finite-state sensors

  • Special Issue Podc 04
  • Published:
Distributed Computing Aims and scope Submit manuscript

Abstract

The computational power of networks of small resource-limited mobile agents is explored. Two new models of computation based on pairwise interactions of finite-state agents in populations of finite but unbounded size are defined. With a fairness condition on interactions, the concept of stable computation of a function or predicate is defined. Protocols are given that stably compute any predicate in the class definable by formulas of Presburger arithmetic, which includes Boolean combinations of threshold-k, majority, and equivalence modulo m. All stably computable predicates are shown to be in NL. Assuming uniform random sampling of interacting pairs yields the model of conjugating automata. Any counter machine with O(1) counters of capacity O(n) can be simulated with high probability by a conjugating automaton in a population of size n. All predicates computable with high probability in this model are shown to be in P; they can also be computed by a randomized logspace machine in exponential time. Several open problems and promising future directions are discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Angluin, D., Aspnes, J., Chan, M., Fischer, M.J., Jiang, H., Peralta, R.: Stably computable properties of network graphs. In: Viktor K. Prasanna, Sitharama Iyengar, Paul Spirakis and Matt Welsh (eds.), Distributed Computing in Sensor Systems: First IEEE International Conference (2005). Lecture Notes in Computer Science 3560, 63–74 (June/July, 2005) Proceedings Marina del Rey, CA, USA

  2. Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Urn automata. Tech. Rep. YALEU/DCS/TR–1280, Yale University Department of Computer Science (2003)

  3. Berry, G., Boudol, G.: The chemical abstract machine. Theor. Comp. Sci. 96, 217–248 (1992)

    Article  MathSciNet  Google Scholar 

  4. Brand, D., Zafiropulo, P.: On communicating finite-state machines. J. ACM 30(2), 323–342 (1983)

    Article  MathSciNet  Google Scholar 

  5. Diamadi, Z., Fischer, M.J.: A simple game for the study of trust in distributed systems. Wuhan Univ. J. Natur. Sci. 6(1–2), 72–82 (2001). Also appears as Yale Technical Report TR–1207, January 2001, available at URL ftp://ftp.cs.yale.edu/pub/TR/tr1207.ps

  6. Esparza, J.: Decidability and complexity of Petri net problems-an introduction. In: Rozenberg, G., Reisig, W., (eds.) Lectures on Petri Nets I: Basic models, pp. 374–428. Springer Verlag (1998). Published as LNCS 1491

  7. Esparza, J., Nielsen, M.: Decibility issues for Petri nets—a survey. J. Inform. Process. Cybern. 30(3), 143–160 (1994)

    Google Scholar 

  8. Fang, Q., Zhao, F., Guibas, L.: Lightweight sensing and communication protocols for target enumeration and aggregation. In: Proceedings of the 4th ACM International Symposium on Mobile ad hoc Networking & Computing, pp. 165–176. ACM Press (2003)

  9. Fischer, M.J., Rabin, M.O.: Super-exponential complexity of Presburger arithmetic. In: Complexity of Computation, SIAM-AMS Proceedings, vol. VII, pp. 27–41. American Mathematical Society (1974)

  10. Ginsburg, S., Spanier, E.H.: Semigroups, Presburger formulas, and languages. Pac. J. Math. 16, 285–296 (1966)

    MathSciNet  Google Scholar 

  11. Grossglauser, M., Tse, D.N.C.: Mobility increases the capacity of ad hoc wireless networks. IEEE/ACM Transac. Networking 10(4), 477–486 (2002)

    Google Scholar 

  12. Ibarra, O.H., Dang, Z., Egecioglu, O.: Catalytic p systems, semilinear sets, and vector addition systems. Theor. Comput. Sci. 312(2–3), 379–399 (2004)

    Article  MathSciNet  Google Scholar 

  13. Immerman, N.: Nondeterministic space is closed under complementation. SIAM J. Comput. 17(5), 935–938 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  14. Intanagonwiwat, C., Govindan, R., Estrin, D.: Directed diffusion: a scalable and robust communication paradigm for sensor networks. In: Proceedings of the 6th Annual International Conference on Mobile computing and networking, pp. 56–67. ACM Press (2000)

  15. Kracht, M.: The Mathematics of Language, Studies in Generative Grammar, vol. 63. Mouton de Gruyter (2003). ISBN 3-11-017620-3

  16. Madden, S.R., Franklin, M.J., Hellerstein, J.M., Hong, W.: TAG: A Tiny AGgregation service for ad-hoc sensor networks (December, 2002). In OSDI 2002: Fifth Symposium on Operating Systems Design and Implementation

  17. Milner, R.: Bigraphical reactive systems: basic theory. Tech. rep., University of Cambridge (2001). UCAM-CL-TR-523

  18. Minsky, M.L.: Computation: Finite and Infinite Machines. Prentice-Hall Series in Automatic Computation. Prentice-Hall, Inc., Englewood Cliffs, N.J. (1967)

    Google Scholar 

  19. Monk, J.D.: Mathematical Logic. Springer, Berlin, Heidelberg (1976)

    Google Scholar 

  20. von Neumann, J.: Theory and organization of complicated automata. In: A.W. Burks (ed.) Theory of Self-Reproducing Automata [by] John von Neumann, pp. 29–87 (Part One). University of Illinois Press, Urbana (1949). Based on transcripts of lectures delivered at the University of Illinois, in December 1949. Edited for publication by A.W. Burks

  21. Parikh, R.J.: On context-free languages. J. ACM 13(4), 570–581 (1966).

    Article  MATH  MathSciNet  Google Scholar 

  22. Presburger, M.: Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. In: Comptes-Rendus du I Congrès de Mathématiciens des Pays Slaves, pp. 92–101. Warszawa (1929)

  23. Volzer, H.: Randomized non-sequential processes. In: Proceedings of CONCUR 2001-Concurrency Theory, pp. 184–201 (2001)

  24. Zhao, F., Liu, J., Liu, J., Guibas, L., Reich, J.: Collaborative signal and information processing: An information directed approach. Proc. IEEE 91(8), 1199–1209 (2003)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Yale University, New Haven, CT, 06520-8285, USA

    Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer & René Peralta

Authors
  1. Dana Angluin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. James Aspnes
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zoë Diamadi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Michael J. Fischer
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. René Peralta
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michael J. Fischer.

Additional information

Supported in part by NSF grants CCR-9820888, CCR-0098078, and CNS-0305258 (Aspnes), by ONR grant N00014-01-1-0795 (Diamadi), and by NSF grant CSE-0081823 (Fischer and Peralta).

A preliminary version of this paper appeared in the proceedings of the 23rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, St. John’s, Newfoundland, Canada, July 2004.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Angluin, D., Aspnes, J., Diamadi, Z. et al. Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18, 235–253 (2006). https://doi.org/10.1007/s00446-005-0138-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00446-005-0138-3

Keywords

Search

Navigation