{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:28:16Z","timestamp":1750307296440,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,6,1]],"date-time":"2011-06-01T00:00:00Z","timestamp":1306886400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0428738"],"award-info":[{"award-number":["CNS-0428738"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Auton. Adapt. Syst."],"published-print":{"date-parts":[[2011,6]]},"abstract":"<jats:p>\n            In this article, we formalize\n            <jats:italic>locally distributed predicates<\/jats:italic>\n            , a concept previously introduced to address specific challenges associated with modular robotics and distributed debugging. A locally distributed predicate (LDP) is a novel construction for representing and detecting distributed properties in sparse-topology systems. Our previous work on LDPs presented empirical validation; here we show a formal model for two variants of the LDP algorithm, LDP-Basic and LDP-Snapshot, and establish performance bounds for these variants. We prove that LDP-Basic can detect strong stable predicates, that LDP-Snapshot can detect all stable predicates, and discuss their applicability to various distributed programming domains and to spatial computing in general. LDP detection in bounded-degree networks is shown to be scale-free, making the approach particularly attractive for specific topologies, even though LDPs are less efficient than snapshot algorithms in general distributed systems.\n          <\/jats:p>","DOI":"10.1145\/1968513.1968516","type":"journal-article","created":{"date-parts":[[2011,6,28]],"date-time":"2011-06-28T17:31:10Z","timestamp":1309282270000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Detecting Locally Distributed Predicates"],"prefix":"10.1145","volume":"6","author":[{"given":"Michael","family":"De Rosa","sequence":"first","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seth Copen","family":"Goldstein","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Lee","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jason","family":"Campbell","sequence":"additional","affiliation":[{"name":"Intel Labs, Pittsburgh"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Padmanabhan S.","family":"Pillai","sequence":"additional","affiliation":[{"name":"Intel Labs, Pittsburgh"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,6]]},"reference":[{"volume-title":"Proceedings of the IEEE International Conference on Robots and Systems (IROS\u201907)","author":"Ashley-Rollman M.","key":"e_1_2_1_1_1","unstructured":"Ashley-Rollman , M. , De Rosa , M. , Srinivasa , S. , Pillai , P. , Goldstein , S. , and Campbell , J . 2007. Declarative programming for modular robots . In Proceedings of the IEEE International Conference on Robots and Systems (IROS\u201907) . IEEE, Los Alamitos, CA. Ashley-Rollman, M., De Rosa, M., Srinivasa, S., Pillai, P., Goldstein, S., and Campbell, J. 2007. Declarative programming for modular robots. In Proceedings of the IEEE International Conference on Robots and Systems (IROS\u201907). IEEE, Los Alamitos, CA."},{"key":"e_1_2_1_2_1","unstructured":"Babao \u00d6. Marzullo K. and Marzullo K. 1993. Consistent global states of distributed systems: Fundamental concepts and mechanisms. In Distributed Systems Addison-Wesley Reading MA 55--96. Babao \u00d6. Marzullo K. and Marzullo K. 1993. Consistent global states of distributed systems: Fundamental concepts and mechanisms. In Distributed Systems Addison-Wesley Reading MA 55--96."},{"key":"e_1_2_1_3_1","unstructured":"Baldoni R. and Raynal M. 2002. Fundamentals of distributed computing: A practical tour of vector clock systems. In Distributed Systems Online. Baldoni R. and Raynal M. 2002. Fundamentals of distributed computing: A practical tour of vector clock systems. In Distributed Systems Online ."},{"volume-title":"Proceedings of the International Conference on Robotics and Automation (ICRA). IEEE","author":"Butler Z.","key":"e_1_2_1_4_1","unstructured":"Butler , Z. , Kotay , K. , Rus , D. , and Tomita , K . 2002. Generic decentralized control for a class of self-reconfigurable robots . In Proceedings of the International Conference on Robotics and Automation (ICRA). IEEE , Los Alamitos, CA, 809--816. Butler, Z., Kotay, K., Rus, D., and Tomita, K. 2002. Generic decentralized control for a class of self-reconfigurable robots. In Proceedings of the International Conference on Robotics and Automation (ICRA). IEEE, Los Alamitos, CA, 809--816."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/214451.214456"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/127695.122774"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/93385.93398"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364907084986"},{"volume-title":"Proceedings of the International Conference on Intelligent Robots and Systems (IROS). IEEE","author":"De Rosa M.","key":"e_1_2_1_9_1","unstructured":"De Rosa , M. , Goldstein , S. C. , Lee , P. , Pillai , P. , and Campbell , J . 2009. A tale of two planners: Modular robotic planning with LDP . In Proceedings of the International Conference on Intelligent Robots and Systems (IROS). IEEE , Los Alamitos, CA. De Rosa, M., Goldstein, S. C., Lee, P., Pillai, P., and Campbell, J. 2009. A tale of two planners: Modular robotic planning with LDP. In Proceedings of the International Conference on Intelligent Robots and Systems (IROS). IEEE, Los Alamitos, CA."},{"volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation (ICRA\u201908)","author":"De Rosa M.","key":"e_1_2_1_10_1","unstructured":"De Rosa , M. , Goldstein , S. C. , Lee , P. , Pillai , P. S. , and Campbell , J . 2008. Programming modular robots with locally distributed predicates . In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA\u201908) . IEEE, Los Alamitos, CA. De Rosa, M., Goldstein, S. C., Lee, P., Pillai, P. S., and Campbell, J. 2008. Programming modular robots with locally distributed predicates. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA\u201908). IEEE, Los Alamitos, CA."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.84874"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/345910.345953"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2007.1000"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1088\/0967-1846\/2\/4\/005"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90125-6"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_1_17_1","volume-title":"Tinyos: An operating system for sensor networks. In Ambient Intelligence","author":"Levis P.","year":"2004","unstructured":"Levis , P. , Madden , S. , Polastre , J. , Szewczyk , R. , Whitehouse , K. , Woo , A. , Gay , D. , Hill , J. , Welsh , M. , Brewer , E. , and Culler , D . 2004 . Tinyos: An operating system for sensor networks. In Ambient Intelligence , Springer Verlag . Levis, P., Madden, S., Polastre, J., Szewczyk, R., Whitehouse, K., Woo, A., Gay, D., Hill, J., Welsh, M., Brewer, E., and Culler, D. 2004. Tinyos: An operating system for sensor networks. In Ambient Intelligence, Springer Verlag."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280830"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/319702.319717"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/646664.700610"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026566201350"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280831"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/151646.151647"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.1989.37930"}],"container-title":["ACM Transactions on Autonomous and Adaptive Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1968513.1968516","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1968513.1968516","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:48Z","timestamp":1750244388000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1968513.1968516"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["10.1145\/1968513.1968516"],"URL":"https:\/\/doi.org\/10.1145\/1968513.1968516","relation":{},"ISSN":["1556-4665","1556-4703"],"issn-type":[{"type":"print","value":"1556-4665"},{"type":"electronic","value":"1556-4703"}],"subject":[],"published":{"date-parts":[[2011,6]]},"assertion":[{"value":"2009-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}