{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:35:13Z","timestamp":1750307713373,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["(B)19300017"],"award-info":[{"award-number":["(B)19300017"]}],"id":[{"id":"10.13039\/501100001691","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":[[2009,1]]},"abstract":"<jats:p>\n            In this article, we quantify the amount of \u201cpractical\u201d information (i.e., views obtained from the neighbors, colors attributed to the nodes and links) to obtain \u201ctheoretical\u201d information (i.e., the local topology of the network up to distance\n            <jats:italic>k<\/jats:italic>\n            ) in anonymous networks. In more detail, we show that a coloring at distance 2\n            <jats:italic>k<\/jats:italic>\n            + 1 is necessary and sufficient to obtain the local topology at distance\n            <jats:italic>k<\/jats:italic>\n            that includes outgoing links. This bound drops to 2\n            <jats:italic>k<\/jats:italic>\n            when outgoing links are not needed. A second contribution of this article deals with color bootstrapping (from which local topology can be obtained using the aforementioned mechanisms). On the negative side, we show that (\n            <jats:italic>i<\/jats:italic>\n            ) with a distributed daemon, it is impossible to achieve deterministic color bootstrap, even if the whole network topology can be instantaneously obtained, and (\n            <jats:italic>ii<\/jats:italic>\n            ) with a central daemon, it is impossible to achieve distance\n            <jats:italic>m<\/jats:italic>\n            when instantaneous topology knowledge is limited to\n            <jats:italic>m<\/jats:italic>\n            \u2212 1. On the positive side, we show that (\n            <jats:italic>i<\/jats:italic>\n            ) under the\n            <jats:italic>k<\/jats:italic>\n            -central daemon, deterministic self-stabilizing bootstrap of colors up to distance\n            <jats:italic>k<\/jats:italic>\n            is possible provided that\n            <jats:italic>k<\/jats:italic>\n            -local topology can be instantaneously obtained, and (\n            <jats:italic>ii<\/jats:italic>\n            ) under the distributed daemon, probabilistic self-stabilizing bootstrap is possible for any range.\n          <\/jats:p>","DOI":"10.1145\/1462187.1462195","type":"journal-article","created":{"date-parts":[[2009,2,10]],"date-time":"2009-02-10T16:42:19Z","timestamp":1234284139000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["On bootstrapping topology knowledge in anonymous networks"],"prefix":"10.1145","volume":"4","author":[{"given":"Toshimitsu","family":"Masuzawa","sequence":"first","affiliation":[{"name":"Osaka University, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S\u00e9bastien","family":"Tixeuil","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Pierre et Marie Curie, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,2,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-007-0029-x"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/301308.301358"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004460100062"},{"key":"e_1_2_1_4_1","volume-title":"proceedings of the 8th International Symposium on Stebilization, Safety, and Security on Distributed Systems (SSS'06)","volume":"4280","author":"Danturi P.","unstructured":"Danturi , P. , Nesterenko , M. , and Tixeuil , S . 2006. Self-stabilizing philosophers with generic conflicts . In proceedings of the 8th International Symposium on Stebilization, Safety, and Security on Distributed Systems (SSS'06) , A. K. Datta and M. Gradinariu, Eds. Lecture Notes in Computer Science , vol. 4280 . Springer-Verlag, 214--230. Danturi, P., Nesterenko, M., and Tixeuil, S. 2006. Self-stabilizing philosophers with generic conflicts. In proceedings of the 8th International Symposium on Stebilization, Safety, and Security on Distributed Systems (SSS'06), A. K. Datta and M. Gradinariu, Eds. Lecture Notes in Computer Science, vol. 4280. Springer-Verlag, 214--230."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2001.1827"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Dolev S. 2000. Self-Stabilization. MIT Press.   Dolev S. 2000. Self-Stabilization. MIT Press.","DOI":"10.7551\/mitpress\/6156.001.0001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050180"},{"key":"e_1_2_1_8_1","article-title":"Superstabilizing protocols for dynamic distributed systems. Chicago","author":"Dolev S.","year":"1997","unstructured":"Dolev , S. and Herman , T. 1997 . Superstabilizing protocols for dynamic distributed systems. Chicago J. Theor. Comput. Sci. Dolev, S. and Herman, T. 1997. Superstabilizing protocols for dynamic distributed systems. Chicago J. Theor. Comput. Sci.","journal-title":"J. Theor. Comput. Sci."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008935"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.92911"},{"volume-title":"Proceedings of the International Conference on Principles of Distributed Systems (OPODIS'00)","author":"Gradinariu M.","key":"e_1_2_1_11_1","unstructured":"Gradinariu , M. and Tixeuil , S . 2000. Self-stabilizing vertex coloring of arbitrary graphs . In Proceedings of the International Conference on Principles of Distributed Systems (OPODIS'00) , 55--70. Gradinariu, M. and Tixeuil, S. 2000. Self-stabilizing vertex coloring of arbitrary graphs. In Proceedings of the International Conference on Principles of Distributed Systems (OPODIS'00), 55--70."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 1st Workshop on Algorithmic Aspects of Wireless Sensor Networks (AlgoSensors'04)","volume":"3121","author":"Herman T.","unstructured":"Herman , T. and Tixeuil , S . 2004. A distributed TDMA slot assignment algorithm for wireless sensor networks . In Proceedings of the 1st Workshop on Algorithmic Aspects of Wireless Sensor Networks (AlgoSensors'04) . Lecture Notes in Computer Science , vol. 3121 , Springer-Verlag, 45--58. Herman, T. and Tixeuil, S. 2004. A distributed TDMA slot assignment algorithm for wireless sensor networks. In Proceedings of the 1st Workshop on Algorithmic Aspects of Wireless Sensor Networks (AlgoSensors'04). Lecture Notes in Computer Science, vol. 3121, Springer-Verlag, 45--58."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2002.1134340"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 2nd Workshop on Self-Stabilizing Systems, 1.1--1.15","author":"Masuzawa T.","year":"1995","unstructured":"Masuzawa , T. 1995 . A fault-tolerant and self-stabilizing protocol for the topology problem . In Proceedings of the 2nd Workshop on Self-Stabilizing Systems, 1.1--1.15 . Masuzawa, T. 1995. A fault-tolerant and self-stabilizing protocol for the topology problem. In Proceedings of the 2nd Workshop on Self-Stabilizing Systems, 1.1--1.15."},{"volume-title":"Proceedings of the International Conference on Parallel and Distributed Systems (ICPADS'06)","author":"Mitton N.","key":"e_1_2_1_15_1","unstructured":"Mitton , N. , Fleury , E. , Gu\u00e9rin-Lassous , I. , S\u00e9ricola , B. , and Tixeuil , S . 2006. On fast randomized colorings in sensor networks . In Proceedings of the International Conference on Parallel and Distributed Systems (ICPADS'06) . IEEE Press, 31--38. Mitton, N., Fleury, E., Gu\u00e9rin-Lassous, I., S\u00e9ricola, B., and Tixeuil, S. 2006. On fast randomized colorings in sensor networks. In Proceedings of the International Conference on Parallel and Distributed Systems (ICPADS'06). IEEE Press, 31--38."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCSW.2005.122"},{"key":"e_1_2_1_17_1","volume-title":"OSPF: Anatomy of an Internet Routing Protocol","author":"Moy J. T.","year":"1998","unstructured":"Moy , J. T. 1998 . OSPF: Anatomy of an Internet Routing Protocol . Addison-Wesley Longman Publishing Co., Inc. , Boston, MA . Moy, J. T. 1998. OSPF: Anatomy of an Internet Routing Protocol. Addison-Wesley Longman Publishing Co., Inc., Boston, MA."},{"volume-title":"Interconnexion Networks","author":"Perlman R.","key":"e_1_2_1_18_1","unstructured":"Perlman , R. 2000. Interconnexion Networks . Addison-Wesley . Perlman, R. 2000. Interconnexion Networks. Addison-Wesley."},{"key":"e_1_2_1_19_1","first-page":"2029","article-title":"Structure of initial conditions for distributed algorithms. IEICE","volume":"12","author":"Sakamoto N.","year":"2000","unstructured":"Sakamoto , N. 2000 . Structure of initial conditions for distributed algorithms. IEICE Trans. Inform. Syst. E83-D , 12 , 2029 -- 2038 . Sakamoto, N. 2000. Structure of initial conditions for distributed algorithms. IEICE Trans. Inform. Syst. E83-D, 12, 2029--2038.","journal-title":"Trans. Inform. Syst. E83-D"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.24597"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.798313"}],"container-title":["ACM Transactions on Autonomous and Adaptive Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462187.1462195","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1462187.1462195","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:15Z","timestamp":1750253415000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462187.1462195"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1145\/1462187.1462195"],"URL":"https:\/\/doi.org\/10.1145\/1462187.1462195","relation":{},"ISSN":["1556-4665","1556-4703"],"issn-type":[{"type":"print","value":"1556-4665"},{"type":"electronic","value":"1556-4703"}],"subject":[],"published":{"date-parts":[[2009,1]]},"assertion":[{"value":"2007-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-02-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}