Tomasz Jurdzin´ski Stefan Schmid (Eds.) Structural Information 0 1 8 and Communication 2 1 S C Complexity N L 28th International Colloquium, SIROCCO 2021 Wrocław, Poland, June 28 – July 1, 2021 Proceedings Lecture Notes in Computer Science 12810 Founding Editors Gerhard Goos Karlsruhe Institute of Technology, Karlsruhe, Germany Juris Hartmanis Cornell University, Ithaca, NY, USA Editorial Board Members Elisa Bertino Purdue University, West Lafayette, IN, USA Wen Gao Peking University, Beijing, China Bernhard Steffen TU Dortmund University, Dortmund, Germany Gerhard Woeginger RWTH Aachen, Aachen, Germany Moti Yung Columbia University, New York, NY, USA More information about this subseries at http://www.springer.com/series/7407 ń Tomasz Jurdzi ski Stefan Schmid (Eds.) (cid:129) Structural Information and Communication Complexity 28th International Colloquium, SIROCCO 2021 ł – Wroc aw, Poland, June 28 July 1, 2021 Proceedings 123 Editors Tomasz Jurdziński StefanSchmid Institute of Computer Science University of Vienna University of Wrocław Vienna,Austria Wroclaw,Poland ISSN 0302-9743 ISSN 1611-3349 (electronic) Lecture Notesin Computer Science ISBN 978-3-030-79526-9 ISBN978-3-030-79527-6 (eBook) https://doi.org/10.1007/978-3-030-79527-6 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ©SpringerNatureSwitzerlandAG2021 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartofthe material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodologynow knownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbookare believedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsortheeditors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissionsthatmayhavebeenmade.Thepublisherremainsneutralwithregardtojurisdictionalclaimsin publishedmapsandinstitutionalaffiliations. ThisSpringerimprintispublishedbytheregisteredcompanySpringerNatureSwitzerlandAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Preface The papers in this volume were presented at the 28th International Colloquium on StructuralInformationandCommunicationComplexity(SIROCCO2021), whichwas plannedtobeheldduringJune28–July1,2021,inWrocław,Poland.However,dueto the COVID-19 pandemic, the conference took place online, as in the previous year. SIROCCO is devoted to the study of the interplay between structural knowledge, communication, and computing in decentralized systems of multiple communicating entities. Special emphasis is given to innovative approaches leading to better under- standing of the relationship between computing and communication. Thisyear,forthefirsttime,wemovedthesubmissiondeadlinesignificantlyearlier, to4December,2020,(usuallythedeadline isaround March),while keeping theusual conferencedate.Wearehappythatbecauseof,ordespite,thischangewecouldattract a large number of submissions compared to previous years. In total we received 48 submissions, from which we accepted 20, i.e., 42%. This volume also includes abstracts of the keynote presentations and one invited paper from a keynote speaker. The paper “Superfast Coloring in CONGEST via Efficient Color Sampling” by Magnús M. Halldórsson and Alexandre Nolin received the Best Paper Award, and “New Approximation Algorithms for the Heterogeneous Weighted Delivery Problem” by Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti, and Mirko Rossi won the Best Student Paper Award. WewouldliketothanktheauthorswhosubmittedtheirworktoSIROCCOthisyear and the Program Committee members and subreviewers for their valuable and insightful reviews and comments. We would also like to thank the keynote speakers, RotemOshman(TelAvivUniversity,Israel),DanAlistarh(IST,Austria),andKenneth Cheung (NASA, USA), for their excellent talks, and Friedhelm Meyer auf der Heide for his featured talk as the recipient of the 2021 SIROCCO Prize for Innovation in Distributed Computing. The SIROCCO Steering Committee, chaired by Magnús M. Halldórsson, provided help and guidance throughout the process. The EasyChair systemwasusedtohandlethesubmissionofpapersandtomanagethereviewprocess. Without all of these people it would not have been possible to come up with these proceedings and the great conference program. June 2021 Tomasz Jurdziński Stefan Schmid Laudatio 2021 SIROCCO Prize for Innovation in Distributed Computing It is a pleasure to award the 2021 SIROCCO Prize for Innovation in Distributed Computing to Friedhelm Meyer auf der Heide. Friedhelm has been an active con- tributortothefieldofDistributedComputingsinceitsverybeginning,withpioneering contributionstoonlineschedulingproblems,loadbalancing,distributeddatastructures, hashing, network routing, mobile facility location, and distributed data streams. Not only has he produced excellent research on distributed computing but he has also inspired and mentored several young researchers, some of whom are now well established scientists in this field. His numerous research contributions include seven articles in SIROCCO and a keynote lecture. The prize is awarded for his contributions to continuous strategies for swarms of mobile robots. The decentralized coordination of large teams of mobile robots has been a key research theme is this community, but primarily with the simplifying assumption that robots act only at discrete times. This discrete time model and its variations have been canonical in the research on distributed mobile robotics. Fried- helm advocated the unorthodox model of continuous protocols [8] where robots observe their surroundings and execute the protocol continuously while they are moving. Such a model requires a completely different set of tools for analyzing robot protocols and proving their correctness and efficiency. This model was first presented in the SIROCCO 2010 paper [1], which considers continuous strategies for line for- mation by mobile robots with limited vision. Subsequent papers addressed the fun- damental problem of gathering and its other variants [4, 6, 7] in the same model, thus establishing the utility of this new model. Another important contribution of Friedhelm is the introduction of new techniques for analyzing well-known algorithms for mobile robots which, among other results, providedanasymptoticallyoptimaltimeboundfortheclassicalconvergencealgorithm [3] and a tight bound for the first known gathering algorithm in the limited visibility model [2]. Yet another novel contribution of Friedhelm is the consideration of energy-efficientstrategiesformobilerobotformationproblemsinthecontinuousplane [5]. The model proposed and studied in detail by Friedhelm and his coauthors has two keyfeatures:limitedvisibilityofrobotsandcontinuousmotion, whichbringsit closer to the research performed by the robotics community as well as control theory researchers, thus bridging the gap between three different communities of researchers who work on mobile robots. With his coauthors, Friedhelm is already extending his work to the three dimensional case, presenting the first gathering algorithm for robots moving continuously in the 3D space in an article [9] that received the Best Student viii Laudatio Paper Award at SIROCCO 2020. We believe Friedhelm’s contributions will continue to inspire young researchers to work in this emerging area of distributed computing. The 2021 Award committee1 Keren Censor-Hillel Technion, Israel Shantanu Das Aix-Marseille Université, France Michele Flammini Gran Sasso Science Institute, Italy Magnús M. Halldórsson (Chair) Reykjavik University, Iceland Zvi Lotker Ben Gurion University, Israel Boaz Patt-Shamir Tel Aviv University, Israel Sébastien Tixeuil Sorbonne Université, France Selected Publications Related to Friedhelm Meyer auf der Heide’s Contribution: 1. B. Degener, B. Kempkes, P. Kling, F. Meyer auf der Heide, A Continuous, Local Strategy for Constructing a Short Chain of Mobile Robots. Proc. SIROCCO 2010: 168–182. 2. B. Degener, B. Kempkes, T. Langner, F. Meyer auf der Heide, P. Pietrzyk, R. Wattenhofer, A tight runtime bound for synchronous gathering of autonomous robots with limited visibility. Proc. SPAA 2011: 139–148. 3. A. Cord-Landwehr, B. Degener, M. Fischer, M. Hüllmann, B. Kempkes, A. Klaas, P.Kling,S.Kurras,M.Märtens,F.MeyeraufderHeide,C.Raupach,K.Swierkot, D. Warner, C. Weddemann, D. Wonisch, A New Approach for Analyzing Con- vergence Algorithms for Mobile Robots. Proc. ICAL P(2) 2011: 650–661. 4. B. Kempkes, P. Kling, F. Meyer auf der Heide, Optimal and Competitive runtime bounds for continuous, local gathering ofmobilerobots.Proc.SPAA 2012: 18–26. 5. P. Brandes, B. Degener, B. Kempkes, F. Meyer auf der Heide, Energy-efficient Strategies for Building Short Chains of Mobile Robots Locally. Theoretical Com- puter Science, 509: 97–112 (2013). 6.B.Degener,B.Kempkes,P.Kling,F.MeyeraufderHeide,LinearandCompetitive Strategies for Continuous Robot Formation Problems. ACM Transactions on Par- allel Computing, 2(1): 2:1–2:18 (2015). 7. S. Li, C. Markarian, F. Meyer auf der Heide, P. Podlipyan, A Continuous Strategy for Collisionless Gathering. Proc. ALGOSENSORS 2017: 182–197. 8. P. Kling, F. Meyer auf der Heide, Continuous Protocols for Swarm Robotics. Distributed Computing by Mobile Entities, Current Research in Moving and Computing, 317–334 (2019). 9.M.Braun,J.Castenow,F.MeyeraufderHeide,LocalGatheringofMobileRobots in Three Dimensions. Proc. SIROCCO 2020: 63–79. 1Wewishtothankthenominatorforthenominationandforcontributingtothistext. Organization Program Committee Chairs Tomasz Jurdziński University of Wrocław, Poland Stefan Schmid University of Vienna, Austria Program Committee Ittai Abraham VMware Research, Israel Petra Berenbrink University of Hamburg, Germany Marcin Bieńkowski University of Wrocław, Poland Sebastian Brandt ETH Zurich, Switzerland Shantanu Das Aix-Marseille University, France Sándor Fekete TU Braunschweig, Germany Antonio Fernandez Anta IMDEA Networks Institute, Spain Magnús M. Halldórsson Reykjavik University, Iceland Taisuke Izumi Osaka University, Japan Tomasz Jurdzinski University of Wrocław, Poland Christoph Lenzen MPI for Informatics, Germany Toshimitsu Masuzawa Osaka University, Japan Friedhelm Meyer Auf der Heinz Nixdorf Institute and University of Paderborn, Heide Germany Stefan Neumann University of Vienna, Austria Rotem Oshman Tel Aviv University, Israel Boaz Patt-Shamir Tel Aviv University, Israel Yvonne-Anne Pignolet DFINITY, Switzerland Maria Potop-Butucaru Sorbonne Université and LIP6, France Andrea Richa Arizona State University, USA Peter Robinson City University of Hong Kong, Hong Kong Christian Scheideler University of Paderborn, Germany Stefan Schmid University of Vienna, Austria Sebastien Tixeuil Universite Pierre et Marie Curie, France Jara Uitto Aalto University, Finland Przemysław Uznański University of Wrocław, Poland André van Renssen The University of Sydney, Australia Steering Committee Keren Censor-Hillel Technion, Israel Michele Flammini Gran Sasso Science Institute, Italy Pierre Fraigniaud Université de Paris and CNRS, France x Organization Magnús M. Halldórsson Reykjavik University, Iceland (Chair) Zvi Lotker Ben-Gurion University, Israel Andrea Richa Arizona State University, USA Christian Scheideler Paderborn University, Germany Boaz Patt-Shamir Tel Aviv University, Israel Organizing Committee Marcin Bieńkowski University of Wrocław, Poland Adam Gańczorz University of Wrocław, Poland Paweł Garncarek University of Wrocław, Poland Tomasz Jurdziński University of Wrocław, Poland Artur Kraska University of Wrocław, Poland Aleksander Łukasiewicz University of Wrocław, Poland Przemysław Uznański University of Wrocław, Poland Additional Reviewers Almethen, Abdullah Harbig, Jonas Altisen, Karine Hinnenthal, Kristian Brankovic, Milutin Keldenich, Phillip Bu, Gewu Knollmann, Till Bund, Johannes Kraska, Artur Böhm, Martin Labourel, Arnaud Cambus, Mélanie Maack, Marten Castenow, Jannik Maus, Yannic Chalopin, Jérémie Miller, Avery Connor, Matthew Molla, Anisur Rahaman Daymude, Joshua Navarra, Alfredo Dereniowski, Dariusz Ost, Wolfgang Di Luna, Giuseppe Antonio Padalkin, Andreas Dobrev, Stefan Portmann, Julian Dong, Rongcheng Sauerwald, Thomas Eades, Patrick Saulpic, David Feldmann, Michael Sha, Yuan Fischer, Orr Skretas, George Függer, Matthias Srinivas, Shreyas Götte, Thorsten Theofilatos, Michail Hanckowiak, Michal Wiederhake, Ben