| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Causality-Based Predicate Detection across Space and Time
November 2005 (vol. 54 no. 11)
pp. 1438-1453
This paper presents event stream-based online algorithms that fuse the data reported from processes to detect causality-based predicates of interest. The proposed algorithms have the following features. 1) The algorithms are based on logical time, which is useful to detect "cause and effect” relationships in an execution. 2) The algorithms detect properties that can be specified using predicates under a rich palette of time modalities. Specifically, for a conjunctive predicate \phi, the algorithms can detect the exact fine-grained time modalities between each pair of intervals, one interval at each process, with low space, time, and message complexities. The main idea used to design the algorithms is that any "cause and effect” interaction can be decomposed as a collection of interactions between pairs of system components. The detection algorithms, which leverage the pairwise interaction among the processes, incur a low overhead and are, hence, highly scalable. The paper then shows how the algorithms can deal with mobility in mobile ad hoc networks.
[1] I. Akyildiz, W. Su, Y. Sankarasubramanian, and E. Cayirci, “Wireless Sensor Networks: A Survey,” Computer Networks, vol. 38, no. 4, pp. 393-422, 2002.
[2] A. Amis, R. Prakash, T. Vuong, and D. Huynh, “Max-Min D-Cluster Formation in Wireless Ad-Hoc Networks,” Proc. IEEE Infocom, pp. 32-41, 2000.
[3] S. Banerjee and S. Khuller, “A Clustering Scheme for Hierarchical Control in Multi-Hop Wireless Networks,” Proc. IEEE Infocom, pp. 1028-1037, Apr. 2001.
[4] D. Baker and A. Ephremedis, “The Architectural Organization of a Mobile Radio Network via a Distributed Algorithm,” IEEE Trans. Comm., vol. 29, pp. 1694-1701, Nov. 1981.
[5] P. Chandra and A.D. Kshemkalyani, “Detection of Orthogonal Interval Relations,” Proc. Ninth Int'l Conf. High-Performance Computing, pp. 323-333, 2002.
[6] P. Chandra and A.D. Kshemkalyani, “Distributed Detection of Temporal Interval Interactions,” Technical Report UIC-ECE-02-07, Univ. of Illinois at Chicago, Apr. 2002.
[7] P. Chandra and A.D. Kshemkalyani, “Distributed Algorithm to Detect Strong Conjunctive Predicates,” Information Processing Letters, vol. 87, no. 5, pp. 243-249, Sept. 2003.
[8] P. Chandra and A.D. Kshemkalyani, “Global Predicate Detection under Fine-Grained Modalities,” Proc. ASIAN Computing Science Conf. 2003, pp. 91-109, Dec. 2003.
[9] K.M. Chandy and L. Lamport, “Distributed Snapshots: Determining Global States of Distributed Systems,” ACM Trans. Computer Systems, vol. 3, no. 1, pp. 63-75, 1985.
[10] C.-C. Chiang, M. Gerla, and L. Zhang, “Tree Multicast Strategies in Mobile, Multihop Wireless Networks,” Mobile Networks and Applications (MONET), vol. 3, pp. 193-207, 1999.
[11] G. Coulouris, J. Dollimore, and T. Kindberg, Distributed Systems Concepts and Design, third ed. Addison-Wesley, 2001.
[12] R. Cooper and K. Marzullo, “Consistent Detection of Global Predicates,” Proc. ACM/ONR Workshop Parallel and Distributed Debugging, pp. 163-173, May 1991.
[13] J. Elson and K. Romer, “Wireless Sensor Networks: A New Regime for Time Synchronization,” Proc. First Workshop Hot Topics in Networks (HotNets-I), Oct. 2002.
[14] C.J. Fidge, “Timestamps in Message-Passing Systems that Preserve Partial Ordering,” Australian Computer Science Comm., vol. 10, no. 1, pp. 56-66, Feb. 1988.
[15] V.K. Garg and B. Waldecker, “Detection of Weak Unstable Predicates in Distributed Programs,” IEEE Trans. Parallel and Distributed Systems, vol. 5, no. 3, pp. 299-307, Mar. 1994.
[16] V.K. Garg and B. Waldecker, “Detection of Strong Unstable Predicates in Distributed Programs,” IEEE Trans. Parallel and Distributed Systems, vol. 7, no. 12, pp. 1323-1333, Dec. 1996.
[17] P. Chandra and A.D. Kshemkalyani, “Global State Detection Based on Peer-to-Peer Interactions,” Proc. IFIP Int'l Conf. Embedded and Ubiquitous Computing, Dec. 2005.
[18] M. Hurfin, M. Mizuno, M. Raynal, and M. Singhal, “Efficient Distributed Detection of Conjunctions of Local Predicates,” IEEE Trans. Software Eng., vol. 24, no. 8, pp. 664-677, Aug. 1998.
[19] A.D. Kshemkalyani, “Temporal Interactions of Intervals in Distributed Systems,” J. Computer and System Sciences, vol. 52, no. 2, pp. 287-298, Apr. 1996.
[20] A.D. Kshemkalyani, “A Fine-Grained Modality Classification for Global Predicates,” IEEE Trans. Parallel and Distributed Systems, vol. 14, no. 8, pp. 807-816, Aug. 2003.
[21] A.D. Kshemkalyani, “A Note on Fine-Grained Modalities for Nonconjunctive Predicates,” Proc. Fifth Int'l Workshop Distributed Computing, pp. 11-25, Dec. 2003.
[22] A.D. Kshemkalyani, “The Power of Logical Clock Abstractions,” Distributed Computing, vol. 17, no. 2, pp. 131-150, Aug. 2004.
[23] A.D. Kshemkalyani, “Predicate Detection Using Event Streams in Ubiquitous Environments,” Proc. Int'l Symp. Network-Centric Ubiquitous Systems, Dec. 2005.
[24] L. Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System,” Comm. ACM, vol. 21, no. 7, pp. 558-565, July 1978.
[25] L. Lamport, “On Interprocess Communication, Part I: Basic Formalism; Part II: Algorithms,” Distributed Computing, vol. 1, pp. 77-85, vol. 1, pp. 86-101, 1986.
[26] C.R. Lin and M. Gerla, “Adaptive Clustering for Mobile Wireless Networks,” IEEE J. Selected Areas in Comm., vol. 15, no. 7, pp. 1265-1275, Sept. 1997.
[27] T. Logsdon, The Navstar Global Positioning System. New York: Van Nostrand/Reinhold, 1992.
[28] F. Mattern, “Virtual Time and Global States of Distributed Systems,” Parallel and Distributed Algorithms, pp. 215-226, North-Holland, 1989.
[29] D. Mills, “Internet Time Synchronization: The Network Time Protocol,” IEEE Trans. Comm., vol. 39, no. 10, pp. 1482-1493, Oct. 1991.
[30] G. Pei, M. Gerla, X. Hong, and C. Chiang, “A Wireless Hierarchical Routing Protocol with Group Mobility,” IEEE Wireless Comm. and Networking Conference (WCNC), pp. 1538-1542, 1999.
[31] G. Pottie and W. Kaiser, “Wireless Integrated Network Sensors,” Comm. ACM, vol. 43, no. 5, pp. 51-58, May 2000.
[32] R. Ramanathan and M. Steenstrup, “Hierarchically Organized, Multihop Wireless Mobile Wireless Networks for Quality-Of-Service Support,” Mobile Networks and Applications (MONET), vol. 3, no. 1, pp. 101-110, June 1998.
[33] M. Raynal and M. Singhal, “Logical Time: Capturing Causality in Distributed Systems,” Computer, vol. 29, no. 2, pp. 49-56, Feb. 1996.
[34] R. Schwarz and F. Mattern, “Detecting Causal Relationships in Distributed Computations: In Search of the Holy Grail,” Distributed Computing, vol. 7, pp. 149-174, 1994.
[35] M. Singhal and A.D. Kshemkalyani, “Efficient Implementation of Vector Clocks,” Information Processing Letters, vol. 43, pp. 47-52, Aug. 1992.
[36] B. Sundararaman, U. Buy, and A.D. Kshemkalyani, “Clock Synchronization for Wireless Sensor Networks: A Survey,” Ad-Hoc Networks, vol. 3, no. 3, pp. 281-323, May 2005.
[37] S. Tilak, N. Abu-Ghazaleh, and W. Heinzelman, “A Taxonomy of Wireless Micro-Sensor Models,” ACM Mobile Computing & Comm. Rev., vol. 6, no. 2, Apr. 2002.
[38] X. Yu, K. Niyogi, S. Mehrotra, and N. Venkatasubramanian, “Adaptive Middleware for Distributed Sensor Environments,” IEEE Distributed Systems Online, vol. 4, May 2003.
Index Terms:
Index Terms- Predicates, event streams, causality, data fusion, time, space-time, mobility, ad hoc network, intervals, monitoring.
Citation:
Punit Chandra, Ajay D. Kshemkalyani, "Causality-Based Predicate Detection across Space and Time," IEEE Transactions on Computers, vol. 54, no. 11, pp. 1438-1453, Nov. 2005, doi:10.1109/TC.2005.176
