Abstract
Assume a set of distributed nodes which are equipped with a sensor device. When nodes sense an event, they want to know (the size of) the connected component consisting of nodes which have also sensed the event, in order to raise—if necessary—a disaster alarm. This paper presents distributed algorithms for this problem. Concretely, our algorithms aim at minimizing both the response time as well as the message complexity.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Awerbuch, B., Berger, B., Cowen, L., Peleg, D.: Fast Network Decomposition. In: Proc. ACM PODC (1992)
Blelloch, G.E., Maggs, B.M.: Parallel Algorithms. In: Atallah, M.J. (ed.) Handbook of Algrorithms and Theory of Comptuation, CRC Press, Boca Raton (1998)
Birk, Y., Keidar, I., Liss, L., Schuster, A., Wolff, R.: Veracity Radius: Capturing the Locality of Distributed Computations. In: Proc. ACM PODC (2006)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press and McGraw-Hill (2001)
Dong, C.J.G., Wang, B.: Detection and Tracking of Region-Based Evolving Targets in Sensor Networks. In: Proc. 14th ICCCN (2005)
Eguchi, R.T., Huyck, C.K., Adams, B.J., Mansouri, B., Houhmand, B., Shinozuka, M.: Resilient Disaster Response: Using Remote Sensing Technologies for Post-Earthquake Damage Detection. In: Earthquake Engineering to Extreme Events (MCEER), Research Progress and Accomplishments 2001-2003 (2003)
Elkin, M.: A Faster Distributed Protocol for Constructing a Minimum Spanning Tree. In: Proc. 15th SODA (2004)
Gallager, R.G., Humblet, P.A., Spira, P.M.: A Distributed Algorithm for Minimum-Weight Spanning Trees. In: ACM TOPLAS (1983)
Kim, H.-A., Karp, B.: Autograph: Toward Automated, Distributed Worm Signature Detection. In: Proc. 13th Usenix Security Symposium (2004)
Lotker, Z., Patt-Shamir, B., Peleg, D.: Distributed MST for Constant Diameter Graphs. J. of Dist. Comp. (2006)
Peleg, D.: Time-optimal Leader Election in General Networks. J. Parallel Distrib. Comput. 8(1), 96–99 (1990)
Peleg, D.: Distributed Computing: A Locality-sensitive Approach. SIAM, Philadelphia (2000)
Schrodt, P.A.: Early Warning of Conflict in Southern Lebanon Using Hidden Markov Models. In: American Political Science Association (1997)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mans, B., Schmid, S., Wattenhofer, R. (2008). Distributed Disaster Disclosure. In: Gudmundsson, J. (eds) Algorithm Theory – SWAT 2008. SWAT 2008. Lecture Notes in Computer Science, vol 5124. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69903-3_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-69903-3_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69900-2
Online ISBN: 978-3-540-69903-3
eBook Packages: Computer ScienceComputer Science (R0)