{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T17:05:23Z","timestamp":1754154323262,"version":"3.41.2"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030171261"},{"type":"electronic","value":"9783030171278"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T00:00:00Z","timestamp":1554422400000},"content-version":"vor","delay-in-days":94,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We propose a formal model of distributed computing based on register automata that captures a broad class of synchronous network algorithms. The local memory of each process is represented by a finite-state controller and a fixed number of registers, each of which can store the unique identifier of some process in the network. To underline the naturalness of our model, we show that it has the same expressive power as a certain extension of first-order logic on graphs whose nodes are equipped with a total order. Said extension lets us define new functions on the set of nodes by means of a so-called partial fixpoint operator. In spirit, our result bears close resemblance to a classical theorem of descriptive complexity theory that characterizes the complexity class <jats:inline-formula>\n              <jats:tex-math>$$\\textsc {pspace}$$<\/jats:tex-math>\n            <\/jats:inline-formula> in terms of partial fixpoint logic (a proper superclass of the logic we consider here).<\/jats:p>","DOI":"10.1007\/978-3-030-17127-8_7","type":"book-chapter","created":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T11:11:46Z","timestamp":1554462706000},"page":"115-132","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Identifiers in Registers"],"prefix":"10.1007","author":[{"given":"Benedikt","family":"Bollig","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patricia","family":"Bouyer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabian","family":"Reiter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,5]]},"reference":[{"key":"7_CR1","doi-asserted-by":"publisher","unstructured":"Abiteboul, S., Vianu, V.: Fixpoint extensions of first-order logic and datalog-like languages. In: Proceedings of the Fourth Annual Symposium on Logic in Computer Science (LICS 1989), Pacific Grove, California, USA, 5\u20138 June 1989, pp. 71\u201379. IEEE Computer Society (1989). https:\/\/doi.org\/10.1109\/LICS.1989.39160","DOI":"10.1109\/LICS.1989.39160"},{"key":"7_CR2","doi-asserted-by":"publisher","unstructured":"Aiswarya, C., Bollig, B., Gastin, P.: An automata-theoretic approach to the verification of distributed algorithms. In: Aceto, L., de Frutos-Escrig, D. (eds.) 26th International Conference on Concurrency Theory, CONCUR 2015, Madrid, Spain, 14 September 2015. LIPIcs, vol. 42, pp. 340\u2013353. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2015.340","DOI":"10.4230\/LIPIcs.CONCUR.2015.340"},{"issue":"Part 3","key":"7_CR3","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/j.ic.2017.05.006","volume":"259","author":"C Aiswarya","year":"2018","unstructured":"Aiswarya, C., Bollig, B., Gastin, P.: An automata-theoretic approach to the verification of distributed algorithms. Inf. Comput. 259(Part 3), 305\u2013327 (2018). https:\/\/doi.org\/10.1016\/j.ic.2017.05.006","journal-title":"Inf. Comput."},{"key":"7_CR4","doi-asserted-by":"publisher","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Encyclopedia of Mathematics and Its Applications, vol. 138. Cambridge University Press, Cambridge (2012). https:\/\/hal.archives-ouvertes.fr\/hal-00646514. https:\/\/doi.org\/10.1017\/CBO9780511977619","DOI":"10.1017\/CBO9780511977619"},{"key":"7_CR5","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2017","unstructured":"Diestel, R.: Graph Theory. GTM, vol. 173. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-53622-3"},{"key":"7_CR6","unstructured":"Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Karp, R.M. (ed.) Complexity of Computation. SIAM-AMS Proceedings, vol. 7, pp. 43\u201373 (1974). http:\/\/www.almaden.ibm.com\/cs\/people\/fagin\/genspec.pdf"},{"key":"7_CR7","unstructured":"Feuilloley, L., Fraigniaud, P.: Survey of distributed decision. Bull. EATCS 119 (2016). http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/411"},{"key":"7_CR8","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68804-8","volume-title":"Finite Model Theory and Its Applications","author":"E Gr\u00e4del","year":"2007","unstructured":"Gr\u00e4del, E., et al.: Finite Model Theory and Its Applications. Texts in Theoretical Computer Science. An EATCS Series, 1st edn. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/3-540-68804-8","edition":"1"},{"key":"7_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-642-11409-0_14","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S Grumbach","year":"2010","unstructured":"Grumbach, S., Wu, Z.: Logical locality entails frugal distributed computation over graphs (extended abstract). In: Paul, C., Habib, M. (eds.) WG 2009. LNCS, vol. 5911, pp. 154\u2013165. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11409-0_14"},{"key":"7_CR10","doi-asserted-by":"publisher","unstructured":"Hella, L., et al.: Weak models of distributed computing, with connections to modal logic. In: Kowalski, D., Panconesi, A. (eds.) ACM Symposium on Principles of Distributed Computing, PODC 2012, Funchal, Madeira, Portugal, 16\u201318 July 2012, pp. 185\u2013194. ACM (2012). https:\/\/doi.org\/10.1145\/2332432.2332466","DOI":"10.1145\/2332432.2332466"},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"Hella, L., et al.: Weak models of distributed computing, with connections to modallogic. Distrib. Comput. 28(1), 31\u201353 (2015). https:\/\/arxiv.org\/abs\/1205.2051. http:\/\/dx.doi.org\/10.1007\/s00446-013-0202-3","DOI":"10.1007\/s00446-013-0202-3"},{"key":"7_CR12","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive Complexity. Texts in Computer Science. Springer, New York (1999). https:\/\/doi.org\/10.1007\/978-1-4612-0539-5"},{"issue":"2","key":"7_CR13","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/0304-3975(94)90242-9","volume":"134","author":"M Kaminski","year":"1994","unstructured":"Kaminski, M., Francez, N.: Finite-memory automata. Theor. Comput. Sci. 134(2), 329\u2013363 (1994). https:\/\/doi.org\/10.1016\/0304-3975(94)90242-9","journal-title":"Theor. Comput. Sci."},{"key":"7_CR14","doi-asserted-by":"publisher","unstructured":"Kuusisto, A.: Modal logic and distributed message passing automata. In: Rocca, S.R.D. (eds.) Computer Science Logic 2013 (CSL 2013), Torino, Italy, 2\u20135 September 2013, LIPIcs, vol. 23, pp. 452\u2013468. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2013). https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2013.452","DOI":"10.4230\/LIPIcs.CSL.2013.452"},{"key":"7_CR15","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"L Libkin","year":"2004","unstructured":"Libkin, L., et al.: Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series, 1st edn. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-662-07003-1","edition":"1"},{"issue":"6","key":"7_CR16","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). https:\/\/doi.org\/10.1137\/S0097539793254571","journal-title":"SIAM J. Comput."},{"key":"7_CR17","doi-asserted-by":"publisher","unstructured":"Reiter, F.: Distributed graph automata. In: 30th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, 6\u201310 July 2015, pp. 192\u2013201. IEEE Computer Society (2015). https:\/\/arxiv.org\/abs\/1408.3030. https:\/\/doi.org\/10.1109\/LICS.2015.27","DOI":"10.1109\/LICS.2015.27"},{"key":"7_CR18","doi-asserted-by":"publisher","unstructured":"Reiter, F.: Asynchronous distributed automata: a characterization of the modal MU-fragment. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, Warsaw, Poland, 10\u201314 July 2017. LIPIcs, vol. 80, pp. 100:1\u2013100:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017). http:\/\/arxiv.org\/abs\/1611.08554. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.100","DOI":"10.4230\/LIPIcs.ICALP.2017.100"},{"key":"7_CR19","doi-asserted-by":"publisher","unstructured":"Vardi, M.Y.: The complexity of relational query languages (extended abstract). In: Lewis, H.R., Simons, B.B., Burkhard, W.A., Landweber, L.H. (eds.) Proceedings of the 14th Annual ACM Symposium on Theory of Computing, San Francisco, California, USA, 5\u20137 May 1982, pp. 137\u2013146. ACM (1982). https:\/\/doi.org\/10.1145\/800070.802186","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-17127-8_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T05:14:22Z","timestamp":1753334062000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-17127-8_7"}},"subtitle":["Describing Network Algorithms with Logic"],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030171261","9783030171278"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-17127-8_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"5 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Prague","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Czech Republic","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 April 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.etaps.org\/2019\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}