--- _id: '33240' author: - first_name: Thorsten full_name: Götte, Thorsten id: '34727' last_name: Götte - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler citation: ama: 'Götte T, Scheideler C. Brief Announcement: The (Limited) Power of Multiple Identities: Asynchronous Byzantine Reliable Broadcast with Improved Resilience through Collusion. In: Agrawal K, Lee I-TA, eds. SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022. ACM; 2022:99–101. doi:10.1145/3490148.3538556' apa: 'Götte, T., & Scheideler, C. (2022). Brief Announcement: The (Limited) Power of Multiple Identities: Asynchronous Byzantine Reliable Broadcast with Improved Resilience through Collusion. In K. Agrawal & I.-T. A. Lee (Eds.), SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022 (pp. 99–101). ACM. https://doi.org/10.1145/3490148.3538556' bibtex: '@inproceedings{Götte_Scheideler_2022, title={Brief Announcement: The (Limited) Power of Multiple Identities: Asynchronous Byzantine Reliable Broadcast with Improved Resilience through Collusion}, DOI={10.1145/3490148.3538556}, booktitle={SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022}, publisher={ACM}, author={Götte, Thorsten and Scheideler, Christian}, editor={Agrawal, Kunal and Lee, I-Ting Angelina}, year={2022}, pages={99–101} }' chicago: 'Götte, Thorsten, and Christian Scheideler. “Brief Announcement: The (Limited) Power of Multiple Identities: Asynchronous Byzantine Reliable Broadcast with Improved Resilience through Collusion.” In SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022, edited by Kunal Agrawal and I-Ting Angelina Lee, 99–101. ACM, 2022. https://doi.org/10.1145/3490148.3538556.' ieee: 'T. Götte and C. Scheideler, “Brief Announcement: The (Limited) Power of Multiple Identities: Asynchronous Byzantine Reliable Broadcast with Improved Resilience through Collusion,” in SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022, 2022, pp. 99–101, doi: 10.1145/3490148.3538556.' mla: 'Götte, Thorsten, and Christian Scheideler. “Brief Announcement: The (Limited) Power of Multiple Identities: Asynchronous Byzantine Reliable Broadcast with Improved Resilience through Collusion.” SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022, edited by Kunal Agrawal and I-Ting Angelina Lee, ACM, 2022, pp. 99–101, doi:10.1145/3490148.3538556.' short: 'T. Götte, C. Scheideler, in: K. Agrawal, I.-T.A. Lee (Eds.), SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022, ACM, 2022, pp. 99–101.' date_created: 2022-09-01T07:55:00Z date_updated: 2022-09-01T07:57:53Z department: - _id: '79' doi: 10.1145/3490148.3538556 editor: - first_name: Kunal full_name: Agrawal, Kunal last_name: Agrawal - first_name: I-Ting Angelina full_name: Lee, I-Ting Angelina last_name: Lee language: - iso: eng page: 99–101 project: - _id: '1' name: 'SFB 901: SFB 901' - _id: '4' name: 'SFB 901 - C: SFB 901 - Project Area C' - _id: '13' name: 'SFB 901 - C1: SFB 901 - Subproject C1' publication: 'SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022' publisher: ACM status: public title: 'Brief Announcement: The (Limited) Power of Multiple Identities: Asynchronous Byzantine Reliable Broadcast with Improved Resilience through Collusion' type: conference user_id: '15504' year: '2022' ... --- _id: '30987' author: - first_name: Irina full_name: Kostitsyna, Irina last_name: Kostitsyna - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler - first_name: Daniel full_name: Warner, Daniel id: '3902' last_name: Warner citation: ama: 'Kostitsyna I, Scheideler C, Warner D. Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model. In: Aspnes J, Michail O, eds. 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Vol 221. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik; 2022:23:1–23:3. doi:10.4230/LIPIcs.SAND.2022.23' apa: 'Kostitsyna, I., Scheideler, C., & Warner, D. (2022). Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model. In J. Aspnes & O. Michail (Eds.), 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022) (Vol. 221, p. 23:1–23:3). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SAND.2022.23' bibtex: '@inproceedings{Kostitsyna_Scheideler_Warner_2022, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model}, volume={221}, DOI={10.4230/LIPIcs.SAND.2022.23}, booktitle={1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)}, publisher={Schloss Dagstuhl – Leibniz-Zentrum für Informatik}, author={Kostitsyna, Irina and Scheideler, Christian and Warner, Daniel}, editor={Aspnes, James and Michail, Othon}, year={2022}, pages={23:1–23:3}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }' chicago: 'Kostitsyna, Irina, Christian Scheideler, and Daniel Warner. “Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model.” In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), edited by James Aspnes and Othon Michail, 221:23:1–23:3. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.SAND.2022.23.' ieee: 'I. Kostitsyna, C. Scheideler, and D. Warner, “Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model,” in 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), 2022, vol. 221, p. 23:1–23:3, doi: 10.4230/LIPIcs.SAND.2022.23.' mla: 'Kostitsyna, Irina, et al. “Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model.” 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), edited by James Aspnes and Othon Michail, vol. 221, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, p. 23:1–23:3, doi:10.4230/LIPIcs.SAND.2022.23.' short: 'I. Kostitsyna, C. Scheideler, D. Warner, in: J. Aspnes, O. Michail (Eds.), 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2022, p. 23:1–23:3.' date_created: 2022-05-03T00:13:06Z date_updated: 2022-10-27T08:45:52Z department: - _id: '79' doi: 10.4230/LIPIcs.SAND.2022.23 editor: - first_name: James full_name: Aspnes, James last_name: Aspnes - first_name: Othon full_name: Michail, Othon last_name: Michail intvolume: ' 221' language: - iso: eng page: 23:1–23:3 place: Dagstuhl, Germany project: - _id: '1' name: 'SFB 901: SFB 901' - _id: '4' name: 'SFB 901 - C: SFB 901 - Project Area C' - _id: '13' name: 'SFB 901 - C1: SFB 901 - Subproject C1' publication: 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022) publication_identifier: isbn: - 978-3-95977-224-2 issn: - 1868-8969 publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik series_title: Leibniz International Proceedings in Informatics (LIPIcs) status: public title: 'Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model' type: conference user_id: '15504' volume: 221 year: '2022' ... --- _id: '33967' author: - first_name: Marcos full_name: Aguiliera, Marcos last_name: Aguiliera - first_name: Andréa W. full_name: Richa, Andréa W. last_name: Richa - first_name: Alexander A. full_name: Schwarzmann, Alexander A. last_name: Schwarzmann - first_name: Alessandro full_name: Panconesi, Alessandro last_name: Panconesi - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler - first_name: Philipp full_name: Woelfel, Philipp last_name: Woelfel citation: ama: 'Aguiliera M, Richa AW, Schwarzmann AA, Panconesi A, Scheideler C, Woelfel P. 2022 Edsger W. Dijkstra Prize in Distributed Computing. In: Milani A, Woelfel P, eds. PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022. ACM; 2022:1. doi:10.1145/3519270.3538411' apa: 'Aguiliera, M., Richa, A. W., Schwarzmann, A. A., Panconesi, A., Scheideler, C., & Woelfel, P. (2022). 2022 Edsger W. Dijkstra Prize in Distributed Computing. In A. Milani & P. Woelfel (Eds.), PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022 (p. 1). ACM. https://doi.org/10.1145/3519270.3538411' bibtex: '@inproceedings{Aguiliera_Richa_Schwarzmann_Panconesi_Scheideler_Woelfel_2022, title={2022 Edsger W. Dijkstra Prize in Distributed Computing}, DOI={10.1145/3519270.3538411}, booktitle={PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022}, publisher={ACM}, author={Aguiliera, Marcos and Richa, Andréa W. and Schwarzmann, Alexander A. and Panconesi, Alessandro and Scheideler, Christian and Woelfel, Philipp}, editor={Milani, Alessia and Woelfel, Philipp}, year={2022}, pages={1} }' chicago: 'Aguiliera, Marcos, Andréa W. Richa, Alexander A. Schwarzmann, Alessandro Panconesi, Christian Scheideler, and Philipp Woelfel. “2022 Edsger W. Dijkstra Prize in Distributed Computing.” In PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022, edited by Alessia Milani and Philipp Woelfel, 1. ACM, 2022. https://doi.org/10.1145/3519270.3538411.' ieee: 'M. Aguiliera, A. W. Richa, A. A. Schwarzmann, A. Panconesi, C. Scheideler, and P. Woelfel, “2022 Edsger W. Dijkstra Prize in Distributed Computing,” in PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022, 2022, p. 1, doi: 10.1145/3519270.3538411.' mla: 'Aguiliera, Marcos, et al. “2022 Edsger W. Dijkstra Prize in Distributed Computing.” PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022, edited by Alessia Milani and Philipp Woelfel, ACM, 2022, p. 1, doi:10.1145/3519270.3538411.' short: 'M. Aguiliera, A.W. Richa, A.A. Schwarzmann, A. Panconesi, C. Scheideler, P. Woelfel, in: A. Milani, P. Woelfel (Eds.), PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022, ACM, 2022, p. 1.' date_created: 2022-11-02T08:53:37Z date_updated: 2022-11-02T08:56:16Z department: - _id: '79' doi: 10.1145/3519270.3538411 editor: - first_name: Alessia full_name: Milani, Alessia last_name: Milani - first_name: Philipp full_name: Woelfel, Philipp last_name: Woelfel language: - iso: eng page: '1' project: - _id: '1' name: 'SFB 901: SFB 901' - _id: '2' name: 'SFB 901 - A: SFB 901 - Project Area A' - _id: '5' name: 'SFB 901 - A1: SFB 901 - Subproject A1' publication: 'PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022' publisher: ACM status: public title: 2022 Edsger W. Dijkstra Prize in Distributed Computing type: conference user_id: '15504' year: '2022' ... --- _id: '21096' abstract: - lang: eng text: While many research in distributed computing has covered solutions for self-stabilizing computing and topologies, there is far less work on self-stabilization for distributed data structures. However, when peers in peer-to-peer networks crash, a distributed data structure may not remain intact. We present a self-stabilizing protocol for a distributed data structure called the Hashed Patricia Trie (Kniesburges and Scheideler WALCOM'11) that enables efficient prefix search on a set of keys. The data structure has many applications while offering low overhead and efficient operations when embedded on top of a Distributed Hash Table. Especially, longest prefix matching for x can be done in O(log |x|) hash table read accesses. We show how to maintain the structure in a self-stabilizing way, while assuring a low overhead in a legal state and an asymptotically optimal memory demand of O(d) bits, where d is the number of bits needed for storing all keys. article_number: '104697' author: - first_name: Till full_name: Knollmann, Till id: '39241' last_name: Knollmann orcid: 0000-0003-2014-4696 - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler citation: ama: Knollmann T, Scheideler C. A self-stabilizing Hashed Patricia Trie. Information and Computation. Published online 2022. doi:10.1016/j.ic.2021.104697 apa: Knollmann, T., & Scheideler, C. (2022). A self-stabilizing Hashed Patricia Trie. Information and Computation, Article 104697. https://doi.org/10.1016/j.ic.2021.104697 bibtex: '@article{Knollmann_Scheideler_2022, title={A self-stabilizing Hashed Patricia Trie}, DOI={10.1016/j.ic.2021.104697}, number={104697}, journal={Information and Computation}, author={Knollmann, Till and Scheideler, Christian}, year={2022} }' chicago: Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia Trie.” Information and Computation, 2022. https://doi.org/10.1016/j.ic.2021.104697. ieee: 'T. Knollmann and C. Scheideler, “A self-stabilizing Hashed Patricia Trie,” Information and Computation, Art. no. 104697, 2022, doi: 10.1016/j.ic.2021.104697.' mla: Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia Trie.” Information and Computation, 104697, 2022, doi:10.1016/j.ic.2021.104697. short: T. Knollmann, C. Scheideler, Information and Computation (2022). date_created: 2021-01-29T09:39:40Z date_updated: 2023-03-27T07:56:48Z department: - _id: '63' - _id: '79' doi: 10.1016/j.ic.2021.104697 language: - iso: eng project: - _id: '1' name: SFB 901 - _id: '2' name: SFB 901 - Project Area A - _id: '5' name: SFB 901 - Subproject A1 publication: Information and Computation publication_identifier: issn: - 0890-5401 publication_status: published status: public title: A self-stabilizing Hashed Patricia Trie type: journal_article user_id: '15504' year: '2022' ... --- _id: '25105' author: - first_name: Shlomi full_name: Dolev, Shlomi last_name: Dolev - first_name: Ram full_name: Prasadh Narayanan, Ram last_name: Prasadh Narayanan - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler - first_name: Christian full_name: Schindelhauer, Christian last_name: Schindelhauer citation: ama: 'Dolev S, Prasadh Narayanan R, Scheideler C, Schindelhauer C. Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization. In: Galluccio L, Mitra U, Magarini M, Abada S, Taynnan Barros M, Krishnaswamy B, eds. NANOCOM ’21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021. ACM; 2021:30:1-30:2. doi:10.1145/3477206.3477471' apa: 'Dolev, S., Prasadh Narayanan, R., Scheideler, C., & Schindelhauer, C. (2021). Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization. In L. Galluccio, U. Mitra, M. Magarini, S. Abada, M. Taynnan Barros, & B. Krishnaswamy (Eds.), NANOCOM ’21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021 (p. 30:1-30:2). ACM. https://doi.org/10.1145/3477206.3477471' bibtex: '@inproceedings{Dolev_Prasadh Narayanan_Scheideler_Schindelhauer_2021, title={Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization}, DOI={10.1145/3477206.3477471}, booktitle={NANOCOM ’21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021}, publisher={ACM}, author={Dolev, Shlomi and Prasadh Narayanan, Ram and Scheideler, Christian and Schindelhauer, Christian}, editor={Galluccio, Laura and Mitra, Urbashi and Magarini, Maurizio and Abada, Sergi and Taynnan Barros, Michael and Krishnaswamy, Bhuvana}, year={2021}, pages={30:1-30:2} }' chicago: 'Dolev, Shlomi, Ram Prasadh Narayanan, Christian Scheideler, and Christian Schindelhauer. “Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization.” In NANOCOM ’21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021, edited by Laura Galluccio, Urbashi Mitra, Maurizio Magarini, Sergi Abada, Michael Taynnan Barros, and Bhuvana Krishnaswamy, 30:1-30:2. ACM, 2021. https://doi.org/10.1145/3477206.3477471.' ieee: 'S. Dolev, R. Prasadh Narayanan, C. Scheideler, and C. Schindelhauer, “Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization,” in NANOCOM ’21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021, 2021, p. 30:1-30:2, doi: 10.1145/3477206.3477471.' mla: 'Dolev, Shlomi, et al. “Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization.” NANOCOM ’21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021, edited by Laura Galluccio et al., ACM, 2021, p. 30:1-30:2, doi:10.1145/3477206.3477471.' short: 'S. Dolev, R. Prasadh Narayanan, C. Scheideler, C. Schindelhauer, in: L. Galluccio, U. Mitra, M. Magarini, S. Abada, M. Taynnan Barros, B. Krishnaswamy (Eds.), NANOCOM ’21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021, ACM, 2021, p. 30:1-30:2.' date_created: 2021-09-29T09:09:58Z date_updated: 2022-01-06T06:56:51Z doi: 10.1145/3477206.3477471 editor: - first_name: Laura full_name: Galluccio, Laura last_name: Galluccio - first_name: Urbashi full_name: Mitra, Urbashi last_name: Mitra - first_name: Maurizio full_name: Magarini, Maurizio last_name: Magarini - first_name: Sergi full_name: Abada, Sergi last_name: Abada - first_name: Michael full_name: Taynnan Barros, Michael last_name: Taynnan Barros - first_name: Bhuvana full_name: Krishnaswamy, Bhuvana last_name: Krishnaswamy language: - iso: eng page: 30:1-30:2 publication: 'NANOCOM ''21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021' publisher: ACM status: public title: Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization type: conference user_id: '15504' year: '2021' ... --- _id: '28917' author: - first_name: Michael full_name: Feldmann, Michael last_name: Feldmann - first_name: Andreas full_name: Padalkin, Andreas id: '88238' last_name: Padalkin - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler - first_name: Shlomi full_name: Dolev, Shlomi last_name: Dolev citation: ama: 'Feldmann M, Padalkin A, Scheideler C, Dolev S. Coordinating Amoebots via Reconfigurable Circuits. In: Johnen C, Michael Schiller E, Schmid S, eds. Stabilization, Safety, and Security of Distributed Systems - 23rd International Symposium, (SSS) 2021, Virtual Event, November 17-20, 2021, Proceedings. Vol 13046. Lecture Notes in Computer Science. Springer; 2021:484-488. doi:10.1007/978-3-030-91081-5\_34' apa: Feldmann, M., Padalkin, A., Scheideler, C., & Dolev, S. (2021). Coordinating Amoebots via Reconfigurable Circuits. In C. Johnen, E. Michael Schiller, & S. Schmid (Eds.), Stabilization, Safety, and Security of Distributed Systems - 23rd International Symposium, (SSS) 2021, Virtual Event, November 17-20, 2021, Proceedings (Vol. 13046, pp. 484–488). Springer. https://doi.org/10.1007/978-3-030-91081-5\_34 bibtex: '@inproceedings{Feldmann_Padalkin_Scheideler_Dolev_2021, series={Lecture Notes in Computer Science}, title={Coordinating Amoebots via Reconfigurable Circuits}, volume={13046}, DOI={10.1007/978-3-030-91081-5\_34}, booktitle={Stabilization, Safety, and Security of Distributed Systems - 23rd International Symposium, (SSS) 2021, Virtual Event, November 17-20, 2021, Proceedings}, publisher={Springer}, author={Feldmann, Michael and Padalkin, Andreas and Scheideler, Christian and Dolev, Shlomi}, editor={Johnen, Colette and Michael Schiller, Elad and Schmid, Stefan}, year={2021}, pages={484–488}, collection={Lecture Notes in Computer Science} }' chicago: Feldmann, Michael, Andreas Padalkin, Christian Scheideler, and Shlomi Dolev. “Coordinating Amoebots via Reconfigurable Circuits.” In Stabilization, Safety, and Security of Distributed Systems - 23rd International Symposium, (SSS) 2021, Virtual Event, November 17-20, 2021, Proceedings, edited by Colette Johnen, Elad Michael Schiller, and Stefan Schmid, 13046:484–88. Lecture Notes in Computer Science. Springer, 2021. https://doi.org/10.1007/978-3-030-91081-5\_34. ieee: 'M. Feldmann, A. Padalkin, C. Scheideler, and S. Dolev, “Coordinating Amoebots via Reconfigurable Circuits,” in Stabilization, Safety, and Security of Distributed Systems - 23rd International Symposium, (SSS) 2021, Virtual Event, November 17-20, 2021, Proceedings, 2021, vol. 13046, pp. 484–488, doi: 10.1007/978-3-030-91081-5\_34.' mla: Feldmann, Michael, et al. “Coordinating Amoebots via Reconfigurable Circuits.” Stabilization, Safety, and Security of Distributed Systems - 23rd International Symposium, (SSS) 2021, Virtual Event, November 17-20, 2021, Proceedings, edited by Colette Johnen et al., vol. 13046, Springer, 2021, pp. 484–88, doi:10.1007/978-3-030-91081-5\_34. short: 'M. Feldmann, A. Padalkin, C. Scheideler, S. Dolev, in: C. Johnen, E. Michael Schiller, S. Schmid (Eds.), Stabilization, Safety, and Security of Distributed Systems - 23rd International Symposium, (SSS) 2021, Virtual Event, November 17-20, 2021, Proceedings, Springer, 2021, pp. 484–488.' date_created: 2021-12-15T09:37:38Z date_updated: 2022-01-06T06:58:41Z department: - _id: '79' doi: 10.1007/978-3-030-91081-5\_34 editor: - first_name: Colette full_name: Johnen, Colette last_name: Johnen - first_name: Elad full_name: Michael Schiller, Elad last_name: Michael Schiller - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid intvolume: ' 13046' language: - iso: eng page: 484-488 publication: Stabilization, Safety, and Security of Distributed Systems - 23rd International Symposium, (SSS) 2021, Virtual Event, November 17-20, 2021, Proceedings publisher: Springer series_title: Lecture Notes in Computer Science status: public title: Coordinating Amoebots via Reconfigurable Circuits type: conference user_id: '15504' volume: 13046 year: '2021' ... --- _id: '27048' author: - first_name: Shlomi full_name: Dolev, Shlomi last_name: Dolev - first_name: Ram full_name: Prasadh Narayanan, Ram last_name: Prasadh Narayanan - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler - first_name: Christian full_name: Schindelhauer, Christian last_name: Schindelhauer citation: ama: 'Dolev S, Prasadh Narayanan R, Scheideler C, Schindelhauer C. Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization. In: Galluccio L, Mitra U, Magarini M, Abada S, Taynnan Barros M, Krishnaswamy B, eds. NANOCOM ’21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021. ACM; 2021:30:1-30:2. doi:10.1145/3477206.3477471' apa: 'Dolev, S., Prasadh Narayanan, R., Scheideler, C., & Schindelhauer, C. (2021). Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization. In L. Galluccio, U. Mitra, M. Magarini, S. Abada, M. Taynnan Barros, & B. Krishnaswamy (Eds.), NANOCOM ’21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021 (p. 30:1-30:2). ACM. https://doi.org/10.1145/3477206.3477471' bibtex: '@inproceedings{Dolev_Prasadh Narayanan_Scheideler_Schindelhauer_2021, title={Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization}, DOI={10.1145/3477206.3477471}, booktitle={NANOCOM ’21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021}, publisher={ACM}, author={Dolev, Shlomi and Prasadh Narayanan, Ram and Scheideler, Christian and Schindelhauer, Christian}, editor={Galluccio, Laura and Mitra, Urbashi and Magarini, Maurizio and Abada, Sergi and Taynnan Barros, Michael and Krishnaswamy, Bhuvana}, year={2021}, pages={30:1-30:2} }' chicago: 'Dolev, Shlomi, Ram Prasadh Narayanan, Christian Scheideler, and Christian Schindelhauer. “Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization.” In NANOCOM ’21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021, edited by Laura Galluccio, Urbashi Mitra, Maurizio Magarini, Sergi Abada, Michael Taynnan Barros, and Bhuvana Krishnaswamy, 30:1-30:2. ACM, 2021. https://doi.org/10.1145/3477206.3477471.' ieee: 'S. Dolev, R. Prasadh Narayanan, C. Scheideler, and C. Schindelhauer, “Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization,” in NANOCOM ’21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021, 2021, p. 30:1-30:2, doi: 10.1145/3477206.3477471.' mla: 'Dolev, Shlomi, et al. “Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization.” NANOCOM ’21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021, edited by Laura Galluccio et al., ACM, 2021, p. 30:1-30:2, doi:10.1145/3477206.3477471.' short: 'S. Dolev, R. Prasadh Narayanan, C. Scheideler, C. Schindelhauer, in: L. Galluccio, U. Mitra, M. Magarini, S. Abada, M. Taynnan Barros, B. Krishnaswamy (Eds.), NANOCOM ’21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021, ACM, 2021, p. 30:1-30:2.' date_created: 2021-11-02T09:57:53Z date_updated: 2022-01-06T06:57:33Z doi: 10.1145/3477206.3477471 editor: - first_name: Laura full_name: Galluccio, Laura last_name: Galluccio - first_name: Urbashi full_name: Mitra, Urbashi last_name: Mitra - first_name: Maurizio full_name: Magarini, Maurizio last_name: Magarini - first_name: Sergi full_name: Abada, Sergi last_name: Abada - first_name: Michael full_name: Taynnan Barros, Michael last_name: Taynnan Barros - first_name: Bhuvana full_name: Krishnaswamy, Bhuvana last_name: Krishnaswamy language: - iso: eng page: 30:1-30:2 publication: 'NANOCOM ''21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021' publisher: ACM status: public title: Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization type: conference user_id: '15504' year: '2021' ... --- _id: '27050' author: - first_name: Joshua full_name: J. Daymude, Joshua last_name: J. Daymude - first_name: Andrea full_name: W. Richa, Andrea last_name: W. Richa - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler citation: ama: 'J. Daymude J, W. Richa A, Scheideler C. The Canonical Amoebot Model: Algorithms and Concurrency Control. In: Gilbert S, ed. 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference). Vol 209. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021:20:1-20:19. doi:10.4230/LIPIcs.DISC.2021.20' apa: 'J. Daymude, J., W. Richa, A., & Scheideler, C. (2021). The Canonical Amoebot Model: Algorithms and Concurrency Control. In S. Gilbert (Ed.), 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference) (Vol. 209, p. 20:1-20:19). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2021.20' bibtex: '@inproceedings{J. Daymude_W. Richa_Scheideler_2021, series={LIPIcs}, title={The Canonical Amoebot Model: Algorithms and Concurrency Control}, volume={209}, DOI={10.4230/LIPIcs.DISC.2021.20}, booktitle={35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference)}, publisher={Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, author={J. Daymude, Joshua and W. Richa, Andrea and Scheideler, Christian}, editor={Gilbert, Seth}, year={2021}, pages={20:1-20:19}, collection={LIPIcs} }' chicago: 'J. Daymude, Joshua, Andrea W. Richa, and Christian Scheideler. “The Canonical Amoebot Model: Algorithms and Concurrency Control.” In 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), edited by Seth Gilbert, 209:20:1-20:19. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.DISC.2021.20.' ieee: 'J. J. Daymude, A. W. Richa, and C. Scheideler, “The Canonical Amoebot Model: Algorithms and Concurrency Control,” in 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), 2021, vol. 209, p. 20:1-20:19, doi: 10.4230/LIPIcs.DISC.2021.20.' mla: 'J. Daymude, Joshua, et al. “The Canonical Amoebot Model: Algorithms and Concurrency Control.” 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), edited by Seth Gilbert, vol. 209, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 20:1-20:19, doi:10.4230/LIPIcs.DISC.2021.20.' short: 'J. J. Daymude, A. W. Richa, C. Scheideler, in: S. Gilbert (Ed.), 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 20:1-20:19.' date_created: 2021-11-02T10:00:00Z date_updated: 2022-01-06T06:57:33Z doi: 10.4230/LIPIcs.DISC.2021.20 editor: - first_name: Seth full_name: Gilbert, Seth last_name: Gilbert intvolume: ' 209' language: - iso: eng page: 20:1-20:19 publication: 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference) publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik series_title: LIPIcs status: public title: 'The Canonical Amoebot Model: Algorithms and Concurrency Control' type: conference user_id: '15504' volume: 209 year: '2021' ... --- _id: '22283' abstract: - lang: eng text: " We show how to construct an overlay network of constant degree and diameter $O(\\log n)$ in time $O(\\log n)$ starting from an arbitrary weakly connected graph.\r\n We assume a synchronous communication network in which nodes can send messages to nodes they know the identifier of and establish new connections by sending node identifiers.\r\n If the initial network's graph is weakly connected and has constant degree, then our algorithm constructs the desired topology with each node sending and receiving only $O(\\log n)$ messages in each round in time $O(\\log n)$, w.h.p., which beats the currently best $O(\\log^{3/2} n)$ time algorithm of [Götte et al., SIROCCO'19].\r\n Since the problem cannot be solved faster than by using pointer jumping for $O(\\log n)$ rounds (which would even require each node to communicate $\\Omega(n)$ bits), our algorithm is asymptotically optimal.\r\n \ We achieve this speedup by using short random walks to repeatedly establish random connections between the nodes that quickly reduce the conductance of the graph using an observation of [Kwok and Lau, APPROX'14].\r\n \r\n Additionally, we show how our algorithm can be used to efficiently solve graph problems in \\emph{hybrid networks} [Augustine et al., SODA'20].\r\n Motivated by the idea that nodes possess two different modes of communication, we assume that communication of the \\emph{initial} edges is unrestricted. In contrast, only polylogarithmically many messages can be communicated over edges that have been established throughout an algorithm's execution.\r\n For an (undirected) graph $G$ with arbitrary degree, we show how to compute connected components, a spanning tree, and biconnected components in time $O(\\log n)$, w.h.p.\r\n Furthermore, we show how to compute an MIS in time $O(\\log d + \\log \\log n)$, w.h.p., where $d$ is the initial degree of $G$." author: - first_name: Thorsten full_name: Götte, Thorsten id: '34727' last_name: Götte - first_name: Kristian full_name: Hinnenthal, Kristian id: '32229' last_name: Hinnenthal - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler - first_name: Julian full_name: Werthmann, Julian id: '50024' last_name: Werthmann citation: ama: 'Götte T, Hinnenthal K, Scheideler C, Werthmann J. Time-Optimal Construction of Overlays. In: Censor-Hillel K, ed. Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC ’21). New York: ACM. doi:10.1145/3465084.3467932' apa: 'Götte, T., Hinnenthal, K., Scheideler, C., & Werthmann, J. (n.d.). Time-Optimal Construction of Overlays. In K. Censor-Hillel (Ed.), Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC ’21). New York: ACM. https://doi.org/10.1145/3465084.3467932' bibtex: '@inproceedings{Götte_Hinnenthal_Scheideler_Werthmann, place={New York}, title={Time-Optimal Construction of Overlays}, DOI={10.1145/3465084.3467932}, booktitle={Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC ’21)}, publisher={ACM}, author={Götte, Thorsten and Hinnenthal, Kristian and Scheideler, Christian and Werthmann, Julian}, editor={Censor-Hillel, KerenEditor} }' chicago: 'Götte, Thorsten, Kristian Hinnenthal, Christian Scheideler, and Julian Werthmann. “Time-Optimal Construction of Overlays.” In Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC ’21), edited by Keren Censor-Hillel. New York: ACM, n.d. https://doi.org/10.1145/3465084.3467932.' ieee: T. Götte, K. Hinnenthal, C. Scheideler, and J. Werthmann, “Time-Optimal Construction of Overlays,” in Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC ’21), Virtual. mla: Götte, Thorsten, et al. “Time-Optimal Construction of Overlays.” Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC ’21), edited by Keren Censor-Hillel, ACM, doi:10.1145/3465084.3467932. short: 'T. Götte, K. Hinnenthal, C. Scheideler, J. Werthmann, in: K. Censor-Hillel (Ed.), Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC ’21), ACM, New York, n.d.' conference: end_date: 2021-07-30 location: Virtual name: ACM Symposium on Principles of Distributed Computing (PODC) start_date: 2021-07-26 date_created: 2021-06-06T19:10:26Z date_updated: 2022-01-06T06:55:30Z ddc: - '000' department: - _id: '34' doi: 10.1145/3465084.3467932 editor: - first_name: Keren full_name: Censor-Hillel, Keren last_name: Censor-Hillel file: - access_level: closed content_type: application/pdf creator: thgoette date_created: 2021-06-06T19:12:49Z date_updated: 2021-06-06T19:12:49Z file_id: '22284' file_name: Wicked_Fast_Overlay_Construction(1).pdf file_size: 590875 relation: main_file success: 1 file_date_updated: 2021-06-06T19:12:49Z has_accepted_license: '1' language: - iso: eng place: New York project: - _id: '2' name: SFB 901 - Project Area A - _id: '5' name: SFB 901 - Subproject A1 - _id: '4' name: SFB 901 - Project Area C - _id: '13' name: SFB 901 - Subproject C1 - _id: '1' name: SFB 901 publication: Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC '21) publication_status: accepted publisher: ACM status: public title: Time-Optimal Construction of Overlays type: conference user_id: '477' year: '2021' ... --- _id: '30217' author: - first_name: Sam full_name: Coy, Sam last_name: Coy - first_name: Artur full_name: Czumaj, Artur last_name: Czumaj - first_name: Michael full_name: Feldmann, Michael last_name: Feldmann - first_name: Kristian full_name: Hinnenthal, Kristian last_name: Hinnenthal - first_name: Fabian full_name: Kuhn, Fabian last_name: Kuhn - first_name: Christian full_name: Scheideler, Christian id: '20792' last_name: Scheideler - first_name: Philipp full_name: Schneider, Philipp last_name: Schneider - first_name: Martijn full_name: Struijs, Martijn last_name: Struijs citation: ama: 'Coy S, Czumaj A, Feldmann M, et al. Near-Shortest Path Routing in Hybrid Communication Networks. In: Bramas Q, Gramoli V, Milani A, eds. 25th International Conference on Principles of Distributed Systems, OPODIS 2021, December 13-15, 2021, Strasbourg, France. Vol 217. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021:11:1–11:23. doi:10.4230/LIPIcs.OPODIS.2021.11' apa: Coy, S., Czumaj, A., Feldmann, M., Hinnenthal, K., Kuhn, F., Scheideler, C., Schneider, P., & Struijs, M. (2021). Near-Shortest Path Routing in Hybrid Communication Networks. In Q. Bramas, V. Gramoli, & A. Milani (Eds.), 25th International Conference on Principles of Distributed Systems, OPODIS 2021, December 13-15, 2021, Strasbourg, France (Vol. 217, p. 11:1–11:23). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2021.11 bibtex: '@inproceedings{Coy_Czumaj_Feldmann_Hinnenthal_Kuhn_Scheideler_Schneider_Struijs_2021, series={LIPIcs}, title={Near-Shortest Path Routing in Hybrid Communication Networks}, volume={217}, DOI={10.4230/LIPIcs.OPODIS.2021.11}, booktitle={25th International Conference on Principles of Distributed Systems, OPODIS 2021, December 13-15, 2021, Strasbourg, France}, publisher={Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, author={Coy, Sam and Czumaj, Artur and Feldmann, Michael and Hinnenthal, Kristian and Kuhn, Fabian and Scheideler, Christian and Schneider, Philipp and Struijs, Martijn}, editor={Bramas, Quentin and Gramoli, Vincent and Milani, Alessia}, year={2021}, pages={11:1–11:23}, collection={LIPIcs} }' chicago: Coy, Sam, Artur Czumaj, Michael Feldmann, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Philipp Schneider, and Martijn Struijs. “Near-Shortest Path Routing in Hybrid Communication Networks.” In 25th International Conference on Principles of Distributed Systems, OPODIS 2021, December 13-15, 2021, Strasbourg, France, edited by Quentin Bramas, Vincent Gramoli, and Alessia Milani, 217:11:1–11:23. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.OPODIS.2021.11. ieee: 'S. Coy et al., “Near-Shortest Path Routing in Hybrid Communication Networks,” in 25th International Conference on Principles of Distributed Systems, OPODIS 2021, December 13-15, 2021, Strasbourg, France, 2021, vol. 217, p. 11:1–11:23, doi: 10.4230/LIPIcs.OPODIS.2021.11.' mla: Coy, Sam, et al. “Near-Shortest Path Routing in Hybrid Communication Networks.” 25th International Conference on Principles of Distributed Systems, OPODIS 2021, December 13-15, 2021, Strasbourg, France, edited by Quentin Bramas et al., vol. 217, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 11:1–11:23, doi:10.4230/LIPIcs.OPODIS.2021.11. short: 'S. Coy, A. Czumaj, M. Feldmann, K. Hinnenthal, F. Kuhn, C. Scheideler, P. Schneider, M. Struijs, in: Q. Bramas, V. Gramoli, A. Milani (Eds.), 25th International Conference on Principles of Distributed Systems, OPODIS 2021, December 13-15, 2021, Strasbourg, France, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 11:1–11:23.' date_created: 2022-03-09T10:43:28Z date_updated: 2022-03-09T10:46:34Z department: - _id: '79' doi: 10.4230/LIPIcs.OPODIS.2021.11 editor: - first_name: Quentin full_name: Bramas, Quentin last_name: Bramas - first_name: Vincent full_name: Gramoli, Vincent last_name: Gramoli - first_name: Alessia full_name: Milani, Alessia last_name: Milani intvolume: ' 217' language: - iso: eng page: 11:1–11:23 publication: 25th International Conference on Principles of Distributed Systems, OPODIS 2021, December 13-15, 2021, Strasbourg, France publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik series_title: LIPIcs status: public title: Near-Shortest Path Routing in Hybrid Communication Networks type: conference user_id: '15504' volume: 217 year: '2021' ...