[{"publication_identifier":{"isbn":["978-3-95977-361-4"],"issn":["1868-8969"]},"page":"45:1–45:26","intvolume":"       325","citation":{"mla":"Dou, Jinfeng, et al. “Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs.” <i>16th Innovations in Theoretical Computer Science Conference (ITCS 2025)</i>, edited by Raghu Meka, vol. 325, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025, p. 45:1–45:26, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.45\">10.4230/LIPIcs.ITCS.2025.45</a>.","bibtex":"@inproceedings{Dou_Götte_Hillebrandt_Scheideler_Werthmann_2025, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs}, volume={325}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.45\">10.4230/LIPIcs.ITCS.2025.45</a>}, booktitle={16th Innovations in Theoretical Computer Science Conference (ITCS 2025)}, publisher={Schloss Dagstuhl – Leibniz-Zentrum für Informatik}, author={Dou, Jinfeng and Götte, Thorsten and Hillebrandt, Henning and Scheideler, Christian and Werthmann, Julian}, editor={Meka, Raghu}, year={2025}, pages={45:1–45:26}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }","short":"J. Dou, T. Götte, H. Hillebrandt, C. Scheideler, J. Werthmann, in: R. Meka (Ed.), 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2025, p. 45:1–45:26.","apa":"Dou, J., Götte, T., Hillebrandt, H., Scheideler, C., &#38; Werthmann, J. (2025). Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs. In R. Meka (Ed.), <i>16th Innovations in Theoretical Computer Science Conference (ITCS 2025)</i> (Vol. 325, p. 45:1–45:26). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.45\">https://doi.org/10.4230/LIPIcs.ITCS.2025.45</a>","ieee":"J. Dou, T. Götte, H. Hillebrandt, C. Scheideler, and J. Werthmann, “Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs,” in <i>16th Innovations in Theoretical Computer Science Conference (ITCS 2025)</i>, 2025, vol. 325, p. 45:1–45:26, doi: <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.45\">10.4230/LIPIcs.ITCS.2025.45</a>.","chicago":"Dou, Jinfeng, Thorsten Götte, Henning Hillebrandt, Christian Scheideler, and Julian Werthmann. “Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs.” In <i>16th Innovations in Theoretical Computer Science Conference (ITCS 2025)</i>, edited by Raghu Meka, 325:45:1–45:26. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.45\">https://doi.org/10.4230/LIPIcs.ITCS.2025.45</a>.","ama":"Dou J, Götte T, Hillebrandt H, Scheideler C, Werthmann J. Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs. In: Meka R, ed. <i>16th Innovations in Theoretical Computer Science Conference (ITCS 2025)</i>. Vol 325. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik; 2025:45:1–45:26. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.45\">10.4230/LIPIcs.ITCS.2025.45</a>"},"place":"Dagstuhl, Germany","year":"2025","volume":325,"date_created":"2025-04-02T14:09:19Z","author":[{"first_name":"Jinfeng","last_name":"Dou","id":"92888","full_name":"Dou, Jinfeng"},{"full_name":"Götte, Thorsten","id":"34727","last_name":"Götte","first_name":"Thorsten"},{"id":"74425","full_name":"Hillebrandt, Henning","last_name":"Hillebrandt","first_name":"Henning"},{"last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792","first_name":"Christian"},{"first_name":"Julian","last_name":"Werthmann","full_name":"Werthmann, Julian","id":"50024"}],"publisher":"Schloss Dagstuhl – Leibniz-Zentrum für Informatik","date_updated":"2025-10-15T12:57:11Z","doi":"10.4230/LIPIcs.ITCS.2025.45","title":"Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs","publication":"16th Innovations in Theoretical Computer Science Conference (ITCS 2025)","type":"conference","status":"public","editor":[{"first_name":"Raghu","last_name":"Meka","full_name":"Meka, Raghu"}],"user_id":"34727","series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","_id":"59268","language":[{"iso":"eng"}]},{"year":"2023","citation":{"apa":"Götte, T., Kolb, C., Scheideler, C., &#38; Werthmann, J. (2023). Beep-and-Sleep: Message and Energy Efficient Set Cover. <i>Theor. Comput. Sci.</i>, <i>950</i>, 113756. <a href=\"https://doi.org/10.1016/j.tcs.2023.113756\">https://doi.org/10.1016/j.tcs.2023.113756</a>","mla":"Götte, Thorsten, et al. “Beep-and-Sleep: Message and Energy Efficient Set Cover.” <i>Theor. Comput. Sci.</i>, vol. 950, 2023, p. 113756, doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.113756\">10.1016/j.tcs.2023.113756</a>.","bibtex":"@article{Götte_Kolb_Scheideler_Werthmann_2023, title={Beep-and-Sleep: Message and Energy Efficient Set Cover}, volume={950}, DOI={<a href=\"https://doi.org/10.1016/j.tcs.2023.113756\">10.1016/j.tcs.2023.113756</a>}, journal={Theor. Comput. Sci.}, author={Götte, Thorsten and Kolb, Christina and Scheideler, Christian and Werthmann, Julian}, year={2023}, pages={113756} }","short":"T. Götte, C. Kolb, C. Scheideler, J. Werthmann, Theor. Comput. Sci. 950 (2023) 113756.","ieee":"T. Götte, C. Kolb, C. Scheideler, and J. Werthmann, “Beep-and-Sleep: Message and Energy Efficient Set Cover,” <i>Theor. Comput. Sci.</i>, vol. 950, p. 113756, 2023, doi: <a href=\"https://doi.org/10.1016/j.tcs.2023.113756\">10.1016/j.tcs.2023.113756</a>.","chicago":"Götte, Thorsten, Christina Kolb, Christian Scheideler, and Julian Werthmann. “Beep-and-Sleep: Message and Energy Efficient Set Cover.” <i>Theor. Comput. Sci.</i> 950 (2023): 113756. <a href=\"https://doi.org/10.1016/j.tcs.2023.113756\">https://doi.org/10.1016/j.tcs.2023.113756</a>.","ama":"Götte T, Kolb C, Scheideler C, Werthmann J. Beep-and-Sleep: Message and Energy Efficient Set Cover. <i>Theor Comput Sci</i>. 2023;950:113756. doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.113756\">10.1016/j.tcs.2023.113756</a>"},"intvolume":"       950","page":"113756","title":"Beep-and-Sleep: Message and Energy Efficient Set Cover","doi":"10.1016/j.tcs.2023.113756","date_updated":"2023-03-27T09:55:04Z","date_created":"2023-03-27T07:45:44Z","author":[{"first_name":"Thorsten","full_name":"Götte, Thorsten","id":"34727","last_name":"Götte"},{"full_name":"Kolb, Christina","last_name":"Kolb","first_name":"Christina"},{"full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler","first_name":"Christian"},{"first_name":"Julian","last_name":"Werthmann","id":"50024","full_name":"Werthmann, Julian"}],"volume":950,"status":"public","type":"journal_article","publication":"Theor. Comput. Sci.","language":[{"iso":"eng"}],"project":[{"_id":"1","name":"SFB 901: SFB 901"},{"name":"SFB 901 - A: SFB 901 - Project Area A","_id":"2"},{"_id":"5","name":"SFB 901 - A1: SFB 901 - Subproject A1"}],"_id":"43109","user_id":"15504","department":[{"_id":"79"}]},{"title":"Time-Optimal Construction of Overlays","doi":"https://doi.org/10.1007/s00446-023-00442-4","date_updated":"2023-05-23T12:38:57Z","date_created":"2023-05-22T14:34:34Z","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"},{"last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792","first_name":"Christian"},{"id":"50024","full_name":"Werthmann, Julian","last_name":"Werthmann","first_name":"Julian"}],"year":"2023","citation":{"ieee":"T. Götte, K. Hinnenthal, C. Scheideler, and J. Werthmann, “Time-Optimal Construction of Overlays,” <i>Distributed Computing</i>, 2023, doi: <a href=\"https://doi.org/10.1007/s00446-023-00442-4\">https://doi.org/10.1007/s00446-023-00442-4</a>.","chicago":"Götte, Thorsten, Kristian Hinnenthal, Christian Scheideler, and Julian Werthmann. “Time-Optimal Construction of Overlays.” <i>Distributed Computing</i>, 2023. <a href=\"https://doi.org/10.1007/s00446-023-00442-4\">https://doi.org/10.1007/s00446-023-00442-4</a>.","ama":"Götte T, Hinnenthal K, Scheideler C, Werthmann J. Time-Optimal Construction of Overlays. <i>Distributed Computing</i>. Published online 2023. doi:<a href=\"https://doi.org/10.1007/s00446-023-00442-4\">https://doi.org/10.1007/s00446-023-00442-4</a>","apa":"Götte, T., Hinnenthal, K., Scheideler, C., &#38; Werthmann, J. (2023). Time-Optimal Construction of Overlays. <i>Distributed Computing</i>. <a href=\"https://doi.org/10.1007/s00446-023-00442-4\">https://doi.org/10.1007/s00446-023-00442-4</a>","mla":"Götte, Thorsten, et al. “Time-Optimal Construction of Overlays.” <i>Distributed Computing</i>, 2023, doi:<a href=\"https://doi.org/10.1007/s00446-023-00442-4\">https://doi.org/10.1007/s00446-023-00442-4</a>.","bibtex":"@article{Götte_Hinnenthal_Scheideler_Werthmann_2023, title={Time-Optimal Construction of Overlays}, DOI={<a href=\"https://doi.org/10.1007/s00446-023-00442-4\">https://doi.org/10.1007/s00446-023-00442-4</a>}, journal={Distributed Computing}, author={Götte, Thorsten and Hinnenthal, Kristian and Scheideler, Christian and Werthmann, Julian}, year={2023} }","short":"T. Götte, K. Hinnenthal, C. Scheideler, J. Werthmann, Distributed Computing (2023)."},"language":[{"iso":"eng"}],"_id":"45192","project":[{"_id":"1","name":"SFB 901: SFB 901"},{"_id":"2","name":"SFB 901 - A: SFB 901 - Project Area A"},{"name":"SFB 901 - C: SFB 901 - Project Area C","_id":"4"},{"name":"SFB 901 - C1: SFB 901 - Subproject C1","_id":"13"},{"name":"SFB 901 - A1: SFB 901 - Subproject A1","_id":"5"}],"user_id":"477","status":"public","publication":"Distributed Computing","type":"journal_article"},{"date_created":"2023-07-07T06:21:38Z","publisher":"Heinz Nixdorf Institut, Universität Paderborn","title":"Capabilities and Limitations of Local Strategies in Dynamic Networks","year":"2023","language":[{"iso":"eng"}],"ddc":["004"],"publication":"On-The-Fly Computing -- Individualized IT-services in dynamic markets","file":[{"file_size":543715,"access_level":"open_access","file_name":"A1-Chapter-SFB-Buch-Final.pdf","file_id":"45876","date_updated":"2023-07-07T06:20:43Z","date_created":"2023-07-07T06:20:43Z","creator":"ups","relation":"main_file","content_type":"application/pdf"}],"author":[{"id":"34727","full_name":"Götte, Thorsten","last_name":"Götte","first_name":"Thorsten"},{"first_name":"Till","orcid":"0000-0003-2014-4696","last_name":"Knollmann","id":"39241","full_name":"Knollmann, Till"},{"first_name":"Friedhelm","last_name":"Meyer auf der Heide","id":"15523","full_name":"Meyer auf der Heide, Friedhelm"},{"full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler","first_name":"Christian"},{"first_name":"Julian","full_name":"Werthmann, Julian","id":"50024","last_name":"Werthmann"}],"volume":412,"oa":"1","date_updated":"2023-07-07T06:21:57Z","doi":"10.5281/zenodo.8060372","has_accepted_license":"1","citation":{"ama":"Götte T, Knollmann T, Meyer auf der Heide F, Scheideler C, Werthmann J. Capabilities and Limitations of Local Strategies in Dynamic Networks. In: Haake C-J, Meyer auf der Heide F, Platzner M, Wachsmuth H, Wehrheim H, eds. <i>On-The-Fly Computing -- Individualized IT-Services in Dynamic Markets</i>. Vol 412. Verlagsschriftenreihe des Heinz Nixdorf Instituts. Heinz Nixdorf Institut, Universität Paderborn; 2023:1--20. doi:<a href=\"https://doi.org/10.5281/zenodo.8060372\">10.5281/zenodo.8060372</a>","chicago":"Götte, Thorsten, Till Knollmann, Friedhelm Meyer auf der Heide, Christian Scheideler, and Julian Werthmann. “Capabilities and Limitations of Local Strategies in Dynamic Networks.” In <i>On-The-Fly Computing -- Individualized IT-Services in Dynamic Markets</i>, edited by Claus-Jochen Haake, Friedhelm Meyer auf der Heide, Marco Platzner, Henning Wachsmuth, and Heike Wehrheim, 412:1--20. Verlagsschriftenreihe Des Heinz Nixdorf Instituts. Paderborn: Heinz Nixdorf Institut, Universität Paderborn, 2023. <a href=\"https://doi.org/10.5281/zenodo.8060372\">https://doi.org/10.5281/zenodo.8060372</a>.","ieee":"T. Götte, T. Knollmann, F. Meyer auf der Heide, C. Scheideler, and J. Werthmann, “Capabilities and Limitations of Local Strategies in Dynamic Networks,” in <i>On-The-Fly Computing -- Individualized IT-services in dynamic markets</i>, vol. 412, C.-J. Haake, F. Meyer auf der Heide, M. Platzner, H. Wachsmuth, and H. Wehrheim, Eds. Paderborn: Heinz Nixdorf Institut, Universität Paderborn, 2023, pp. 1--20.","apa":"Götte, T., Knollmann, T., Meyer auf der Heide, F., Scheideler, C., &#38; Werthmann, J. (2023). Capabilities and Limitations of Local Strategies in Dynamic Networks. In C.-J. Haake, F. Meyer auf der Heide, M. Platzner, H. Wachsmuth, &#38; H. Wehrheim (Eds.), <i>On-The-Fly Computing -- Individualized IT-services in dynamic markets</i> (Vol. 412, pp. 1--20). Heinz Nixdorf Institut, Universität Paderborn. <a href=\"https://doi.org/10.5281/zenodo.8060372\">https://doi.org/10.5281/zenodo.8060372</a>","bibtex":"@inbook{Götte_Knollmann_Meyer auf der Heide_Scheideler_Werthmann_2023, place={Paderborn}, series={Verlagsschriftenreihe des Heinz Nixdorf Instituts}, title={Capabilities and Limitations of Local Strategies in Dynamic Networks}, volume={412}, DOI={<a href=\"https://doi.org/10.5281/zenodo.8060372\">10.5281/zenodo.8060372</a>}, booktitle={On-The-Fly Computing -- Individualized IT-services in dynamic markets}, publisher={Heinz Nixdorf Institut, Universität Paderborn}, author={Götte, Thorsten and Knollmann, Till and Meyer auf der Heide, Friedhelm and Scheideler, Christian and Werthmann, Julian}, editor={Haake, Claus-Jochen and Meyer auf der Heide, Friedhelm and Platzner, Marco and Wachsmuth, Henning and Wehrheim, Heike}, year={2023}, pages={1--20}, collection={Verlagsschriftenreihe des Heinz Nixdorf Instituts} }","mla":"Götte, Thorsten, et al. “Capabilities and Limitations of Local Strategies in Dynamic Networks.” <i>On-The-Fly Computing -- Individualized IT-Services in Dynamic Markets</i>, edited by Claus-Jochen Haake et al., vol. 412, Heinz Nixdorf Institut, Universität Paderborn, 2023, pp. 1--20, doi:<a href=\"https://doi.org/10.5281/zenodo.8060372\">10.5281/zenodo.8060372</a>.","short":"T. Götte, T. Knollmann, F. Meyer auf der Heide, C. Scheideler, J. Werthmann, in: C.-J. Haake, F. Meyer auf der Heide, M. Platzner, H. Wachsmuth, H. Wehrheim (Eds.), On-The-Fly Computing -- Individualized IT-Services in Dynamic Markets, Heinz Nixdorf Institut, Universität Paderborn, Paderborn, 2023, pp. 1--20."},"intvolume":"       412","page":"1--20","place":"Paderborn","series_title":"Verlagsschriftenreihe des Heinz Nixdorf Instituts","user_id":"477","department":[{"_id":"7"}],"project":[{"grant_number":"160364472","name":"SFB 901: SFB 901: On-The-Fly Computing - Individualisierte IT-Dienstleistungen in dynamischen Märkten ","_id":"1"},{"_id":"2","name":"SFB 901 - A: SFB 901 - Project Area A"},{"_id":"5","name":"SFB 901 - A1: SFB 901 - Möglichkeiten und Grenzen lokaler Strategien in dynamischen Netzen (Subproject A1)","grant_number":"160364472"}],"_id":"45875","file_date_updated":"2023-07-07T06:20:43Z","type":"book_chapter","status":"public","editor":[{"last_name":"Haake","full_name":"Haake, Claus-Jochen","first_name":"Claus-Jochen"},{"first_name":"Friedhelm","last_name":"Meyer auf der Heide","full_name":"Meyer auf der Heide, Friedhelm"},{"last_name":"Platzner","full_name":"Platzner, Marco","first_name":"Marco"},{"full_name":"Wachsmuth, Henning","last_name":"Wachsmuth","first_name":"Henning"},{"full_name":"Wehrheim, Heike","last_name":"Wehrheim","first_name":"Heike"}]},{"citation":{"apa":"Dou, J., Götte, T., Hillebrandt, H., Scheideler, C., &#38; Werthmann, J. (2023). Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs. <i>Proc. of the 42nd ACM Symposium on Principles of Distributed Computing (PODC ’23)</i>. ACM Symposium on Principles of Distributed Computing (PODC), Orlando, USA.","mla":"Dou, Jinfeng, et al. “Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs.” <i>Proc. of the 42nd ACM Symposium on Principles of Distributed Computing (PODC ’23)</i>, 2023.","short":"J. Dou, T. Götte, H. Hillebrandt, C. Scheideler, J. Werthmann, in: Proc. of the 42nd ACM Symposium on Principles of Distributed Computing (PODC ’23), 2023.","bibtex":"@inproceedings{Dou_Götte_Hillebrandt_Scheideler_Werthmann_2023, title={Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs}, booktitle={Proc. of the 42nd ACM Symposium on Principles of Distributed Computing (PODC ’23)}, author={Dou, Jinfeng and Götte, Thorsten and Hillebrandt, Henning and Scheideler, Christian and Werthmann, Julian}, year={2023} }","ama":"Dou J, Götte T, Hillebrandt H, Scheideler C, Werthmann J. Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs. In: <i>Proc. of the 42nd ACM Symposium on Principles of Distributed Computing (PODC ’23)</i>. ; 2023.","chicago":"Dou, Jinfeng, Thorsten Götte, Henning Hillebrandt, Christian Scheideler, and Julian Werthmann. “Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs.” In <i>Proc. of the 42nd ACM Symposium on Principles of Distributed Computing (PODC ’23)</i>, 2023.","ieee":"J. Dou, T. Götte, H. Hillebrandt, C. Scheideler, and J. Werthmann, “Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs,” presented at the ACM Symposium on Principles of Distributed Computing (PODC), Orlando, USA, 2023."},"year":"2023","author":[{"first_name":"Jinfeng","last_name":"Dou","full_name":"Dou, Jinfeng","id":"92888"},{"id":"34727","full_name":"Götte, Thorsten","last_name":"Götte","first_name":"Thorsten"},{"full_name":"Hillebrandt, Henning","id":"74425","last_name":"Hillebrandt","first_name":"Henning"},{"first_name":"Christian","last_name":"Scheideler","id":"20792","full_name":"Scheideler, Christian"},{"first_name":"Julian","last_name":"Werthmann","full_name":"Werthmann, Julian","id":"50024"}],"date_created":"2023-05-22T14:42:31Z","date_updated":"2025-10-15T12:57:48Z","conference":{"end_date":"2023-06-25","location":"Orlando, USA","name":"ACM Symposium on Principles of Distributed Computing (PODC)","start_date":"2023-06-19"},"title":"Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs","publication":"Proc. of the 42nd ACM Symposium on Principles of Distributed Computing (PODC '23)","type":"conference","status":"public","user_id":"34727","_id":"45193","project":[{"name":"SFB 901 - A: SFB 901 - Project Area A","_id":"2"},{"_id":"5","name":"SFB 901 - A1: SFB 901 - Subproject A1"},{"_id":"1","name":"SFB 901: SFB 901"}],"language":[{"iso":"eng"}]},{"user_id":"15504","department":[{"_id":"79"}],"project":[{"name":"SFB 901: SFB 901","_id":"1"},{"_id":"4","name":"SFB 901 - C: SFB 901 - Project Area C"},{"_id":"13","name":"SFB 901 - C1: SFB 901 - Subproject C1"}],"_id":"33240","language":[{"iso":"eng"}],"type":"conference","publication":"SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022","status":"public","editor":[{"last_name":"Agrawal","full_name":"Agrawal, Kunal","first_name":"Kunal"},{"first_name":"I-Ting Angelina","last_name":"Lee","full_name":"Lee, I-Ting Angelina"}],"author":[{"last_name":"Götte","id":"34727","full_name":"Götte, Thorsten","first_name":"Thorsten"},{"last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792","first_name":"Christian"}],"date_created":"2022-09-01T07:55:00Z","date_updated":"2022-09-01T07:57:53Z","publisher":"ACM","doi":"10.1145/3490148.3538556","title":"Brief Announcement: The (Limited) Power of Multiple Identities: Asynchronous Byzantine Reliable Broadcast with Improved Resilience through Collusion","citation":{"apa":"Götte, T., &#38; Scheideler, C. (2022). Brief Announcement: The (Limited) Power of Multiple Identities: Asynchronous Byzantine Reliable Broadcast with Improved Resilience through Collusion. In K. Agrawal &#38; I.-T. A. Lee (Eds.), <i>SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022</i> (pp. 99–101). ACM. <a href=\"https://doi.org/10.1145/3490148.3538556\">https://doi.org/10.1145/3490148.3538556</a>","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={<a href=\"https://doi.org/10.1145/3490148.3538556\">10.1145/3490148.3538556</a>}, 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} }","mla":"Götte, Thorsten, and Christian Scheideler. “Brief Announcement: The (Limited) Power of Multiple Identities: Asynchronous Byzantine Reliable Broadcast with Improved Resilience through Collusion.” <i>SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022</i>, edited by Kunal Agrawal and I-Ting Angelina Lee, ACM, 2022, pp. 99–101, doi:<a href=\"https://doi.org/10.1145/3490148.3538556\">10.1145/3490148.3538556</a>.","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.","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 <i>SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022</i>, edited by Kunal Agrawal and I-Ting Angelina Lee, 99–101. ACM, 2022. <a href=\"https://doi.org/10.1145/3490148.3538556\">https://doi.org/10.1145/3490148.3538556</a>.","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 <i>SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022</i>, 2022, pp. 99–101, doi: <a href=\"https://doi.org/10.1145/3490148.3538556\">10.1145/3490148.3538556</a>.","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. <i>SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022</i>. ACM; 2022:99–101. doi:<a href=\"https://doi.org/10.1145/3490148.3538556\">10.1145/3490148.3538556</a>"},"page":"99–101","year":"2022"},{"citation":{"ama":"Götte T, Hinnenthal K, Scheideler C, Werthmann J. Time-Optimal Construction of Overlays. In: Censor-Hillel K, ed. <i>Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC ’21)</i>. New York: ACM. doi:<a href=\"https://doi.org/10.1145/3465084.3467932\">10.1145/3465084.3467932</a>","chicago":"Götte, Thorsten, Kristian Hinnenthal, Christian Scheideler, and Julian Werthmann. “Time-Optimal Construction of Overlays.” In <i>Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC ’21)</i>, edited by Keren Censor-Hillel. New York: ACM, n.d. <a href=\"https://doi.org/10.1145/3465084.3467932\">https://doi.org/10.1145/3465084.3467932</a>.","ieee":"T. Götte, K. Hinnenthal, C. Scheideler, and J. Werthmann, “Time-Optimal Construction of Overlays,” in <i>Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC ’21)</i>, Virtual.","apa":"Götte, T., Hinnenthal, K., Scheideler, C., &#38; Werthmann, J. (n.d.). Time-Optimal Construction of Overlays. In K. Censor-Hillel (Ed.), <i>Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC ’21)</i>. New York: ACM. <a href=\"https://doi.org/10.1145/3465084.3467932\">https://doi.org/10.1145/3465084.3467932</a>","bibtex":"@inproceedings{Götte_Hinnenthal_Scheideler_Werthmann, place={New York}, title={Time-Optimal Construction of Overlays}, DOI={<a href=\"https://doi.org/10.1145/3465084.3467932\">10.1145/3465084.3467932</a>}, 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} }","mla":"Götte, Thorsten, et al. “Time-Optimal Construction of Overlays.” <i>Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC ’21)</i>, edited by Keren Censor-Hillel, ACM, doi:<a href=\"https://doi.org/10.1145/3465084.3467932\">10.1145/3465084.3467932</a>.","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."},"place":"New York","has_accepted_license":"1","publication_status":"accepted","doi":"10.1145/3465084.3467932","conference":{"location":"Virtual","end_date":"2021-07-30","start_date":"2021-07-26","name":"ACM Symposium on Principles of Distributed Computing (PODC)"},"author":[{"id":"34727","full_name":"Götte, Thorsten","last_name":"Götte","first_name":"Thorsten"},{"first_name":"Kristian","last_name":"Hinnenthal","full_name":"Hinnenthal, Kristian","id":"32229"},{"first_name":"Christian","id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler"},{"full_name":"Werthmann, Julian","id":"50024","last_name":"Werthmann","first_name":"Julian"}],"date_updated":"2022-01-06T06:55:30Z","status":"public","editor":[{"last_name":"Censor-Hillel","full_name":"Censor-Hillel, Keren","first_name":"Keren"}],"type":"conference","file_date_updated":"2021-06-06T19:12:49Z","department":[{"_id":"34"}],"user_id":"477","_id":"22283","project":[{"_id":"2","name":"SFB 901 - Project Area A"},{"name":"SFB 901 - Subproject A1","_id":"5"},{"_id":"4","name":"SFB 901 - Project Area C"},{"name":"SFB 901 - Subproject C1","_id":"13"},{"name":"SFB 901","_id":"1"}],"year":"2021","title":"Time-Optimal Construction of Overlays","date_created":"2021-06-06T19:10:26Z","publisher":"ACM","file":[{"success":1,"relation":"main_file","content_type":"application/pdf","file_size":590875,"file_name":"Wicked_Fast_Overlay_Construction(1).pdf","access_level":"closed","file_id":"22284","date_updated":"2021-06-06T19:12:49Z","creator":"thgoette","date_created":"2021-06-06T19:12:49Z"}],"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$."}],"publication":"Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC '21)","language":[{"iso":"eng"}],"ddc":["000"]},{"citation":{"ama":"Götte T, Kolb C, Scheideler C, Werthmann J. Beep-And-Sleep: Message and Energy Efficient Set Cover. In: <i>Algorithms for Sensor Systems (ALGOSENSORS ’21)</i>. ; 2021. doi:<a href=\"https://doi.org/10.1007/978-3-030-89240-1_7\">10.1007/978-3-030-89240-1_7</a>","ieee":"T. Götte, C. Kolb, C. Scheideler, and J. Werthmann, “Beep-And-Sleep: Message and Energy Efficient Set Cover,” in <i>Algorithms for Sensor Systems (ALGOSENSORS ’21)</i>, Cham, 2021.","chicago":"Götte, Thorsten, Christina Kolb, Christian Scheideler, and Julian Werthmann. “Beep-And-Sleep: Message and Energy Efficient Set Cover.” In <i>Algorithms for Sensor Systems (ALGOSENSORS ’21)</i>. Cham, 2021. <a href=\"https://doi.org/10.1007/978-3-030-89240-1_7\">https://doi.org/10.1007/978-3-030-89240-1_7</a>.","apa":"Götte, T., Kolb, C., Scheideler, C., &#38; Werthmann, J. (2021). Beep-And-Sleep: Message and Energy Efficient Set Cover. In <i>Algorithms for Sensor Systems (ALGOSENSORS ’21)</i>. ALGOSENSORS 2021, Lisbon, Portgual. <a href=\"https://doi.org/10.1007/978-3-030-89240-1_7\">https://doi.org/10.1007/978-3-030-89240-1_7</a>","short":"T. Götte, C. Kolb, C. Scheideler, J. Werthmann, in: Algorithms for Sensor Systems (ALGOSENSORS ’21), Cham, 2021.","bibtex":"@inbook{Götte_Kolb_Scheideler_Werthmann_2021, place={Cham}, title={Beep-And-Sleep: Message and Energy Efficient Set Cover}, DOI={<a href=\"https://doi.org/10.1007/978-3-030-89240-1_7\">10.1007/978-3-030-89240-1_7</a>}, booktitle={Algorithms for Sensor Systems (ALGOSENSORS ’21)}, author={Götte, Thorsten and Kolb, Christina and Scheideler, Christian and Werthmann, Julian}, year={2021} }","mla":"Götte, Thorsten, et al. “Beep-And-Sleep: Message and Energy Efficient Set Cover.” <i>Algorithms for Sensor Systems (ALGOSENSORS ’21)</i>, 2021, doi:<a href=\"https://doi.org/10.1007/978-3-030-89240-1_7\">10.1007/978-3-030-89240-1_7</a>."},"year":"2021","place":"Cham","publication_identifier":{"issn":["0302-9743","1611-3349"]},"publication_status":"published","conference":{"location":"Lisbon, Portgual","name":"ALGOSENSORS 2021"},"doi":"10.1007/978-3-030-89240-1_7","title":"Beep-And-Sleep: Message and Energy Efficient Set Cover","author":[{"id":"34727","full_name":"Götte, Thorsten","last_name":"Götte","first_name":"Thorsten"},{"full_name":"Kolb, Christina","id":"43647","last_name":"Kolb","first_name":"Christina"},{"first_name":"Christian","id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler"},{"first_name":"Julian","last_name":"Werthmann","full_name":"Werthmann, Julian","id":"50024"}],"date_created":"2021-10-26T12:06:04Z","date_updated":"2022-11-18T10:01:36Z","status":"public","publication":"Algorithms for Sensor Systems (ALGOSENSORS '21)","type":"book_chapter","language":[{"iso":"eng"}],"user_id":"477","_id":"26888","project":[{"name":"SFB 901 - Project Area A","_id":"2"},{"_id":"5","name":"SFB 901 - Subproject A1"},{"name":"SFB 901: SFB 901","_id":"1"}]},{"date_updated":"2022-01-07T15:24:10Z","volume":13046,"author":[{"first_name":"Jannik","last_name":"Castenow","id":"38705","full_name":"Castenow, Jannik"},{"id":"34727","full_name":"Götte, Thorsten","last_name":"Götte","first_name":"Thorsten"},{"first_name":"Till","full_name":"Knollmann, Till","id":"39241","orcid":"0000-0003-2014-4696","last_name":"Knollmann"},{"first_name":"Friedhelm","last_name":"Meyer auf der Heide","id":"15523","full_name":"Meyer auf der Heide, Friedhelm"}],"doi":"10.1007/978-3-030-91081-5_19","conference":{"location":"Online","end_date":"2021-11-20","start_date":"2021-11-17","name":"23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems"},"publication_status":"published","page":"289-304 ","intvolume":"     13046","citation":{"ama":"Castenow J, Götte T, Knollmann T, Meyer auf der Heide F. The Max-Line-Formation Problem – And New Insights for Gathering and Chain-Formation. In: Johnen C, Schiller EM, Schmid S, eds. <i>Proceedings of the 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2021</i>. Vol 13046. LNCS. Springer; 2021:289-304. doi:<a href=\"https://doi.org/10.1007/978-3-030-91081-5_19\">10.1007/978-3-030-91081-5_19</a>","ieee":"J. Castenow, T. Götte, T. Knollmann, and F. Meyer auf der Heide, “The Max-Line-Formation Problem – And New Insights for Gathering and Chain-Formation,” in <i>Proceedings of the 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2021</i>, Online, 2021, vol. 13046, pp. 289–304, doi: <a href=\"https://doi.org/10.1007/978-3-030-91081-5_19\">10.1007/978-3-030-91081-5_19</a>.","chicago":"Castenow, Jannik, Thorsten Götte, Till Knollmann, and Friedhelm Meyer auf der Heide. “The Max-Line-Formation Problem – And New Insights for Gathering and Chain-Formation.” In <i>Proceedings of the 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2021</i>, edited by C. Johnen, E.M. Schiller, and S. Schmid, 13046:289–304. LNCS. Springer, 2021. <a href=\"https://doi.org/10.1007/978-3-030-91081-5_19\">https://doi.org/10.1007/978-3-030-91081-5_19</a>.","apa":"Castenow, J., Götte, T., Knollmann, T., &#38; Meyer auf der Heide, F. (2021). The Max-Line-Formation Problem – And New Insights for Gathering and Chain-Formation. In C. Johnen, E. M. Schiller, &#38; S. Schmid (Eds.), <i>Proceedings of the 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2021</i> (Vol. 13046, pp. 289–304). Springer. <a href=\"https://doi.org/10.1007/978-3-030-91081-5_19\">https://doi.org/10.1007/978-3-030-91081-5_19</a>","short":"J. Castenow, T. Götte, T. Knollmann, F. Meyer auf der Heide, in: C. Johnen, E.M. Schiller, S. Schmid (Eds.), Proceedings of the 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2021, Springer, 2021, pp. 289–304.","bibtex":"@inproceedings{Castenow_Götte_Knollmann_Meyer auf der Heide_2021, series={LNCS}, title={The Max-Line-Formation Problem – And New Insights for Gathering and Chain-Formation}, volume={13046}, DOI={<a href=\"https://doi.org/10.1007/978-3-030-91081-5_19\">10.1007/978-3-030-91081-5_19</a>}, booktitle={Proceedings of the 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2021}, publisher={Springer}, author={Castenow, Jannik and Götte, Thorsten and Knollmann, Till and Meyer auf der Heide, Friedhelm}, editor={Johnen, C. and Schiller, E.M. and Schmid, S.}, year={2021}, pages={289–304}, collection={LNCS} }","mla":"Castenow, Jannik, et al. “The Max-Line-Formation Problem – And New Insights for Gathering and Chain-Formation.” <i>Proceedings of the 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2021</i>, edited by C. Johnen et al., vol. 13046, Springer, 2021, pp. 289–304, doi:<a href=\"https://doi.org/10.1007/978-3-030-91081-5_19\">10.1007/978-3-030-91081-5_19</a>."},"_id":"26986","project":[{"name":"Algorithmen für Schwarmrobotik: Verteiltes Rechnen trifft Dynamische Systeme","_id":"106"}],"department":[{"_id":"63"}],"series_title":"LNCS","user_id":"38705","type":"conference","editor":[{"first_name":"C.","last_name":"Johnen","full_name":"Johnen, C."},{"first_name":"E.M.","last_name":"Schiller","full_name":"Schiller, E.M."},{"full_name":"Schmid, S.","last_name":"Schmid","first_name":"S."}],"status":"public","publisher":"Springer","date_created":"2021-10-28T07:01:30Z","title":"The Max-Line-Formation Problem – And New Insights for Gathering and Chain-Formation","year":"2021","external_id":{"arxiv":["2109.11856"]},"language":[{"iso":"eng"}],"publication":"Proceedings of the 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2021"},{"file":[{"content_type":"application/pdf","success":1,"relation":"main_file","date_updated":"2019-01-26T16:09:08Z","creator":"thgoette","date_created":"2019-01-26T16:09:08Z","file_size":638020,"file_id":"7007","file_name":"Always_be_Two_Steps_Ahead_of_Your_Enemy.pdf","access_level":"closed"}],"abstract":[{"text":"We investigate the maintenance of overlay networks under massive churn, i.e.\r\nnodes joining and leaving the network. We assume an adversary that may churn a\r\nconstant fraction $\\alpha n$ of nodes over the course of $\\mathcal{O}(\\log n)$\r\nrounds. In particular, the adversary has an almost up-to-date information of\r\nthe network topology as it can observe an only slightly outdated topology that\r\nis at least $2$ rounds old. Other than that, we only have the provably minimal\r\nrestriction that new nodes can only join the network via nodes that have taken\r\npart in the network for at least one round.\r\n  Our contributions are as follows: First, we show that it is impossible to\r\nmaintain a connected topology if adversary has up-to-date information about the\r\nnodes' connections. Further, we show that our restriction concerning the join\r\nis also necessary. As our main result present an algorithm that constructs a\r\nnew overlay- completely independent of all previous overlays - every $2$\r\nrounds. Furthermore, each node sends and receives only $\\mathcal{O}(\\log^3 n)$\r\nmessages each round. As part of our solution we propose the Linearized DeBruijn\r\nSwarm (LDS), a highly churn resistant overlay, which will be maintained by the\r\nalgorithm. However, our approaches can be transferred to a variety of classical\r\nP2P Topologies where nodes are mapped into the $[0,1)$-interval.","lang":"eng"}],"publication":"Proceedings of the 2019 IEEE 33rd International Parallel  and Distributed Processing Symposium (IPDPS '19)","language":[{"iso":"eng"}],"ddc":["000"],"year":"2019","title":"Always be Two Steps Ahead of Your Enemy - Maintaining a Routable Overlay under Massive Churn with an Almost Up-to-date Adversary","date_created":"2019-01-24T18:53:11Z","publisher":"IEEE","status":"public","type":"conference","file_date_updated":"2019-01-26T16:09:08Z","user_id":"34727","department":[{"_id":"79"}],"project":[{"_id":"1","name":"SFB 901"},{"_id":"4","name":"SFB 901 - Project Area C"},{"_id":"13","name":"SFB 901 - Subproject C1"}],"_id":"6976","citation":{"mla":"Götte, Thorsten, et al. “Always Be Two Steps Ahead of Your Enemy - Maintaining a Routable Overlay under Massive Churn with an Almost Up-to-Date Adversary.” <i>Proceedings of the 2019 IEEE 33rd International Parallel  and Distributed Processing Symposium (IPDPS ’19)</i>, IEEE.","bibtex":"@inproceedings{Götte_Vijayalakshmi_Scheideler, title={Always be Two Steps Ahead of Your Enemy - Maintaining a Routable Overlay under Massive Churn with an Almost Up-to-date Adversary}, booktitle={Proceedings of the 2019 IEEE 33rd International Parallel  and Distributed Processing Symposium (IPDPS ’19)}, publisher={IEEE}, author={Götte, Thorsten and Vijayalakshmi, Vipin Ravindran and Scheideler, Christian} }","short":"T. Götte, V.R. Vijayalakshmi, C. Scheideler, in: Proceedings of the 2019 IEEE 33rd International Parallel  and Distributed Processing Symposium (IPDPS ’19), IEEE, n.d.","apa":"Götte, T., Vijayalakshmi, V. R., &#38; Scheideler, C. (n.d.). Always be Two Steps Ahead of Your Enemy - Maintaining a Routable Overlay under Massive Churn with an Almost Up-to-date Adversary. In <i>Proceedings of the 2019 IEEE 33rd International Parallel  and Distributed Processing Symposium (IPDPS ’19)</i>. Rio de Janeiro, Brazil: IEEE.","ieee":"T. Götte, V. R. Vijayalakshmi, and C. Scheideler, “Always be Two Steps Ahead of Your Enemy - Maintaining a Routable Overlay under Massive Churn with an Almost Up-to-date Adversary,” in <i>Proceedings of the 2019 IEEE 33rd International Parallel  and Distributed Processing Symposium (IPDPS ’19)</i>, Rio de Janeiro, Brazil.","chicago":"Götte, Thorsten, Vipin Ravindran Vijayalakshmi, and Christian Scheideler. “Always Be Two Steps Ahead of Your Enemy - Maintaining a Routable Overlay under Massive Churn with an Almost Up-to-Date Adversary.” In <i>Proceedings of the 2019 IEEE 33rd International Parallel  and Distributed Processing Symposium (IPDPS ’19)</i>. IEEE, n.d.","ama":"Götte T, Vijayalakshmi VR, Scheideler C. Always be Two Steps Ahead of Your Enemy - Maintaining a Routable Overlay under Massive Churn with an Almost Up-to-date Adversary. In: <i>Proceedings of the 2019 IEEE 33rd International Parallel  and Distributed Processing Symposium (IPDPS ’19)</i>. IEEE."},"publication_status":"accepted","has_accepted_license":"1","conference":{"start_date":"20.05.19","name":"2019 IEEE 33rd International Parallel  and Distributed Processing Symposium (IPDPS '19)","location":"Rio de Janeiro, Brazil","end_date":"24.05.19"},"author":[{"id":"34727","full_name":"Götte, Thorsten","last_name":"Götte","first_name":"Thorsten"},{"first_name":"Vipin Ravindran","full_name":"Vijayalakshmi, Vipin Ravindran","last_name":"Vijayalakshmi"},{"id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler","first_name":"Christian"}],"date_updated":"2022-01-06T07:03:25Z"},{"language":[{"iso":"eng"}],"user_id":"32229","_id":"12944","status":"public","type":"conference","publication":"Structural Information and Communication Complexity","doi":"10.1007/978-3-030-24922-9_18","title":"Faster Construction of Overlay Networks","date_created":"2019-08-19T07:18:57Z","author":[{"first_name":"Thorsten","last_name":"Götte","full_name":"Götte, Thorsten","id":"34727"},{"first_name":"Kristian","id":"32229","full_name":"Hinnenthal, Kristian","last_name":"Hinnenthal"},{"last_name":"Scheideler","full_name":"Scheideler, Christian","id":"20792","first_name":"Christian"}],"date_updated":"2022-01-06T06:51:27Z","citation":{"bibtex":"@inproceedings{Götte_Hinnenthal_Scheideler_2019, place={Cham}, title={Faster Construction of Overlay Networks}, DOI={<a href=\"https://doi.org/10.1007/978-3-030-24922-9_18\">10.1007/978-3-030-24922-9_18</a>}, booktitle={Structural Information and Communication Complexity}, author={Götte, Thorsten and Hinnenthal, Kristian and Scheideler, Christian}, year={2019} }","short":"T. Götte, K. Hinnenthal, C. Scheideler, in: Structural Information and Communication Complexity, Cham, 2019.","mla":"Götte, Thorsten, et al. “Faster Construction of Overlay Networks.” <i>Structural Information and Communication Complexity</i>, 2019, doi:<a href=\"https://doi.org/10.1007/978-3-030-24922-9_18\">10.1007/978-3-030-24922-9_18</a>.","apa":"Götte, T., Hinnenthal, K., &#38; Scheideler, C. (2019). Faster Construction of Overlay Networks. In <i>Structural Information and Communication Complexity</i>. Cham. <a href=\"https://doi.org/10.1007/978-3-030-24922-9_18\">https://doi.org/10.1007/978-3-030-24922-9_18</a>","ieee":"T. Götte, K. Hinnenthal, and C. Scheideler, “Faster Construction of Overlay Networks,” in <i>Structural Information and Communication Complexity</i>, 2019.","chicago":"Götte, Thorsten, Kristian Hinnenthal, and Christian Scheideler. “Faster Construction of Overlay Networks.” In <i>Structural Information and Communication Complexity</i>. Cham, 2019. <a href=\"https://doi.org/10.1007/978-3-030-24922-9_18\">https://doi.org/10.1007/978-3-030-24922-9_18</a>.","ama":"Götte T, Hinnenthal K, Scheideler C. Faster Construction of Overlay Networks. In: <i>Structural Information and Communication Complexity</i>. Cham; 2019. doi:<a href=\"https://doi.org/10.1007/978-3-030-24922-9_18\">10.1007/978-3-030-24922-9_18</a>"},"year":"2019","place":"Cham","publication_status":"published"},{"title":"A Loosely Self-stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory","publisher":"Springer, Cham","date_created":"2019-09-10T12:48:33Z","year":"2019","ddc":["000"],"language":[{"iso":"eng"}],"external_id":{"arxiv":["1909.04544"]},"abstract":[{"lang":"eng","text":"We consider congestion control in peer-to-peer distributed systems. \r\nThe problem can be reduced to the following scenario: Consider a set $V$ of $n$ peers (called \\emph{clients} in this paper) that want to send messages to a fixed common peer (called \\emph{server} in this paper).\r\nWe assume that each client $v \\in V$ sends a message with probability $p(v) \\in [0,1)$ and the server has a capacity of $\\sigma \\in \\mathbb{N}$, i.e., it can recieve at most $\\sigma$ messages per round and excess messages are dropped.\r\nThe server can modify these probabilities when clients send messages.\r\nIdeally, we wish to converge to a state with $\\sum p(v) = \\sigma$ and $p(v) = p(w)$ for all $v,w \\in V$.\t\r\n\r\nWe propose a \\emph{loosely} self-stabilizing protocol with a slightly relaxed legitimate state.   \r\nOur protocol lets the system converge from \\emph{any} initial state to a state where $\\sum p(v) \\in \\left[\\sigma \\pm \\epsilon\\right]$ and $|p(v)-p(w)| \\in O(\\frac{1}{n})$. \r\nThis property is then maintained for $\\Omega(n^{\\mathfrak{c}})$ rounds in expectation.\r\nIn particular, the initial client probabilities and server variables are not necessarily well-defined, i.e., they may have arbitrary values.\r\n\r\nOur protocol uses only $O(W + \\log n)$ bits of memory where $W$ is length of node identifiers, making it very lightweight.\r\nFinally we state a lower bound on the convergence time an see that our protocol performs asymptotically optimal (up to some polylogarithmic factor).\r\n"}],"file":[{"date_updated":"2019-09-11T11:20:16Z","creator":"mfeldma2","date_created":"2019-09-11T11:20:16Z","file_size":428908,"access_level":"closed","file_id":"13188","file_name":"main.pdf","content_type":"application/pdf","success":1,"relation":"main_file"}],"publication":"Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)","doi":"https://doi.org/10.1007/978-3-030-34992-9_13","date_updated":"2022-01-06T06:51:30Z","author":[{"first_name":"Michael","last_name":"Feldmann","full_name":"Feldmann, Michael","id":"23538"},{"first_name":"Thorsten","last_name":"Götte","id":"34727","full_name":"Götte, Thorsten"},{"last_name":"Scheideler","id":"20792","full_name":"Scheideler, Christian","first_name":"Christian"}],"page":"149-164","citation":{"short":"M. Feldmann, T. Götte, C. Scheideler, in: Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Springer, Cham, 2019, pp. 149–164.","bibtex":"@inproceedings{Feldmann_Götte_Scheideler_2019, series={Lecture Notes in Computer Science}, title={A Loosely Self-stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory}, DOI={<a href=\"https://doi.org/10.1007/978-3-030-34992-9_13\">https://doi.org/10.1007/978-3-030-34992-9_13</a>}, booktitle={Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)}, publisher={Springer, Cham}, author={Feldmann, Michael and Götte, Thorsten and Scheideler, Christian}, year={2019}, pages={149–164}, collection={Lecture Notes in Computer Science} }","mla":"Feldmann, Michael, et al. “A Loosely Self-Stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory.” <i>Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>, Springer, Cham, 2019, pp. 149–64, doi:<a href=\"https://doi.org/10.1007/978-3-030-34992-9_13\">https://doi.org/10.1007/978-3-030-34992-9_13</a>.","apa":"Feldmann, M., Götte, T., &#38; Scheideler, C. (2019). A Loosely Self-stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory. In <i>Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i> (pp. 149–164). Springer, Cham. <a href=\"https://doi.org/10.1007/978-3-030-34992-9_13\">https://doi.org/10.1007/978-3-030-34992-9_13</a>","ieee":"M. Feldmann, T. Götte, and C. Scheideler, “A Loosely Self-stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory,” in <i>Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>, 2019, pp. 149–164.","chicago":"Feldmann, Michael, Thorsten Götte, and Christian Scheideler. “A Loosely Self-Stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory.” In <i>Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>, 149–64. Lecture Notes in Computer Science. Springer, Cham, 2019. <a href=\"https://doi.org/10.1007/978-3-030-34992-9_13\">https://doi.org/10.1007/978-3-030-34992-9_13</a>.","ama":"Feldmann M, Götte T, Scheideler C. A Loosely Self-stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory. In: <i>Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>. Lecture Notes in Computer Science. Springer, Cham; 2019:149-164. doi:<a href=\"https://doi.org/10.1007/978-3-030-34992-9_13\">https://doi.org/10.1007/978-3-030-34992-9_13</a>"},"has_accepted_license":"1","file_date_updated":"2019-09-11T11:20:16Z","_id":"13182","project":[{"name":"SFB 901 - Project Area A","_id":"2"},{"name":"SFB 901 - Subproject A1","_id":"5"},{"name":"SFB 901","_id":"1"}],"department":[{"_id":"79"}],"series_title":"Lecture Notes in Computer Science","user_id":"23538","status":"public","type":"conference"},{"file_date_updated":"2018-10-31T15:59:26Z","department":[{"_id":"79"}],"series_title":"Lecture Notes in Computer Science","user_id":"477","_id":"5222","project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Project Area A","_id":"2"},{"_id":"5","name":"SFB 901 - Subproject A1"}],"status":"public","type":"conference","conference":{"name":" 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)","location":"Tokyo, Japan"},"volume":11201,"author":[{"last_name":"Götte","id":"34727","full_name":"Götte, Thorsten","first_name":"Thorsten"},{"first_name":"Christian","id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler"},{"last_name":"Setzer","full_name":"Setzer, Alexander","id":"11108","first_name":"Alexander"}],"date_updated":"2022-01-06T07:01:47Z","intvolume":"     11201","page":"50-64","citation":{"apa":"Götte, T., Scheideler, C., &#38; Setzer, A. (2018). On Underlay-Aware Self-Stabilizing Overlay Networks. In <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i> (Vol. 11201, pp. 50–64). Tokyo, Japan: Springer.","mla":"Götte, Thorsten, et al. “On Underlay-Aware Self-Stabilizing Overlay Networks.” <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>, vol. 11201, Springer, 2018, pp. 50–64.","bibtex":"@inproceedings{Götte_Scheideler_Setzer_2018, series={Lecture Notes in Computer Science}, title={On Underlay-Aware Self-Stabilizing Overlay Networks}, volume={11201}, booktitle={Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)}, publisher={Springer}, author={Götte, Thorsten and Scheideler, Christian and Setzer, Alexander}, year={2018}, pages={50–64}, collection={Lecture Notes in Computer Science} }","short":"T. Götte, C. Scheideler, A. Setzer, in: Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018), Springer, 2018, pp. 50–64.","ama":"Götte T, Scheideler C, Setzer A. On Underlay-Aware Self-Stabilizing Overlay Networks. In: <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>. Vol 11201. Lecture Notes in Computer Science. Springer; 2018:50-64.","chicago":"Götte, Thorsten, Christian Scheideler, and Alexander Setzer. “On Underlay-Aware Self-Stabilizing Overlay Networks.” In <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>, 11201:50–64. Lecture Notes in Computer Science. Springer, 2018.","ieee":"T. Götte, C. Scheideler, and A. Setzer, “On Underlay-Aware Self-Stabilizing Overlay Networks,” in <i>Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)</i>, Tokyo, Japan, 2018, vol. 11201, pp. 50–64."},"has_accepted_license":"1","language":[{"iso":"eng"}],"ddc":["040"],"file":[{"relation":"main_file","success":1,"content_type":"application/pdf","access_level":"closed","file_name":"sss18_camera.pdf","file_id":"5224","file_size":367812,"date_created":"2018-10-31T15:59:26Z","creator":"thgoette","date_updated":"2018-10-31T15:59:26Z"}],"abstract":[{"lang":"eng","text":"We present a self-stabilizing protocol for an overlay network that constructs the Minimum Spanning Tree (MST) for an underlay that is modeled by a weighted tree. The weight of an overlay edge between two nodes is the weighted length of their shortest path in the tree. We rigorously prove that our protocol works correctly under asynchronous and non-FIFO message delivery. Further, the protocol stabilizes after O(N^2) asynchronous rounds where N is the number of nodes in the overlay. "}],"publication":"Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)","title":"On Underlay-Aware Self-Stabilizing Overlay Networks","date_created":"2018-10-31T15:44:30Z","publisher":"Springer","year":"2018"},{"status":"public","type":"mastersthesis","language":[{"iso":"eng"}],"user_id":"477","department":[{"_id":"79"}],"project":[{"name":"SFB 901","_id":"1"},{"name":"SFB 901 - Subprojekt A1","_id":"5"},{"name":"SFB 901 - Project Area A","_id":"2"}],"_id":"701","citation":{"short":"T. Götte, Self-Stabilizing Spanners for Tree Metrics, Universität Paderborn, 2017.","bibtex":"@book{Götte_2017, title={Self-Stabilizing Spanners for Tree Metrics}, publisher={Universität Paderborn}, author={Götte, Thorsten}, year={2017} }","mla":"Götte, Thorsten. <i>Self-Stabilizing Spanners for Tree Metrics</i>. Universität Paderborn, 2017.","apa":"Götte, T. (2017). <i>Self-Stabilizing Spanners for Tree Metrics</i>. Universität Paderborn.","ama":"Götte T. <i>Self-Stabilizing Spanners for Tree Metrics</i>. Universität Paderborn; 2017.","chicago":"Götte, Thorsten. <i>Self-Stabilizing Spanners for Tree Metrics</i>. Universität Paderborn, 2017.","ieee":"T. Götte, <i>Self-Stabilizing Spanners for Tree Metrics</i>. Universität Paderborn, 2017."},"year":"2017","title":"Self-Stabilizing Spanners for Tree Metrics","author":[{"last_name":"Götte","full_name":"Götte, Thorsten","id":"34727","first_name":"Thorsten"}],"date_created":"2017-11-14T09:32:39Z","supervisor":[{"last_name":"Scheideler","id":"20792","full_name":"Scheideler, Christian","first_name":"Christian"}],"publisher":"Universität Paderborn","date_updated":"2022-01-06T07:03:26Z"},{"type":"bachelorsthesis","status":"public","user_id":"477","department":[{"_id":"79"}],"project":[{"_id":"1","name":"SFB 901"},{"_id":"2","name":"SFB 901 - Project Area A"},{"_id":"5","name":"SFB 901 - Subproject A1"}],"_id":"18003","language":[{"iso":"eng"}],"citation":{"bibtex":"@book{Götte_2015, title={Covering and Bridging im selbstorganisierenden Partikelsystem Amoebabot}, publisher={Universität Paderborn}, author={Götte, Thorsten}, year={2015} }","short":"T. Götte, Covering and Bridging Im Selbstorganisierenden Partikelsystem Amoebabot, Universität Paderborn, 2015.","mla":"Götte, Thorsten. <i>Covering and Bridging Im Selbstorganisierenden Partikelsystem Amoebabot</i>. Universität Paderborn, 2015.","apa":"Götte, T. (2015). <i>Covering and Bridging im selbstorganisierenden Partikelsystem Amoebabot</i>. Universität Paderborn.","chicago":"Götte, Thorsten. <i>Covering and Bridging Im Selbstorganisierenden Partikelsystem Amoebabot</i>. Universität Paderborn, 2015.","ieee":"T. Götte, <i>Covering and Bridging im selbstorganisierenden Partikelsystem Amoebabot</i>. Universität Paderborn, 2015.","ama":"Götte T. <i>Covering and Bridging Im Selbstorganisierenden Partikelsystem Amoebabot</i>. Universität Paderborn; 2015."},"year":"2015","supervisor":[{"last_name":"Scheideler","id":"20792","full_name":"Scheideler, Christian","first_name":"Christian"}],"author":[{"id":"34727","full_name":"Götte, Thorsten","last_name":"Götte","first_name":"Thorsten"}],"date_created":"2020-08-17T08:18:04Z","publisher":"Universität Paderborn","date_updated":"2022-01-06T06:53:25Z","title":"Covering and Bridging im selbstorganisierenden Partikelsystem Amoebabot"}]