{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:29Z","timestamp":1759638929374},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439500"},{"type":"electronic","value":"9783662439517"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43951-7_16","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T04:37:49Z","timestamp":1402461469000},"page":"183-195","source":"Crossref","is-referenced-by-count":2,"title":["Computability in Anonymous Networks: Revocable vs. Irrecovable Outputs"],"prefix":"10.1007","author":[{"given":"Yuval","family":"Emek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jochen","family":"Seidel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roger","family":"Wattenhofer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Abrahamson, K., Adler, A., Higham, L., Kirkpatrick, D.: Probabilistic solitude verification on a ring. In: PODC (1986)","DOI":"10.1145\/10590.10604"},{"issue":"4","key":"16_CR2","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. Journal of Algorithms\u00a07(4), 567\u2013583 (1986)","journal-title":"Journal of Algorithms"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors (extended abstract). In: Theory of Computing (1980)","DOI":"10.1145\/800141.804655"},{"key":"16_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/11502593_8","volume-title":"Distributed Computing in Sensor Systems","author":"D. Angluin","year":"2005","unstructured":"Angluin, D., Aspnes, J., Chan, M., Fischer, M.J., Jiang, H., Peralta, R.: Stably computable properties of network graphs. In: Prasanna, V.K., Iyengar, S.S., Spirakis, P.G., Welsh, M. (eds.) DCOSS 2005. LNCS, vol.\u00a03560, pp. 63\u201374. Springer, Heidelberg (2005)"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. In: PODC (2004)","DOI":"10.1145\/1011767.1011810"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D.: Stably computable predicates are semilinear. In: PODC (2006)","DOI":"10.1145\/1146381.1146425"},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s00446-007-0040-2","volume":"20","author":"D. Angluin","year":"2007","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D., Ruppert, E.: The computational power of population protocols. Distributed Computing\u00a020, 279\u2013304 (2007)","journal-title":"Distributed Computing"},{"key":"16_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/11776178_3","volume-title":"Distributed Computing in Sensor Systems","author":"D. Angluin","year":"2006","unstructured":"Angluin, D., Fischer, M.J., Jiang, H.: Stabilizing consensus in mobile networks. In: Gibbons, P.B., Abdelzaher, T., Aspnes, J., Rao, R. (eds.) DCOSS 2006. LNCS, vol.\u00a04026, pp. 37\u201350. Springer, Heidelberg (2006)"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Ruppert, E.: An introduction to population protocols. In: Garbinato, B., Miranda, H., Rodrigues, L. (eds.) MiNEMA (2009)","DOI":"10.1007\/978-3-540-89707-1_5"},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Boldi, P., Vigna, S.: Computing anonymously with arbitrary knowledge. In: PODC (1999)","DOI":"10.1145\/301308.301355"},{"key":"16_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/3-540-45414-4_3","volume-title":"Distributed Computing","author":"P. Boldi","year":"2001","unstructured":"Boldi, P., Vigna, S.: An effective characterization of computability in anonymous networks. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol.\u00a02180, pp. 33\u201347. Springer, Heidelberg (2001)"},{"issue":"3","key":"16_CR12","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s004460100062","volume":"15","author":"P. Boldi","year":"2002","unstructured":"Boldi, P., Vigna, S.: Universal dynamic synchronous self-stabilization. Distributed Computing\u00a015(3), 137\u2013153 (2002)","journal-title":"Distributed Computing"},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/11864219_8","volume-title":"Distributed Computing","author":"J. Chalopin","year":"2006","unstructured":"Chalopin, J., Das, S., Santoro, N.: Groupings and pairings in anonymous networks. In: Dolev, S. (ed.) DISC 2006. LNCS, vol.\u00a04167, pp. 105\u2013119. Springer, Heidelberg (2006)"},{"key":"16_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-540-87779-0_4","volume-title":"Distributed Computing","author":"J. Chalopin","year":"2008","unstructured":"Chalopin, J., Godard, E., M\u00e9tivier, Y.: Local terminations and distributed computability in anonymous networks. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol.\u00a05218, pp. 47\u201362. Springer, Heidelberg (2008)"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Dolev, S.: Self-Stabilization (2000)","DOI":"10.7551\/mitpress\/6156.001.0001"},{"key":"16_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BFb0022445","volume-title":"Distributed Algorithms","author":"S. Dolev","year":"1992","unstructured":"Dolev, S., Israeli, A., Moran, S.: Uniform dynamic self-stabilizing leader election. In: Toueg, S., Spirakis, P.G., Kirousis, L. (eds.) WDAG 1991. LNCS, vol.\u00a0579, pp. 167\u2013180. Springer, Heidelberg (1992)"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Emek, Y., Wattenhofer, R.: Stone age distributed computing. In: PODC (2013)","DOI":"10.1145\/2484239.2484244"},{"issue":"2","key":"16_CR18","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/j.jpdc.2003.11.007","volume":"64","author":"P. Flocchini","year":"2004","unstructured":"Flocchini, P., Kranakis, E., Krizanc, D., Luccio, F.L., Santoro, N.: Sorting and election in anonymous asynchronous rings. J. Parallel Distrib. Comput.\u00a064(2), 254\u2013265 (2004)","journal-title":"J. Parallel Distrib. Comput."},{"key":"16_CR19","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Local distributed decision. In: FOCS (October 2011)","DOI":"10.1109\/FOCS.2011.17"},{"key":"16_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/978-3-642-35476-2_16","volume-title":"Principles of Distributed Systems","author":"P. Fraigniaud","year":"2012","unstructured":"Fraigniaud, P., Halld\u00f3rsson, M.M., Korman, A.: On the impact of identifiers on local decision. In: Baldoni, R., Flocchini, P., Binoy, R. (eds.) OPODIS 2012. LNCS, vol.\u00a07702, pp. 224\u2013238. Springer, Heidelberg (2012)"},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Oracle size: A new measure of difficulty for communication tasks. In: PODC (2006)","DOI":"10.1145\/1146381.1146410"},{"key":"16_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-3-642-33651-5_26","volume-title":"Distributed Computing","author":"P. Fraigniaud","year":"2012","unstructured":"Fraigniaud, P., Korman, A., Parter, M., Peleg, D.: Randomized distributed decision. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol.\u00a07611, pp. 371\u2013385. Springer, Heidelberg (2012)"},{"key":"16_CR23","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Suomela, J.: Locally checkable proofs. In: PODC (2011)","DOI":"10.1145\/1993806.1993829"},{"key":"16_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/11561927_19","volume-title":"Distributed Computing","author":"R. Guerraoui","year":"2005","unstructured":"Guerraoui, R., Ruppert, E.: What can be implemented anonymously? In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol.\u00a03724, pp. 244\u2013259. Springer, Heidelberg (2005)"},{"key":"16_CR25","doi-asserted-by":"crossref","unstructured":"Itai, A., Rodeh, M.: Symmetry breaking in distributive networks. In: FOCS (1981)","DOI":"10.1109\/SFCS.1981.41"},{"key":"16_CR26","doi-asserted-by":"crossref","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. In: PODC (2005)","DOI":"10.1145\/1073814.1073817"},{"key":"16_CR27","doi-asserted-by":"crossref","unstructured":"Korman, A., Sereni, J.S., Viennot, L.: Toward more localized local algorithms: removing assumptions concerning global knowledge. In: PODC (2011)","DOI":"10.1145\/1993806.1993814"},{"issue":"1","key":"16_CR28","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM Journal on Computing\u00a021(1), 193\u2013201 (1992)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR29","doi-asserted-by":"crossref","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. In: Theory of Computing (1985)","DOI":"10.1145\/22145.22146"},{"key":"16_CR30","unstructured":"Lynch, N.A.: Distributed Algorithms (1996)"},{"key":"16_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1007\/11945529_27","volume-title":"Principles of Distributed Systems","author":"M. Mavronicolas","year":"2006","unstructured":"Mavronicolas, M., Michael, L., Spirakis, P.: Computing on a partially eponymous ring. In: Shvartsman, A. (ed.) OPODIS 2006. LNCS, vol.\u00a04305, pp. 380\u2013394. Springer, Heidelberg (2006)"},{"key":"16_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-3-319-03578-9_13","volume-title":"Structural Information and Communication Complexity","author":"Y. M\u00e9tivier","year":"2013","unstructured":"M\u00e9tivier, Y., Robson, J.M., Zemmari, A.: Analysis of fully distributed splitting and naming probabilistic procedures and applications. In: Moscibroda, T., Rescigno, A.A. (eds.) SIROCCO 2013. LNCS, vol.\u00a08179, pp. 153\u2013164. Springer, Heidelberg (2013)"},{"issue":"6","key":"16_CR33","doi-asserted-by":"publisher","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 Journal on Computing\u00a024(6), 1259\u20131277 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"16_CR34","doi-asserted-by":"crossref","unstructured":"Schieber, B., Snir, M.: Calling names on nameless networks. In: PODC (1989)","DOI":"10.1145\/72981.73004"},{"issue":"1","key":"16_CR35","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1109\/71.481599","volume":"7","author":"M. Yamashita","year":"1996","unstructured":"Yamashita, M., Kameda, T.: Computing on anonymous networks: Part i-characterizing the solvable cases. IEEE Trans. Parallel Distrib. Syst.\u00a07(1), 69\u201389 (1996)","journal-title":"IEEE Trans. Parallel Distrib. Syst."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43951-7_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T22:24:41Z","timestamp":1558909481000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43951-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439500","9783662439517"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43951-7_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}