Sensor Networks: Distributed Algorithms Reloaded – or Revolutions?

  • Roger Wattenhofer
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4056)


This paper wants to motivate the distributed algorithms community to study sensor networks. We discuss why sensor networks are distributed algorithms, and why they are not.


Sensor Network Medium Access Control Localize Algorithm Annual IEEE Symposium Unit Disk Graph 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Abramson, N.: The ALOHA System. In: Computer-Communication Networks, Prentice-Hall, Englewood Cliffs (1973)Google Scholar
  2. 2.
    Alon, N., Bar-Noy, A., Linial, N., Peleg, D.: A Lower Bound for Radio Broadcast. Journal of Computer and System Sciences (1991)Google Scholar
  3. 3.
    Awerbuch, B., Varghese, G.: Distributed Program Checking: A Paradigm for Building Self-stabilizing Distributed Protocols. In: 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) (1991)Google Scholar
  4. 4.
    Dijkstra, E.W.: Self-stabilizing Systems in Spite of Distributed Control. Communications of the ACM (1974)Google Scholar
  5. 5.
    Estrin, D., Govindan, R., Heidemann, J.S., Kumar, S.: Next Century Challenges: Scalable Coordination in Sensor Networks. In: Fifth Annual International Conference on Mobile Computing and Networking (MobiCom) (1999)Google Scholar
  6. 6.
    Kuhn, F., Moscibroda, T., Wattenhofer, R.: Initializing Newly Depoloyed Ad-hoc and Sensor Networks. In: 10th Annual Intl. Conf. on Mobile Computing and Networking (MobiCom) (2004)Google Scholar
  7. 7.
    Kuhn, F., Moscibroda, T., Wattenhofer, R.: The Price of Being Near-Sighted. In: ACM-SIAM Symp. on Discrete Algorithms (SODA) (2006)Google Scholar
  8. 8.
    Linial, N.: Distributive Graph Algorithms – Global Solutions from Local Data. In: 28th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (1987)Google Scholar
  9. 9.
    Luby, M.: A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM Journal on Computing (1986)Google Scholar
  10. 10.
    Peleg, D.: Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2000)zbMATHCrossRefGoogle Scholar
  11. 11.
    Roberts, L.G.: Aloha packet system with and without slots and capture. Computer Communication Review (1975)Google Scholar
  12. 12.
    Schmid, S., Wattenhofer, R.: Algorithmic Models for Sensor Networks. In: 14th International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS), Island of Rhodes, Greece (April 2006)Google Scholar
  13. 13.
    Wang, Y., Li, X.-Y., Wan, P.-J., Frieder, O.: Sparse Power Efficient Topology for Wireless Networks. Journal of Parallel and Distributed Computing (2002)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Roger Wattenhofer
    • 1
  1. 1.Computer Engineering and Networks LaboratoryETH ZurichZurichSwitzerland

Personalised recommendations