{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T19:23:42Z","timestamp":1773948222144,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,10,23]],"date-time":"2015-10-23T00:00:00Z","timestamp":1445558400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2016,6]]},"DOI":"10.1007\/s00446-015-0257-4","type":"journal-article","created":{"date-parts":[[2015,10,23]],"date-time":"2015-10-23T15:02:58Z","timestamp":1445612578000},"page":"207-237","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":41,"title":["Simple and efficient local codes for distributed stable network construction"],"prefix":"10.1007","volume":"29","author":[{"given":"Othon","family":"Michail","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,10,23]]},"reference":[{"key":"257_CR1","doi-asserted-by":"crossref","unstructured":"Angluin, D., Aspnes, J., Chan, M., Fischer, M.J., Jiang, H., Peralta, R.: Stably computable properties of network graphs. In: Proceedings of the 1st IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS), volume 3560 of LNCS, pp. 63\u201374. Springer, June (2005)","DOI":"10.1007\/11502593_8"},{"key":"257_CR2","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. Distrib. Comput. 18(4), 235\u2013253 (2006)","DOI":"10.1007\/s00446-005-0138-3"},{"issue":"4","key":"257_CR3","doi-asserted-by":"crossref","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. Distrib. Comput. 20(4), 279\u2013304 (2007)","journal-title":"Distrib. Comput."},{"issue":"11","key":"257_CR4","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1126\/science.7973651","volume":"266","author":"LM Adleman","year":"1994","unstructured":"Adleman, L.M.: Molecular computation of solutions to combinatorial problems. Science 266(11), 1021\u20131024 (1994)","journal-title":"Science"},{"key":"257_CR5","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors. In: Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC), pp. 82\u201393. ACM (1980)","DOI":"10.1145\/800141.804655"},{"key":"257_CR6","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/978-3-540-89707-1_5","volume-title":"Middleware for Network Eccentric and Mobile Applications","author":"J Aspnes","year":"2009","unstructured":"Aspnes, J., Ruppert, E.: An introduction to population protocols. In: Garbinato, B., Miranda, H., Rodrigues, L. (eds.) Middleware for Network Eccentric and Mobile Applications, pp. 97\u2013120. Springer, Berlin (2009)"},{"issue":"5439","key":"257_CR7","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A-L Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509\u2013512 (1999)","journal-title":"Science"},{"key":"257_CR8","doi-asserted-by":"crossref","unstructured":"Beauquier, J., Burman, J., Clement, J., Kutten, S.: On utilizing speed in networks of mobile agents. In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pp. 305\u2013314. ACM (2010)","DOI":"10.1145\/1835698.1835775"},{"issue":"2","key":"257_CR9","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1145\/2465769.2465771","volume":"1","author":"L Blume","year":"2013","unstructured":"Blume, L., Easley, D., Kleinberg, J., Kleinberg, R., Tardos, \u00c9.: Network formation in the presence of contagious risk. ACM Trans. Econ. Comput. 1(2), 6 (2013)","journal-title":"ACM Trans. Econ. Comput."},{"key":"257_CR10","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random Graphs, vol. 73. Cambridge university press, Cambridge (2001)"},{"issue":"5","key":"257_CR11","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1038\/nphys1636","volume":"6","author":"A Bandyopadhyay","year":"2010","unstructured":"Bandyopadhyay, A., Pati, R., Sahu, S., Peper, F., Fujita, D.: Massively parallel computing on an organic molecular layer. Nat. Phys. 6(5), 369\u2013375 (2010)","journal-title":"Nat. Phys."},{"key":"257_CR12","doi-asserted-by":"crossref","unstructured":"Chen, H.-L., Cummings, R., Doty, D., Soloveichik, D.: Speed faults in computation by chemical reaction networks. In: Proceedings of the 28th International Symposium on Distributed Computing (DISC), volume 8784 of LNCS, pp. 16\u201330. Springer (2014). Also to appear in Distributed Computing","DOI":"10.1007\/978-3-662-45174-8_2"},{"issue":"46","key":"257_CR13","doi-asserted-by":"crossref","first-page":"6469","DOI":"10.1016\/j.tcs.2011.07.001","volume":"412","author":"I Chatzigiannakis","year":"2011","unstructured":"Chatzigiannakis, I., Michail, O., Nikolaou, S., Pavlogiannis, A., Spirakis, P.G.: Passively mobile communicating machines that use restricted space. Theor. Comput. Sci. 412(46), 6469\u20136483 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"257_CR14","doi-asserted-by":"crossref","unstructured":"Derakhshandeh, Z., Dolev, S., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Brief announcement: amoebot\u2014a new model for programmable matter. In: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 220\u2013222. ACM (2014)","DOI":"10.1145\/2612669.2612712"},{"issue":"2","key":"257_CR15","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/s00446-014-0220-9","volume":"28","author":"S Das","year":"2015","unstructured":"Das, S., Flocchini, P., Santoro, N., Yamashita, M.: Forming sequences of geometric patterns with oblivious mobile robots. Distrib. Comput. 28(2), 131\u2013145 (2015)","journal-title":"Distrib. Comput."},{"key":"257_CR16","unstructured":"Dolev, S., Gmyr, R., Richa, A.W., Scheideler, C.: Ameba-inspired self-organizing particle systems. arXiv preprint. arXiv:1307.4259 (2013)"},{"key":"257_CR17","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1145\/2380656.2380675","volume":"55","author":"D Doty","year":"2012","unstructured":"Doty, D.: Theory of algorithmic self-assembly. Commun. ACM 55, 78\u201388 (2012)","journal-title":"Commun. ACM"},{"key":"257_CR18","doi-asserted-by":"crossref","unstructured":"Doty, D.: Timing in chemical reaction networks. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 772\u2013784 (2014)","DOI":"10.1137\/1.9781611973402.57"},{"key":"257_CR19","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On random graphs. Publ. Math. Debr. 6, 290\u2013297 (1959)","journal-title":"Publ. Math. Debr."},{"key":"257_CR20","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 1, 3rd edn. Revised Printing. Wiley, New York (1968)"},{"key":"257_CR21","doi-asserted-by":"crossref","unstructured":"Guerraoui, R., Ruppert, E.: Names trump malice: tiny mobile agents can tolerate byzantine failures. In: 36th International Colloquium on Automata, Languages and Programming (ICALP), volume 5556 of LNCS, pp. 484\u2013495. Springer (2009)","DOI":"10.1007\/978-3-642-02930-1_40"},{"key":"257_CR22","doi-asserted-by":"crossref","unstructured":"Jackson, M.O.: A survey of network formation models: stability and efficiency. In: Demange, G., Wooders, M. (eds.) Group Formation in Economics: Networks, Clubs and Coalitions, pp. 11\u201357 (2005)","DOI":"10.1017\/CBO9780511614385.002"},{"key":"257_CR23","unstructured":"Lynch, N.A.: Distributed Algorithms, 1st edn. Morgan Kaufmann Publishers, Inc., San Francisco, California (1996)"},{"issue":"22","key":"257_CR24","doi-asserted-by":"crossref","first-page":"2434","DOI":"10.1016\/j.tcs.2011.02.003","volume":"412","author":"O Michail","year":"2011","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Mediated population protocols. Theor. Comput. Sci. 412(22), 2434\u20132450 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"257_CR25","volume-title":"Synthesis Lectures on Distributed Computing Theory","author":"O Michail","year":"2011","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: New models for population protocols. In: Lynch, N.A. (ed.) Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool, San Rafael (2011)"},{"key":"257_CR26","doi-asserted-by":"crossref","unstructured":"Michail, O.: Terminating distributed construction of shapes and patterns in a fair solution of automata. In: Proceedings of the 34th ACM Symposium on Principles of Distributed Computing (PODC), pp. 37\u201346. ACM (2015)","DOI":"10.1145\/2767386.2767402"},{"key":"257_CR27","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"257_CR28","doi-asserted-by":"crossref","unstructured":"Michail, O., Spirakis, P.G.: Simple and efficient local codes for distributed stable network construction. In: Proceedings of the 33rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 76\u201385. ACM (2014)","DOI":"10.1145\/2611462.2611466"},{"issue":"6198","key":"257_CR29","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1126\/science.1254295","volume":"345","author":"M Rubenstein","year":"2014","unstructured":"Rubenstein, M., Cornejo, A., Nagpal, R.: Programmable self-assembly in a thousand-robot swarm. Science 345(6198), 795\u2013799 (2014)","journal-title":"Science"},{"key":"257_CR30","doi-asserted-by":"crossref","unstructured":"Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), pp. 459\u2013468 (2000)","DOI":"10.1145\/335305.335358"},{"key":"257_CR31","volume-title":"Cellular Automata: A Discrete View of the World","author":"JL Schiff","year":"2011","unstructured":"Schiff, J.L.: Cellular Automata: A Discrete View of the World, vol. 45. Wiley-Interscience, New York (2011)"},{"key":"257_CR32","doi-asserted-by":"crossref","unstructured":"Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347\u20131363 (1999)","DOI":"10.1137\/S009753979628292X"},{"issue":"7422","key":"257_CR33","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1038\/nature11549","volume":"491","author":"N Vaidya","year":"2012","unstructured":"Vaidya, N., Manapat, M.L., Chen, I.A., Xulvi-Brunet, R., Hayden, E.J., Lehman, N.: Spontaneous network formation among cooperative RNA replicators. Nature 491(7422), 72\u201377 (2012)","journal-title":"Nature"},{"key":"257_CR34","doi-asserted-by":"crossref","unstructured":"Woods, D., Chen, H.-L., Goodfriend, S., Dabby, N., Winfree, E., Yin, P.: Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, pp. 353\u2013354. ACM (2013)","DOI":"10.1145\/2422436.2422476"},{"key":"257_CR35","unstructured":"Winfree, E.: Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology, June (1998)"},{"issue":"10","key":"257_CR36","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1038\/nbt874","volume":"21","author":"S Zhang","year":"2003","unstructured":"Zhang, S.: Fabrication of novel biomaterials through molecular self-assembly. Nat. Biotechnol. 21(10), 1171\u20131178 (2003)","journal-title":"Nat. Biotechnol."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-015-0257-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-015-0257-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-015-0257-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T03:30:34Z","timestamp":1748662234000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-015-0257-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,23]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6]]}},"alternative-id":["257"],"URL":"https:\/\/doi.org\/10.1007\/s00446-015-0257-4","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,10,23]]}}}