Predicate detection in asynchronous pervasive environments

Ajay D. Kshemkalyani, Jiannong Cao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

5 Citations (Scopus)

Abstract

An important task in sensor networks is to sense locally to detect global properties that hold at some instant in physical time, namely, Instantaneously. We propose software logical clocks, called strobe clocks, that can be implemented by the middleware when synchronized physical clocks are not available or are too expensive in resource-constrained environments. Strobe clocks come in two flavors - scalar and vector. Let (n) be the number of sensors and (p) be the upper bound on the number of relevant events sensed at a sensor. We propose an algorithm using vector strobes that can detect all occurrences of a conjunctive predicate in time (O(n3p)). The algorithm has some false negatives but this is the best achievable accuracy in the face of race conditions. We also present a variant algorithm using scalar strobes; it needs time (O(n2p)) but may also suffer from some false positives. We provide a characterization of the errors. Both algorithms can also detect relational predicates but with a greater chance of error. The message complexity of strobe clocks (scalar and vector) and both algorithms is (O(np)), which is the same as that of reporting each sensed event for detection of the predicate even with synchronized physical clocks. We formalize the physical time modality, Instantaneously, and show its relationship to the logical time modalities Definitely and Possibly.
Original languageEnglish
Article number6226372
Pages (from-to)1823-1836
Number of pages14
JournalIEEE Transactions on Computers
Volume62
Issue number9
DOIs
Publication statusPublished - 12 Aug 2013

Keywords

  • Distributed system
  • Middleware
  • Pervasive computing
  • Predicate detection
  • Sensor networks
  • Strobe clocks

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this