{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:29Z","timestamp":1759639049983},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319720494"},{"type":"electronic","value":"9783319720500"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-72050-0_16","type":"book-chapter","created":{"date-parts":[[2017,12,29]],"date-time":"2017-12-29T16:57:13Z","timestamp":1514566633000},"page":"263-282","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["How Long It Takes for an Ordinary Node with\u00a0an Ordinary ID to Output?"],"prefix":"10.1007","author":[{"given":"Laurent","family":"Feuilloley","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,30]]},"reference":[{"issue":"4","key":"16_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":"16_CR2","doi-asserted-by":"crossref","DOI":"10.1002\/0471478210","volume-title":"Distributed Computing: Fundamentals, Simulations, and Advanced Topics","author":"H Attiya","year":"2004","unstructured":"Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations, and Advanced Topics. Wiley, Hoboken (2004)"},{"issue":"5\u20136","key":"16_CR3","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s00446-009-0088-2","volume":"22","author":"L Barenboim","year":"2010","unstructured":"Barenboim, L., Elkin, M.: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. Distrib. Comput. 22(5\u20136), 363\u2013379 (2010). \nhttps:\/\/doi.org\/10.1007\/s00446-009-0088-2","journal-title":"Distrib. Comput."},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Brandt, S., Fischer, O., Hirvonen, J., Keller, B., Lempi\u00e4inen, T., Rybicki, J., Suomela, J., Uitto, J.: A lower bound for the distributed lov\u00e1sz local lemma. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18\u201321, 2016, pp. 479\u2013488 (2016). \nhttps:\/\/doi.org\/10.1145\/2897518.2897570","DOI":"10.1145\/2897518.2897570"},{"key":"16_CR5","unstructured":"Brandt, S., Hirvonen, J., Korhonen, J.H., Lempi\u00e4inen, T., \u00d6sterg\u00e5rd, P.R.J., Purcell, C., Rybicki, J., Suomela, J., Uznanski, P.: LCL problems on grids. CoRR, abs\/1702.05456 (2017). \narXiv:1702.05456"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Chang, Y.J., Kopelowitz, T., Pettie, S.: An exponential separation between randomized and deterministic complexity in the local model. In: IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9\u201311 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pp. 615\u2013624 (2016). \nhttps:\/\/doi.org\/10.1109\/FOCS.2016.72","DOI":"10.1109\/FOCS.2016.72"},{"issue":"1","key":"16_CR7","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R Cole","year":"1986","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control 70(1), 32\u201353 (1986). \nhttps:\/\/doi.org\/10.1016\/S0019-9958(86)80023-7","journal-title":"Inf. Control"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Feuilloley, L.: Brief announcement: average complexity for the LOCAL model. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebasti\u00e1n, Spain, July 21\u201323, 2015, pp. 335\u2013337 (2015). \nhttps:\/\/doi.org\/10.1145\/2767386.2767446","DOI":"10.1145\/2767386.2767446"},{"key":"16_CR9","unstructured":"Feuilloley, L., Fraigniaud, P.: Survey of distributed decision. Bull. EATCS 119 (2016). \nEATCS: The Distributed Computing Column by Stefan Schmid"},{"issue":"5","key":"16_CR10","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). \nhttps:\/\/doi.org\/10.1145\/2499228","journal-title":"J. ACM"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Gamarnik, D., Sudan, M.: Limits of local algorithms over sparse random graphs. In: Proceedings of Innovations in Theoretical Computer Science, ITCS\u201914, Princeton, NJ, USA, January 12\u201314, 2014, pp. 369\u2013376 (2014). \nhttps:\/\/doi.org\/10.1145\/2554797.2554831","DOI":"10.1145\/2554797.2554831"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.: An improved distributed algorithm for maximal independent set. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312, 2016, pp. 270\u2013277 (2016). \nhttps:\/\/doi.org\/10.1137\/1.9781611974331.ch20","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-3-642-16367-8_7","volume-title":"Property Testing - Current Research and Surveys","author":"O Goldreich","year":"2010","unstructured":"Goldreich, O.: Introduction to testing graph properties. In: Goldreich, O. (ed.) Property Testing - Current Research and Surveys. LNCS, vol. 6390, pp. 105\u2013141. Springer, Heidelberg (2010). \nhttps:\/\/doi.org\/10.1007\/978-3-642-16367-8_7"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Harris, D.G., Schneider, J., Su, H.H.: Distributed \n            $$(\\Delta +1)$$\n          -coloring in sublogarithmic rounds. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18\u201321, 2016, pp. 465\u2013478 (2016). \nhttps:\/\/doi.org\/10.1145\/2897518.2897533","DOI":"10.1145\/2897518.2897533"},{"issue":"5\u20136","key":"16_CR15","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s00446-012-0174-8","volume":"26","author":"A Korman","year":"2013","unstructured":"Korman, A., Sereni, J.-S., Viennot, L.: Toward more localized local algorithms: removing assumptions concerning global knowledge. Distrib. Comput. 26(5\u20136), 289\u2013308 (2013). \nhttps:\/\/doi.org\/10.1007\/s00446-012-0174-8","journal-title":"Distrib. Comput."},{"issue":"1","key":"16_CR16","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"16_CR17","doi-asserted-by":"publisher","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). \nhttps:\/\/doi.org\/10.1137\/0215074","journal-title":"SIAM J. Comput."},{"key":"16_CR18","volume-title":"Distributed Algorithms","author":"NA Lynch","year":"1996","unstructured":"Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann, Burlington (1996)"},{"key":"16_CR19","unstructured":"Musto, T.: Knowledge of degree bounds in local algorithms. Master\u2019s thesis, University of Helsinki (2011)"},{"issue":"3","key":"16_CR20","doi-asserted-by":"publisher","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. Discrete Math. 4(3), 409\u2013412 (1991). \nhttps:\/\/doi.org\/10.1137\/0404036","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"16_CR21","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.J.: What can be computed locally? SIAM J. Comput. 24(6), 1259\u20131277 (1995). \nhttps:\/\/doi.org\/10.1137\/S0097539793254571","journal-title":"SIAM J. Comput."},{"key":"16_CR22","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 (2000)"},{"key":"16_CR23","unstructured":"Pettie, S., Ramachandran, V.: Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6\u20138, 2002, San Francisco, CA, USA., pp. 713\u2013722 (2002). \nacm:545381.545477"},{"key":"16_CR24","doi-asserted-by":"crossref","DOI":"10.1002\/0470072644","volume-title":"Design and Analysis of Distributed Algorithms","author":"N Santoro","year":"2006","unstructured":"Santoro, N.: Design and Analysis of Distributed Algorithms, vol. 56. Wiley, Hoboken (2006)"},{"key":"16_CR25","unstructured":"Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences. \nA000788"},{"key":"16_CR26","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Probabilistic computations: toward a unified measure of complexity (extended abstract). In: 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977, pp. 222\u2013227 (1977). \nhttps:\/\/doi.org\/10.1109\/SFCS.1977.24","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-72050-0_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,12,29]],"date-time":"2017-12-29T17:02:19Z","timestamp":1514566939000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-72050-0_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319720494","9783319720500"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-72050-0_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}