{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T11:36:29Z","timestamp":1770896189583,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T00:00:00Z","timestamp":1578528000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T00:00:00Z","timestamp":1578528000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Appl. and Comput. Topology"],"published-print":{"date-parts":[[2020,3]]},"DOI":"10.1007\/s41468-019-00047-6","type":"journal-article","created":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T14:02:59Z","timestamp":1578578579000},"page":"141-179","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["A lower bound on the number of opinions needed for fault-tolerant decentralized run-time monitoring"],"prefix":"10.1007","volume":"4","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Rajsbaum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Corentin","family":"Travers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,9]]},"reference":[{"issue":"4","key":"47_CR1","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1145\/153724.153741","volume":"40","author":"Y Afek","year":"1993","unstructured":"Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. J. ACM 40(4), 873\u2013890 (1993)","journal-title":"J. ACM"},{"key":"47_CR2","unstructured":"Arafat, O., Bauer, A., Leucker, M., Schallhart, C.: Runtime verification revisited. Tech. Rep. TUM-I0518, Technischen Universit\u00e4t M\u00fcnchen (2005)"},{"issue":"4","key":"47_CR3","doi-asserted-by":"publisher","first-page":"1286","DOI":"10.1137\/S0097539797330689","volume":"31","author":"H Attiya","year":"2002","unstructured":"Attiya, H., Rajsbaum, S.: The combinatorial structure of wait-free solvable tasks. SIAM J. Comput. 31(4), 1286\u20131313 (2002). https:\/\/doi.org\/10.1137\/S0097539797330689","journal-title":"SIAM J. Comput."},{"key":"47_CR4","doi-asserted-by":"publisher","DOI":"10.1002\/0471478210","volume-title":"Distributed Computing: Fundamentals, Simulations and Advanced Topics","author":"H Attiya","year":"2004","unstructured":"Attiya, H., Welch, J.L.: Distributed Computing: Fundamentals, Simulations and Advanced Topics. Wiley, Hoboken (2004)"},{"key":"47_CR5","doi-asserted-by":"publisher","unstructured":"Awerbuch, B., Varghese, G.: Distributed program checking: A paradigm for building self-stabilizing distributed protocols. In: 32nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 258\u2013267 (1991). https:\/\/doi.org\/10.1109\/SFCS.1991.185377","DOI":"10.1109\/SFCS.1991.185377"},{"key":"47_CR6","doi-asserted-by":"crossref","unstructured":"Bauer, A., Leucker, M., Schallhart, C.: Monitoring of real-time properties. In: 26th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTC), LNCS, vol. 4337, pp. 260\u2013272. Springer (2006)","DOI":"10.1007\/11944836_25"},{"issue":"3","key":"47_CR7","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1093\/logcom\/exn075","volume":"20","author":"A Bauer","year":"2010","unstructured":"Bauer, A., Leucker, M., Schallhart, C.: Comparing LTL semantics for runtime verification. J. Log. Comput. 20(3), 651\u2013674 (2010). https:\/\/doi.org\/10.1093\/logcom\/exn075","journal-title":"J. Log. Comput."},{"key":"47_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32759-9","volume-title":"FM 2012: Formal Methods","year":"2012","unstructured":"Bauer, A.K., Falcone, Y.: Decentralised LTL monitoring. In: 18th International Symposium Formal Methods (FM), LNCS, vol. 7436, pp. 85\u2013100. Springer (2012). https:\/\/doi.org\/10.1007\/978-3-642-32759-9"},{"key":"47_CR9","unstructured":"Berkovich, S., Bonakdarpour, B., Fischmeister, S.: GPU-based runtime verification. In: 27th IEEE International Symposium on Parallel and Distributed Processing (IPDPS), pp. 1025\u20131036 (2013). http:\/\/ieeexplore.ieee.org\/xpl\/mostRecentIssue.jsp?punumber=6569024"},{"key":"47_CR10","unstructured":"Bonakdarpour, B., Fraigniaud, P., Rajsbaum, S., Rosenblueth, D.A., Travers, C.: Decentralized asynchronous crash-resilient runtime verification. In: 27th International Conference on Concurrency Theory (CONCUR), pp. 16:1\u201316:15. LIPIcs 59, Schloss Dagstuhl (2016)"},{"key":"47_CR11","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/978-3-319-47169-3_27","volume-title":"Leveraging Applications of Formal Methods, Verification and Validation: Discussion, Dissemination, Applications","author":"Borzoo Bonakdarpour","year":"2016","unstructured":"Bonakdarpour, B., Fraigniaud, P., Rajsbaum, S., Travers, C.: Challenges in fault-tolerant distributed runtime verification. In: 7th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation (ISOLA), LNCS, vol. 9953, pp. 363\u2013370. Springer (2016). https:\/\/doi.org\/10.1007\/978-3-319-47169-3_27"},{"key":"47_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21437-0","volume-title":"FM 2011: Formal Methods","year":"2011","unstructured":"Bonakdarpour, B., Navabpour, S., Fischmeister, S.: Sampling-based runtime verification. In: 17th International Symposium on Formal Methods (FM), LNCS, vol. 6664, pp. 88\u2013102. Springer (2011). https:\/\/doi.org\/10.1007\/978-3-642-21437-0"},{"issue":"3","key":"47_CR13","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/BF00147939","volume":"22","author":"J Bracho","year":"1987","unstructured":"Bracho, J., Montejano, L.: The combinatorics of colored triangulations of manifolds. Geometriae Dedicata 22(3), 303\u2013328 (1987). https:\/\/doi.org\/10.1007\/BF00147939","journal-title":"Geometriae Dedicata"},{"key":"47_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19835-9","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","year":"2011","unstructured":"Burnim, J., Sen, K., Stergiou, C.: Sound and complete monitoring of sequential consistency for relaxed memory models. In: 17th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), LNCS, vol. 6605, pp. 11\u201325. Springer (2011). https:\/\/doi.org\/10.1007\/978-3-642-19835-9"},{"issue":"1","key":"47_CR15","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1145\/214451.214456","volume":"3","author":"KM Chandy","year":"1985","unstructured":"Chandy, K.M., Lamport, L.: Distributed snapshots: determining global states of distributed systems. ACM Trans. Comput. Syst. 3(1), 63\u201375 (1985). https:\/\/doi.org\/10.1145\/214451.214456","journal-title":"ACM Trans. Comput. Syst."},{"key":"47_CR16","unstructured":"Chauhan, H., Garg, V.K., Natarajan, A., Mittal, N.: A distributed abstraction algorithm for online predicate detection. In: 32nd IEEE Symposium on Reliable Distributed Systems (SRDS), pp. 101\u2013110 (2013). http:\/\/ieeexplore.ieee.org\/xpl\/mostRecentIssue.jsp?punumber=6656126"},{"key":"47_CR17","unstructured":"Cooper, R., Marzullo, K.: Consistent detection of global predicates. In: ACM Workshop on Parallel and Distributed Debugging, pp. 167\u2013174 (1991). http:\/\/dl.acm.org\/citation.cfm?id=122759"},{"issue":"3","key":"47_CR18","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s10009-011-0196-8","volume":"14","author":"Y Falcone","year":"2012","unstructured":"Falcone, Y., Fernandez, J., Mounier, L.: What can you verify and enforce at runtime? Int. J. Softw. Tools Technol. Transf. 14(3), 349\u2013382 (2012). https:\/\/doi.org\/10.1007\/s10009-011-0196-8","journal-title":"Int. J. Softw. Tools Technol. Transf."},{"issue":"2","key":"47_CR19","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1145\/3149.214121","volume":"32","author":"MJ Fischer","year":"1985","unstructured":"Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374\u2013382 (1985). https:\/\/doi.org\/10.1145\/3149.214121","journal-title":"J. ACM"},{"issue":"5","key":"47_CR20","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1145\/2499228","volume":"60","author":"P Fraigniaud","year":"2013","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Towards a complexity theory for local distributed computing. J. ACM 60(5), 35 (2013). https:\/\/doi.org\/10.1145\/2499228","journal-title":"J. ACM"},{"key":"47_CR21","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-319-14472-6_11","volume-title":"Lecture Notes in Computer Science","author":"Pierre Fraigniaud","year":"2014","unstructured":"Fraigniaud, P., Rajsbaum, S., Roy, M., Travers, C.: The opinion number of set-agreement. In: 18th International Conference Principles of Distributed Systems (OPODIS), LNCS, vol. 8878, pp. 155\u2013170. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-319-14472-6_11"},{"issue":"4","key":"47_CR22","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s00446-013-0188-x","volume":"26","author":"P Fraigniaud","year":"2013","unstructured":"Fraigniaud, P., Rajsbaum, S., Travers, C.: Locality and checkability in wait-free computing. Distrib. Comput. 26(4), 223\u2013242 (2013). https:\/\/doi.org\/10.1007\/s00446-013-0188-x","journal-title":"Distrib. Comput."},{"key":"47_CR23","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/978-3-662-49529-2_37","volume-title":"LATIN 2016: Theoretical Informatics","author":"Pierre Fraigniaud","year":"2016","unstructured":"Fraigniaud, P., Rajsbaum, S., Travers, C.: Minimizing the number of opinions for fault-tolerant distributed decision using well-quasi orderings. In: 12th Latin American Symposium on Theoretical Informatics (LATIN), LNCS, vol. 9644, pp. 497\u2013508. Springer (2016). https:\/\/doi.org\/10.1007\/978-3-662-49529-2_37"},{"key":"47_CR24","doi-asserted-by":"crossref","unstructured":"Genon, A., Massart, T., Meuter, C.: Monitoring distributed controllers: When an efficient LTL algorithm on sequences is needed to model-check traces. In: 14th International Symposium on Formal Methods (FM), LNCS, vol. 4085, pp. 557\u2013572. Springer (2006)","DOI":"10.1007\/11813040_37"},{"key":"47_CR25","doi-asserted-by":"crossref","unstructured":"Ha, J., Arnold, M., Blackburn, S.M., McKinley, K.S.: A concurrent dynamic analysis framework for multicore hardware. In: 24th ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), pp. 155\u2013174. ACM (2009)","DOI":"10.1145\/1640089.1640101"},{"key":"47_CR26","unstructured":"Henle, M.: A Combinatorial Introduction to Topology. Dover (1983). http:\/\/store.doverpublications.com\/0486679667.html#productdescription"},{"key":"47_CR27","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Kozlov, D., Rajsbaum, S.: Distributed Computing Through Combinatorial Topology. Morgan Kaufmann-Elsevier (2013). http:\/\/store.elsevier.com\/Distributed-Computing-Through-Combinatorial-Topology\/Maurice-Herlihy\/isbn-9780124045781\/","DOI":"10.1016\/B978-0-12-404578-1.00003-6"},{"key":"47_CR28","doi-asserted-by":"publisher","unstructured":"Herlihy, M., Rajsbaum, S., Tuttle, M.R.: Unifying synchronous and asynchronous message-passing models. In: 17th ACM symposium on Principles of distributed computing (PODC), pp. 133\u2013142 (1998). https:\/\/doi.org\/10.1145\/277697.277722","DOI":"10.1145\/277697.277722"},{"issue":"6","key":"47_CR29","doi-asserted-by":"publisher","first-page":"858","DOI":"10.1145\/331524.331529","volume":"46","author":"M Herlihy","year":"1999","unstructured":"Herlihy, M., Shavit, N.: The topological structure of asynchronous computability. J. ACM 46(6), 858\u2013923 (1999). https:\/\/doi.org\/10.1145\/331524.331529","journal-title":"J. ACM"},{"key":"47_CR30","volume-title":"The Art of Multiprocessor Programming","author":"M Herlihy","year":"2008","unstructured":"Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco (2008)"},{"issue":"3","key":"47_CR31","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1023\/A:1011254632723","volume":"19","author":"Orna Kupferman","year":"2001","unstructured":"Kupferman, O., Y. Vardi, M.: Model checking of safety properties. Form. Methods Syst. Des. 19(3), 291\u2013314 (2001). https:\/\/doi.org\/10.1023\/A:1011254632723","journal-title":"Formal Methods in System Design"},{"key":"47_CR32","volume-title":"Distributed Algorithms","author":"N Lynch","year":"1996","unstructured":"Lynch, N.: Distributed Algorithms. Elsevier, Hoboken (1996)"},{"key":"47_CR33","doi-asserted-by":"crossref","unstructured":"Mostafa, M., Bonakdarpour, B.: Decentralized runtime verification of LTL specifications in distributed systems. In: 29th IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 494\u2013503 (2015)","DOI":"10.1109\/IPDPS.2015.95"},{"key":"47_CR34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32027-9","volume-title":"Concurrent Programming\u2014Algorithms, Principles, and Foundations","author":"M Raynal","year":"2013","unstructured":"Raynal, M.: Concurrent Programming\u2014Algorithms, Principles, and Foundations. Springer, Berlin (2013)"},{"key":"47_CR35","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38123-2","volume-title":"Distributed Algorithms for Message-Passing Systems","author":"M Raynal","year":"2013","unstructured":"Raynal, M.: Distributed Algorithms for Message-Passing Systems. Springer, Berlin (2013)"},{"key":"47_CR36","unstructured":"Scheffel, T., Schmitz, M.: Three-valued asynchronous distributed runtime verification. In: 12th ACM\/IEEE International Conference on Formal Methods and Models for Codesign (MEMOCODE), pp. 52\u201361 (2014). http:\/\/ieeexplore.ieee.org\/xpl\/mostRecentIssue.jsp?punumber=6950639"},{"key":"47_CR37","unstructured":"Sen, K., Vardhan, A., Agha, G., Rosu, G.: Efficient decentralized monitoring of safety in distributed systems. In: 26th IEEE International Conference on Software Engineering (ICSE), pp. 418\u2013427 (2004). http:\/\/dl.acm.org\/citation.cfm?id=998675"},{"key":"47_CR38","unstructured":"Sen, K., Vardhan, A., Agha, G., Rosu, G.: Decentralized runtime analysis of multithreaded applications. In: 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS) (2006). http:\/\/ieeexplore.ieee.org\/xpl\/mostRecentIssue.jsp?punumber=10917"},{"key":"47_CR39","unstructured":"Zhu, H., Dwyer, M.B., Goddard, S.: Predictable runtime monitoring. In: 21st IEEE Euromicro Conference on Real-Time Systems, (ECRTS), pp. 173\u2013183 (2009). http:\/\/ieeexplore.ieee.org\/xpl\/mostRecentIssue.jsp?punumber=5161487"}],"container-title":["Journal of Applied and Computational Topology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-019-00047-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s41468-019-00047-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-019-00047-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,8]],"date-time":"2021-01-08T02:51:31Z","timestamp":1610074291000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s41468-019-00047-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,9]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["47"],"URL":"https:\/\/doi.org\/10.1007\/s41468-019-00047-6","relation":{},"ISSN":["2367-1726","2367-1734"],"issn-type":[{"value":"2367-1726","type":"print"},{"value":"2367-1734","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,9]]},"assertion":[{"value":"22 November 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}