{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:16:28Z","timestamp":1763468188254},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:p>The ability to reason about changes in a distributed system's state enables network administrators to better diagnose protocol misconfigurations, detect intrusions, and pinpoint performance bottlenecks. We propose a novel provenance model called Distributed Time-aware Provenance (DTaP) that aids forensics and debugging in distributed systems by explicitly representing time, distributed state, and state changes. Using a distributed Datalog abstraction for modeling distributed protocols, we prove that the DTaP model provides a sound and complete representation that correctly captures dependencies among events in a distributed system. We additionally introduce DistTape, an implementation of the DTaP model that uses novel distributed storage structures, query processing, and cost-based optimization techniques to efficiently query time-aware provenance in a distributed setting. Using two example systems (declarative network routing and Hadoop MapReduce), we demonstrate that DistTape can efficiently maintain and query time-aware provenance at low communication and computation cost.<\/jats:p>","DOI":"10.14778\/2535568.2448939","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"49-60","source":"Crossref","is-referenced-by-count":27,"title":["Distributed time-aware provenance"],"prefix":"10.14778","volume":"6","author":[{"given":"Wenchao","family":"Zhou","sequence":"first","affiliation":[{"name":"Georgetown University, Washington, DC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suyog","family":"Mapara","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yiqing","family":"Ren","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Li","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Haeberlen","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zachary","family":"Ives","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boon Thau","family":"Loo","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micah","family":"Sherr","sequence":"additional","affiliation":[{"name":"Georgetown University, Washington, DC"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,12]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"316","volume-title":"Proc. ICDT","author":"Buneman P.","year":"2001","unstructured":"P. Buneman , S. Khanna , and W. C. Tan . Why and where: A characterization of data provenance . In Proc. ICDT , pages 316 - 330 , 2001 . P. Buneman, S. Khanna, and W. C. Tan. Why and where: A characterization of data provenance. In Proc. ICDT, pages 316-330, 2001."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000006"},{"key":"e_1_2_1_3_1","first-page":"1345","volume-title":"Proc. SIGMOD","author":"Davidson S. B.","year":"2008","unstructured":"S. B. Davidson and J. Freire . Provenance and scientific workflows: challenges and opportunities . In Proc. SIGMOD , pages 1345 - 1350 , 2008 . 10.1145\/1376616.1376772 S. B. Davidson and J. Freire. Provenance and scientific workflows: challenges and opportunities. In Proc. SIGMOD, pages 1345-1350, 2008. 10.1145\/1376616.1376772"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1145\/1015467.1015491","volume-title":"Proc. SIGCOMM","author":"Feldmann A.","year":"2004","unstructured":"A. Feldmann , O. Maennel , Z. M. Mao , A. Berger , and B. Maggs . Locating internet routing instabilities . In Proc. SIGCOMM , pages 205 - 218 , 2004 . 10.1145\/1015467.1015491 A. Feldmann, O. Maennel, Z. M. Mao, A. Berger, and B. Maggs. Locating internet routing instabilities. In Proc. SIGCOMM, pages 205-218, 2004. 10.1145\/1015467.1015491"},{"key":"e_1_2_1_5_1","first-page":"675","volume-title":"Proc. VLDB","author":"Green T. J.","year":"2007","unstructured":"T. J. Green , G. Karvounarakis , Z. G. Ives , and V. Tannen . Update exchange with mappings and provenance . In Proc. VLDB , pages 675 - 686 , 2007 . T. J. Green, G. Karvounarakis, Z. G. Ives, and V. Tannen. Update exchange with mappings and provenance. In Proc. VLDB, pages 675-686, 2007."},{"key":"e_1_2_1_6_1","unstructured":"Hadoop. http:\/\/hadoop.apache.org\/. Hadoop. http:\/\/hadoop.apache.org\/."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629080.1629082"},{"key":"e_1_2_1_8_1","first-page":"273","volume-title":"Proc. CIDR","author":"Ikeda R.","year":"2011","unstructured":"R. Ikeda , H. Park , and J. Widom . Provenance for generalized map and reduce workflows . In Proc. CIDR , pages 273 - 283 , 2011 . R. Ikeda, H. Park, and J. Widom. Provenance for generalized map and reduce workflows. In Proc. CIDR, pages 273-283, 2011."},{"key":"e_1_2_1_9_1","first-page":"951","volume-title":"Proc. SIGMOD","author":"Karvounarakis G.","year":"2010","unstructured":"G. Karvounarakis , Z. G. Ives , and V. Tannen . Querying data provenance . In Proc. SIGMOD , pages 951 - 962 , 2010 . 10.1145\/1807167.1807269 G. Karvounarakis, Z. G. Ives, and V. Tannen. Querying data provenance. In Proc. SIGMOD, pages 951-962, 2010. 10.1145\/1807167.1807269"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1047915.1047918"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.65"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592761.1592785"},{"key":"e_1_2_1_13_1","first-page":"43","volume-title":"Proc. USENIX ATC","author":"Muniswamy-Reddy K.-K.","year":"2006","unstructured":"K.-K. Muniswamy-Reddy , D. A. Holland , U. Braun , and M. Seltzer . Provenance-aware storage systems . In Proc. USENIX ATC , pages 43 - 56 , 2006 . K.-K. Muniswamy-Reddy, D. A. Holland, U. Braun, and M. Seltzer. Provenance-aware storage systems. In Proc. USENIX ATC, pages 43-56, 2006."},{"key":"e_1_2_1_14_1","unstructured":"Network Simulator 3. http:\/\/www.nsnam.org\/. Network Simulator 3. http:\/\/www.nsnam.org\/."},{"issue":"12","key":"e_1_2_1_15_1","first-page":"1351","article-title":"Ramp: A system for capturing and tracing provenance in mapreduce workflows","volume":"4","author":"Park H.","year":"2011","unstructured":"H. Park , R. Ikeda , and J. Widom . Ramp: A system for capturing and tracing provenance in mapreduce workflows . PVLDB , 4 ( 12 ): 1351 - 1354 , 2011 . H. Park, R. Ikeda, and J. Widom. Ramp: A system for capturing and tracing provenance in mapreduce workflows. PVLDB, 4(12):1351-1354, 2011.","journal-title":"PVLDB"},{"key":"e_1_2_1_16_1","unstructured":"RapidNet. http:\/\/netdb.cis.upenn.edu\/rapidnet\/. RapidNet. http:\/\/netdb.cis.upenn.edu\/rapidnet\/."},{"issue":"1","key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"797","DOI":"10.14778\/1453856.1453943","article-title":"Approximate lineage for probabilistic databases","volume":"1","author":"R\u00e9 C.","year":"2008","unstructured":"C. R\u00e9 and D. Suciu . Approximate lineage for probabilistic databases . Proc. VLDB Endowment , 1 ( 1 ): 797 - 808 , 2008 . C. R\u00e9 and D. Suciu. Approximate lineage for probabilistic databases. Proc. VLDB Endowment, 1(1):797-808, 2008.","journal-title":"Proc. VLDB Endowment"},{"key":"e_1_2_1_18_1","first-page":"313","volume-title":"Proc. ACM SIGCOMM Network Troubleshooting Workshop","author":"Teixeira R.","year":"2004","unstructured":"R. Teixeira and J. Rexford . A measurement framework for pin-pointing routing changes . In Proc. ACM SIGCOMM Network Troubleshooting Workshop , pages 313 - 318 , 2004 . 10.1145\/1016687.1016704 R. Teixeira and J. Rexford. A measurement framework for pin-pointing routing changes. In Proc. ACM SIGCOMM Network Troubleshooting Workshop, pages 313-318, 2004. 10.1145\/1016687.1016704"},{"key":"e_1_2_1_19_1","first-page":"262","volume-title":"Proc. CIDR","author":"Widom J.","year":"2005","unstructured":"J. Widom . Trio : A system for integrated management of data, accuracy, and lineage . In Proc. CIDR , pages 262 - 276 , 2005 . J. Widom. Trio: A system for integrated management of data, accuracy, and lineage. In Proc. CIDR, pages 262-276, 2005."},{"key":"e_1_2_1_20_1","first-page":"57","volume-title":"Proc. NSDI","author":"Yu M.","year":"2011","unstructured":"M. Yu , A. Greenberg , D. Maltz , J. Rexford , L. Yuan , S. Kandula , and C. Kim . Profiling network performance for multi-tier data center applications . In Proc. NSDI , pages 57 - 70 , 2011 . M. Yu, A. Greenberg, D. Maltz, J. Rexford, L. Yuan, S. Kandula, and C. Kim. Profiling network performance for multi-tier data center applications. In Proc. NSDI, pages 57-70, 2011."},{"key":"e_1_2_1_21_1","volume-title":"Secure time-aware provenance for distributed systems","author":"Zhou W.","year":"2012","unstructured":"W. Zhou . Secure time-aware provenance for distributed systems . University of Pennsylvania Ph.D . dissertation, 2012 . Available at http:\/\/netdb.cis.upenn.edu\/papers\/zhou-thesis.pdf. W. Zhou. Secure time-aware provenance for distributed systems. University of Pennsylvania Ph.D. dissertation, 2012. Available at http:\/\/netdb.cis.upenn.edu\/papers\/zhou-thesis.pdf."},{"key":"e_1_2_1_22_1","first-page":"1","volume-title":"Proc. TaPP","author":"Zhou W.","year":"2011","unstructured":"W. Zhou , L. Ding , A. Haeberlen , Z. Ives , and B. T. Loo . TAP: Time-aware provenance for distributed systems . In Proc. TaPP , pages 1 - 6 , 2011 . W. Zhou, L. Ding, A. Haeberlen, Z. Ives, and B. T. Loo. TAP: Time-aware provenance for distributed systems. In Proc. TaPP, pages 1-6, 2011."},{"key":"e_1_2_1_23_1","first-page":"295","volume-title":"Proc. SOSP","author":"Zhou W.","year":"2011","unstructured":"W. Zhou , Q. Fei , A. Narayan , A. Haeberlen , B. T. Loo , and M. Sherr . Secure network provenance . In Proc. SOSP , pages 295 - 310 , 2011 . 10.1145\/2043556.2043584 W. Zhou, Q. Fei, A. Narayan, A. Haeberlen, B. T. Loo, and M. Sherr. Secure network provenance. In Proc. SOSP, pages 295-310, 2011. 10.1145\/2043556.2043584"},{"key":"e_1_2_1_24_1","first-page":"1323","volume-title":"Proc. SIGMOD","author":"Zhou W.","year":"2011","unstructured":"W. Zhou , Q. Fei , S. Sun , T. Tao , A. Haeberlen , Z. Ives , B. T. Loo , and M. Sherr . NetTrails: A declarative platform for provenance maintenance and querying in distributed systems . In Proc. SIGMOD , pages 1323 - 1326 , 2011 . 10.1145\/1989323.1989488 W. Zhou, Q. Fei, S. Sun, T. Tao, A. Haeberlen, Z. Ives, B. T. Loo, and M. Sherr. NetTrails: A declarative platform for provenance maintenance and querying in distributed systems. In Proc. SIGMOD, pages 1323-1326, 2011. 10.1145\/1989323.1989488"},{"key":"e_1_2_1_25_1","first-page":"615","volume-title":"Proc. SIGMOD","author":"Zhou W.","year":"2010","unstructured":"W. Zhou , M. Sherr , T. Tao , X. Li , B. T. Loo , and Y. Mao . Efficient querying and maintenance of network provenance at Internet-scale . In Proc. SIGMOD , pages 615 - 626 , 2010 . 10.1145\/1807167.1807234 W. Zhou, M. Sherr, T. Tao, X. Li, B. T. Loo, and Y. Mao. Efficient querying and maintenance of network provenance at Internet-scale. In Proc. SIGMOD, pages 615-626, 2010. 10.1145\/1807167.1807234"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2535568.2448939","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T14:43:40Z","timestamp":1689345820000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2535568.2448939"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["10.14778\/2535568.2448939"],"URL":"https:\/\/doi.org\/10.14778\/2535568.2448939","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,12]]}}}