{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T20:37:14Z","timestamp":1770064634709,"version":"3.49.0"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2014,4,6]],"date-time":"2014-04-06T00:00:00Z","timestamp":1396742400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2014,12]]},"DOI":"10.1007\/s00446-014-0211-x","type":"journal-article","created":{"date-parts":[[2014,4,5]],"date-time":"2014-04-05T13:54:58Z","timestamp":1396706098000},"page":"419-434","source":"Crossref","is-referenced-by-count":16,"title":["Randomized distributed decision"],"prefix":"10.1007","volume":"27","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[]},{"given":"Mika","family":"G\u00f6\u00f6s","sequence":"additional","affiliation":[]},{"given":"Amos","family":"Korman","sequence":"additional","affiliation":[]},{"given":"Merav","family":"Parter","sequence":"additional","affiliation":[]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,4,6]]},"reference":[{"issue":"4","key":"211_CR1","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"key":"211_CR2","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Distributed $$(\\varDelta +1)$$ ( \u0394 + 1 ) -coloring in linear (in delta) time. In: Proceedings of the 41st ACM Symposium on Theory of Computing (STOC), pp. 111\u2013120 (2009)","DOI":"10.1145\/1536414.1536432"},{"issue":"5","key":"211_CR3","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1137\/11085178X","volume":"41","author":"A DasSarma","year":"2012","unstructured":"DasSarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41(5), 1235\u20131265 (2012)","journal-title":"SIAM J. Comput."},{"key":"211_CR4","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Suomela, J.: Locally checkable proofs. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pp. 159\u2013168 (2011)","DOI":"10.1145\/1993806.1993829"},{"issue":"5","key":"211_CR5","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1145\/2499228","volume":"60","author":"P Fraigniaud","year":"2013","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Local distributed decision. J. ACM 60(5), 35 (2013)","journal-title":"J. ACM"},{"key":"211_CR6","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Pelc, A.: Decidability classes for mobile agents computing. In: Proceedings of the 10th Latin American Symposium on Theoretical Informatics (LATIN) (2012)","DOI":"10.1007\/978-3-642-29344-3_31"},{"issue":"4","key":"211_CR7","doi-asserted-by":"crossref","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)","journal-title":"Distrib. Comput."},{"key":"211_CR8","unstructured":"Fraigniaud, P., Rajsbaum, S., Travers, C.: Universal Distributed Checkers and Orientation-Detection Tasks. Submitted (2012)"},{"key":"211_CR9","unstructured":"Kor, L., Korman, A., Peleg, D.: Tight bounds for distributed MST verification. Theory Comput. Syst. 53(2), 318\u2013340 (2013)"},{"issue":"4","key":"211_CR10","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/s00446-010-0095-3","volume":"22","author":"A Korman","year":"2010","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distrib. Comput. 22(4), 215\u2013233 (2010)","journal-title":"Distrib. Comput."},{"issue":"4","key":"211_CR11","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/s00446-007-0025-1","volume":"20","author":"A Korman","year":"2007","unstructured":"Korman, A., Kutten, S.: Distributed verification of minimum spanning trees. Distrib. Comput. 20(4), 253\u2013266 (2007)","journal-title":"Distrib. Comput."},{"key":"211_CR12","doi-asserted-by":"crossref","unstructured":"Kuhn, F.: Weak graph colorings: distributed algorithms and applications. In: Proceedings of the 21st Annual Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 138\u2013144 (2009)","DOI":"10.1145\/1583991.1584032"},{"issue":"4","key":"211_CR13","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"211_CR14","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1137\/0404036","volume":"4","author":"M Naor","year":"1991","unstructured":"Naor, M.: A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Discret. Math. 4(3), 409\u2013412 (1991)","journal-title":"SIAM J. Discret. Math."},{"issue":"6","key":"211_CR15","doi-asserted-by":"crossref","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput. 24(6), 1259\u20131277 (1995)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"211_CR16","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1006\/jagm.1996.0017","volume":"20","author":"A Panconesi","year":"1996","unstructured":"Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. J. Algorithms 20(2), 356\u2013374 (1996)","journal-title":"J. Algorithms"},{"key":"211_CR17","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia, PA (2000)"},{"key":"211_CR18","doi-asserted-by":"crossref","unstructured":"Schneider, J., Wattenhofer, R.: A new technique for distributed symmetry breaking. In: Proceedings of the 29th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pp. 257\u2013266 (2010)","DOI":"10.1145\/1835698.1835760"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-014-0211-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-014-0211-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-014-0211-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,9]],"date-time":"2019-08-09T08:28:21Z","timestamp":1565339301000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-014-0211-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,4,6]]},"references-count":18,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2014,12]]}},"alternative-id":["211"],"URL":"https:\/\/doi.org\/10.1007\/s00446-014-0211-x","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,4,6]]}}}