{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,8]],"date-time":"2024-03-08T01:39:19Z","timestamp":1709861959554},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,9,22]],"date-time":"2013-09-22T00:00:00Z","timestamp":1379808000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2014,7]]},"DOI":"10.1007\/s00224-013-9504-x","type":"journal-article","created":{"date-parts":[[2013,9,21]],"date-time":"2013-09-21T02:01:35Z","timestamp":1379728895000},"page":"110-135","source":"Crossref","is-referenced-by-count":9,"title":["A Note on the Parallel Runtime of Self-Stabilizing Graph Linearization"],"prefix":"10.1007","volume":"55","author":[{"given":"Dominik","family":"Gall","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Riko","family":"Jacob","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Richa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Scheideler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hanjo","family":"T\u00e4ubig","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,9,22]]},"reference":[{"key":"9504_CR1","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1145\/1073970.1073991","volume-title":"Proc. of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"D. Angluin","year":"2005","unstructured":"Angluin, D., Aspnes, J., Chen, J., Wu, Y., Yin, Y.: Fast construction of overlay networks. In: Proc. of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 145\u2013154 (2005). doi: 10.1145\/1073970.1073991"},{"key":"9504_CR2","first-page":"384","volume-title":"Proc. of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"J. Aspnes","year":"2003","unstructured":"Aspnes, J., Shah, G.: Skip graphs. In: Proc. of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 384\u2013393 (2003)"},{"key":"9504_CR3","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1007\/978-3-540-77096-1_21","volume-title":"Proc. of the 11th Int. Conference on Principles of Distributed Systems (OPODIS)","author":"J. Aspnes","year":"2007","unstructured":"Aspnes, J., Wu, Y.: O(logn)-time overlay network construction from graphs with out-degree 1. In: Proc. of the 11th Int. Conference on Principles of Distributed Systems (OPODIS). LNCS, vol. 4878, pp. 286\u2013300. Springer, Berlin (2007). doi: 10.1007\/978-3-540-77096-1_21"},{"key":"9504_CR4","first-page":"258","volume-title":"Proc. of the 32nd IEEE Symposium on Foundations of Computer Science (FOCS)","author":"B. Awerbuch","year":"1991","unstructured":"Awerbuch, B., Varghese, G.: Distributed program checking: a paradigm for building self-stabilizing distributed protocols. In: Proc. of the 32nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 258\u2013267 (1991)"},{"issue":"1","key":"9504_CR5","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1137\/S0097539793259471","volume":"27","author":"R.D. Blumofe","year":"1998","unstructured":"Blumofe, R.D., Leiserson, C.E.: Space-efficient scheduling of multithreaded computations. SIAM J. Comput. 27(1), 202\u2013229 (1998). doi: 10.1137\/S0097539793259471","journal-title":"SIAM J. Comput."},{"issue":"5","key":"9504_CR6","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1145\/324133.324234","volume":"46","author":"R.D. Blumofe","year":"1999","unstructured":"Blumofe, R.D., Leiserson, C.E.: Scheduling multithreaded computations by work stealing. J. ACM 46(5), 720\u2013748 (1999). doi: 10.1145\/324133.324234","journal-title":"J. ACM"},{"issue":"1","key":"9504_CR7","first-page":"3","volume":"25","author":"J. Brzezi\u0144ski","year":"2000","unstructured":"Brzezi\u0144ski, J., Szychowiak, M.: Self-stabilization in distributed systems\u2014a short survey. Found. Comput. Decision Sci. 25(1), 3\u201322 (2000)","journal-title":"Found. Comput. Decision Sci."},{"issue":"3","key":"9504_CR8","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1109\/18.382023","volume":"41","author":"I. Cidon","year":"1995","unstructured":"Cidon, I., Gopal, I., Kutten, S.: New models and algorithms for future networks. IEEE Trans. Inf. Theory 41(3), 769\u2013780 (1995). doi: 10.1109\/18.382023","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9504_CR9","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/j.tcs.2011.12.079","volume":"428","author":"T. Clouser","year":"2012","unstructured":"Clouser, T., Nesterenko, M., Scheideler, C.: Tiara: a self-stabilizing deterministic skip list and skip graph. Theor. Comput. Sci. 428, 18\u201335 (2012). doi: 10.1016\/j.tcs.2011.12.079","journal-title":"Theor. Comput. Sci."},{"key":"9504_CR10","unstructured":"Cramer, C., Fuhrmann, T.: Self-stabilizing ring networks on connected graphs. Tech. Rep. 2005-5, System Architecture Group, University of Karlsruhe (2005)"},{"issue":"11","key":"9504_CR11","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1145\/361179.361202","volume":"17","author":"E.W. Dijkstra","year":"1974","unstructured":"Dijkstra, E.W.: Self-stabilization in spite of distributed control. Commun. ACM 17(11), 643\u2013644 (1974). doi: 10.1145\/361179.361202","journal-title":"Commun. ACM"},{"key":"9504_CR12","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/978-3-540-77096-1_25","volume-title":"Proc. of the 11th Int. Conference on Principles of Distributed Systems (OPODIS)","author":"D. Dolev","year":"2007","unstructured":"Dolev, D., Hoch, E.N., van Renesse, R.: Self-stabilizing and Byzantine-tolerant overlay network. In: Proc. of the 11th Int. Conference on Principles of Distributed Systems (OPODIS). LNCS, vol. 4878, pp. 343\u2013357. Springer, Berlin (2007). doi: 10.1007\/978-3-540-77096-1_25"},{"key":"9504_CR13","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/6156.001.0001","volume-title":"Self-Stabilization","author":"S. Dolev","year":"2000","unstructured":"Dolev, S.: Self-Stabilization. MIT Press, Cambridge (2000)"},{"issue":"5","key":"9504_CR14","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s00446-007-0038-9","volume":"20","author":"S. Dolev","year":"2008","unstructured":"Dolev, S., Kat, R.I.: HyperTree for self-stabilizing peer-to-peer systems. Distrib. Comput. 20(5), 375\u2013388 (2008). doi: 10.1007\/s00446-007-0038-9","journal-title":"Distrib. Comput."},{"key":"9504_CR15","series-title":"LNCS","first-page":"294","volume-title":"Proc. of the 9th Latin American Theoretical Informatics Symposium (LATIN)","author":"D. Gall","year":"2010","unstructured":"Gall, D., Jacob, R., Richa, A., Scheideler, C., Schmid, S., T\u00e4ubig, H.: Time complexity of distributed topological self-stabilization: the case of graph linearization. In: Proc. of the 9th Latin American Theoretical Informatics Symposium (LATIN). LNCS, vol. 6034, pp. 294\u2013305. Springer, Berlin (2010). doi: 10.1007\/978-3-642-12200-2_27"},{"issue":"2","key":"9504_CR16","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1145\/226643.226670","volume":"43","author":"M.T. Goodrich","year":"1996","unstructured":"Goodrich, M.T., Kosaraju, S.R.: Sorting on a parallel pointer machine with applications to set expression evaluation. J. ACM 43(2), 331\u2013361 (1996). doi: 10.1145\/226643.226670","journal-title":"J. ACM"},{"key":"9504_CR17","first-page":"229","volume-title":"Proc. of the 18th ACM Symposium on Principles of Distributed Computing (PODC)","author":"M. Harchol-Balter","year":"1999","unstructured":"Harchol-Balter, M., Leighton, T., Lewin, D.: Resource discovery in distributed networks. In: Proc. of the 18th ACM Symposium on Principles of Distributed Computing (PODC), pp. 229\u2013237 (1999). doi: 10.1145\/301308.301362"},{"key":"9504_CR18","volume-title":"Self-Stabilization Bibliography: Access Guide","author":"T. Herman","year":"2002","unstructured":"Herman, T.: In: Self-Stabilization Bibliography: Access Guide (2002). See ftp:\/\/ftp.cs.uiowa.edu\/pub\/selfstab\/bibliography\/"},{"key":"9504_CR19","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1145\/1582716.1582741","volume-title":"Proc. of the 28th ACM Symposium on Principles of Distributed Computing (PODC)","author":"R. Jacob","year":"2009","unstructured":"Jacob, R., Richa, A., Scheideler, C., Schmid, S., T\u00e4ubig, H.: A distributed polylogarithmic time algorithm for self-stabilizing skip graphs. In: Proc. of the 28th ACM Symposium on Principles of Distributed Computing (PODC), pp. 131\u2013140 (2009). doi: 10.1145\/1582716.1582741"},{"key":"9504_CR20","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.tcs.2012.07.029","volume":"457","author":"R. Jacob","year":"2012","unstructured":"Jacob, R., Ritscher, S., Scheideler, C., Schmid, S.: Towards higher-dimensional topological self-stabilization: a distributed algorithm for Delaunay graphs. Theor. Comput. Sci. 457, 137\u2013148 (2012). doi: 10.1016\/j.tcs.2012.07.029","journal-title":"Theor. Comput. Sci."},{"key":"9504_CR21","first-page":"235","volume-title":"Proc. of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"S. Kniesburges","year":"2011","unstructured":"Kniesburges, S., Koutsopoulos, A., Scheideler, C.: Re-Chord: a self-stabilizing Chord overlay network. In: Proc. of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 235\u2013244 (2011). doi: 10.1145\/1989493.1989527"},{"key":"9504_CR22","first-page":"133","volume-title":"Proc. of the 25th ACM Symposium on Principles of Distributed Computing (PODC)","author":"T. Moscibroda","year":"2006","unstructured":"Moscibroda, T., Schmid, S., Wattenhofer, R.: On the topologies formed by selfish peers. In: Proc. of the 25th ACM Symposium on Principles of Distributed Computing (PODC), pp. 133\u2013142 (2006). doi: 10.1145\/1146381.1146403"},{"key":"9504_CR23","first-page":"99","volume-title":"Proc. of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX)","author":"M. Onus","year":"2007","unstructured":"Onus, M., Richa, A., Scheideler, C.: Linearization: locally self-stabilizing sorting in graphs. In: Proc. of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 99\u2013108. SIAM, Philadelphia (2007)"},{"key":"9504_CR24","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1109\/P2P.2005.34","volume-title":"Proc. of the 5th IEEE Int. Conference on Peer-to-Peer Computing (P2P)","author":"A. Shaker","year":"2005","unstructured":"Shaker, A., Reeves, D.S.: Self-stabilizing structured ring topology P2P systems. In: Proc. of the 5th IEEE Int. Conference on Peer-to-Peer Computing (P2P), pp. 39\u201346 (2005). doi: 10.1109\/P2P.2005.34"},{"key":"9504_CR25","doi-asserted-by":"crossref","unstructured":"Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., Balakrishnan, H.: Chord: a scalable peer-to-peer lookup service for internet applications. Tech. Rep. MIT-LCS-TR-819, MIT (2001)","DOI":"10.1145\/383059.383071"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9504-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9504-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9504-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,24]],"date-time":"2019-07-24T11:15:39Z","timestamp":1563966939000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9504-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,22]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["9504"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9504-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9,22]]}}}