DISS. ETH NO. 22941 Anonymous Distributed Computing: Computability, Randomization, and Checkability A thesis submitted to attain the degree of DOCTOR OF SCIENCES of ETH ZURICH (Dr. sc. ETH Zurich) presented by JOCHEN SEIDEL Dipl.-Inform.,KarlsruheInstituteofTechnology,Germany born on 18.5.1984 citizen of Germany accepted on the recommendation of Prof. Dr. Roger Wattenhofer, examiner Prof. Dr. Yuval Emek, co-examiner Prof. Dr. Jukka Suomela, co-examiner 2015 Abstract Thisdissertationstudiesvariousaspectsofcomputinginanonymousnet- works,wherenodesarenotequippedwithuniqueidentifiers. Nodesinthe network exchange messages and each node computes some local output; the global output of the network is the combination of all local outputs. We focus mainly on randomized algorithms, beginning with the question “What can be computed in an anonymous network?”. Two classes of problems solvable in anonymous networks are defined, depending on whether nodes are allowed to revoke their outputs or not. Weintroduceandstudytheconceptofadistributedoracle,whichinyields ahierarchyofhardandcompleteproblemsfortheclasses. Severalclassic and/or characteristic problems in distributed computing are classified in terms of computability and hardness. Accesstorandombitsarguablyhasahugeimpactonthecomputabil- ity in anonymous networks. In an effort to exactly characterize this im- pact, we prove that every problem that can be solved (and verified) by arandomized anonymousalgorithmcanalsobesolvedbyadeterministic anonymous algorithm provided that the latter is equipped with a 2-hop coloring of the input graph. It is natural to ask how many random bits are required to solve any such problem. We find that the answer depends on the desired runtime of the algorithm. More precisely, we devise a randomized 2-hop coloring scheme that allows to trade an increase in runtime for a decrease in the random bit complexity. A lower bound we show yields that the trade- off achieved by our scheme is asymptotically optimal for any reasonable runtime,i.e.,reducingtheruntimemustleadtoanincreaseintherandom bit complexity. Lastly,westudylocalcheckabilityofnetworkpropertieslikes-treach- ability, or whether the network is acyclic or contains a cycle. A prover assigns a label to each node so that a verifier can check in constant time whetherthepropertyholdsornot. Weobtainasymptoticallytightbounds forthelabelsizeofthelattertwoproblems. Fors-treachability,weobtain a new asymptotically tight label size lower bound in one of our models, anddeviseanemulationtechniquethatallowsustotransferapreviously knownupperboundwithoutasymptoticlossinthebitcomplexityinan- other model. Zusammenfassung DieseDissertationbetrachtetverschiedeneAspektedesRechnensinanony- men Netzwerken, in denen die (Rechen-)Knoten nicht mit einem ein- deutigen Namen ausgestattet sind. Die Knoten im Netzwerk tauschen Nachrichten untereinander aus und berechnen jeder eine lokale Ausgabe; dieglobaleAusgabeergibtsichausderGesamtheitderlokalenAusgaben. Wirbetrachtenhauptsa¨chlichrandomisierteAlgorithmen,undstellenzu- erstdieFrage WaskannineinemanonymenNetzwerkberechnetwerden?“ ” ZweiKlassenvonProblemen,dieinanonymenNetzwerkenlo¨sbarsind, werdeninAbha¨ngigkeitdavon,obdieKnotenihreAusgabezuru¨cknehmen ko¨nnen oder nicht, definiert. Das Konzept eines verteilten Orakels wird eingefu¨hrtunduntersucht,undesergibtsicheineHierarchiemitschwieri- gen und vollsta¨ndigen Problemen fu¨r die Klassen. Eingie klassische und/ odercharakteristischeProblemeausdemUmfelddesverteiltenRechnens werden in Bezug auf Berechenbarkeit und Schwierigkeit klassifiziert. DerZugriffaufZufallsbitshatbekanntermasseneinengrossenEinfluss aufdieBerechenbarkeitinanonymenNetzwerken.IndemBemu¨hen,diesen Einflussgenauzucharakterisieren,zeigenwir,dassjedesProblem,welches voneinemrandomisierten anonymenAlgorithmusgel¨ost(undverifiziert) werden kann, auch von einem deterministischen anonymen Algorithmus gelo¨st werden kann, falls dieser eine Abstand-2-Fa¨rbung des Eingabe- graphen zur Verfu¨gung hat. Es dra¨ngt sich die Frage auf, wie viele Zufallsbits zum Lo¨sen solcher Probleme beno¨tigt werden. Wir finden heraus, dass die Antwort darauf von der gewu¨nschten Laufzeit des Algorithmus abha¨ngt. Genauer gesagt entwickelnwireinrandomisiertesSchemafu¨rAbstand-2-Fa¨rbungen,wel- ches erlaubt, eine ho¨here Laufzeit gegen eine geringere Anzahl beno¨- tigter Zufallsbits einzutauschen. Wir zeigen eine untere Schranke, die belegt,dassderTrade-offunseresSchemasasymptotischoptimalist,d.h. eine Reduktion der Laufzeit fu¨hrt zwangsweise zu einer ho¨heren Anzahl beno¨tigter Zufallsbits. SchliesslichuntersuchenwirdielokaleU¨berpru¨fbarkeitvonNetzwerk- eigenschaften wie s-t-Erreichbarkeit, Kreisfreiheit, oder ob das Netzwerk einen Kreis entha¨lt. Dabei weist ein Prover (Beweiser) den Knoten Label zu, sodass ein Verifier (Pru¨fer) in konstanter Zeit pru¨fen kann, ob die Eigenschafterfu¨lltist,odernicht.Wirerhaltenhierbeiasymptotischschar- fe Schranken fu¨r die Gro¨sse der Labels fu¨r die letzten beiden Problem- stellungen. Fu¨r s-t-Erreichbarkeit erhalten wir eine neue, asymptotisch scharfe untere Schranke in einem der betrachteten Modelle, und fu¨r ein anderesModellentwickelnwireineEmulationstechnik,dieesunserlaubt, einezuvorbekannteobereSchrankeohneEinbusseninderasymptotischen Labelgr¨osse in unser Modell zu u¨bertragen. Acknowledgements I would like to thank Prof. Roger Wattenhofer for the opportunity to writemythesisinhisgroup. InparticularIenjoyedthatIhadtheliberty toexploredifferenttopicsalongsidemyanonymouscomputingendeavors. ThepositiveeffectRogerhadonmypresentationskillsdeservesaspecial mention. Also, I want to thank my two co-referees Prof. Jukka Suomela and Prof.YuvalEmekfortheefforttheyputintoreviewingmythesis. Special thanksgotoYuvalforbabysittingmeduringRoger’sacademicleave,and for the many fruitful discussions we had. Without him, this thesis would be even less understandable. During my time at DISCO I have met many wonderful people, to whom I want to express my gratitude in no particular order. I thank PhilippSommerforthewarmwelcometoZurich,JohannesSchneiderfor taking me to places in Austria, Raphael Eidenbenz for rolling with me, JasminSmulaforcollectingclues,makingdeserts,andsharinglaughs,Sil- vio Frischknecht for announcing his leave, Stephan Holzer for advocating healthydiets,SamuelWeltenfortalkingSwiss-Germantomeandtaking me stargazing in Gstaad, Tobias Langner for his fine wine taste, and for teaching me how to do a left turn, Jara Uitto for keeping me company in unexpected places, and for Finnish memories, David Stolz for explain- ingthebasicallytwooptions,LauraPeerforpromotinganarchy,Michael Ko¨nig for playing—with words, and random, Barbara Keller for making me a sandwich, and for being patient in Lo`eche-les-Bains, Klaus-Tycho Fo¨rster for explaining the world to me, and for his bread roll deliver- ies,ChristianDeckerforsharinghistomato-tunasaucerecipeintimesof need, Sebastian Brandt for keeping his rusk box filled, Philipp Brandes for having nuts, Pascal Bissig for his baby stories, Yuezhou Lv for never being afraid to ask, Georg Bachmeier for his compatible sense of humor, Harald and Doris Schi¨oberg for awesome barbecues, Benny Ga¨chter for fulfillingmyhardwareneeds,TanjaLantzformakingmymovetoSwitzer- landabreeze,FriederikeBruetschforteachingmehowtoprint,andBeat Futterknecht for solving all problems at a moment’s notice. I would like to thank my friends Daniel, David, Hannes, Henning, Lucas, Manuel, and Marvin for making me feel at home whenever and wherever we meet. From Karlsruhe, Erhard, Holger, Paul, Thomas, and Ulrichhaveaspecialplaceinmyheart. IthankHans-Ju¨rgenforlongand thoughtful discussions, and Christa for having a sane sleeping schedule, especially in Italy. I am indebted to Mariana for enduring me, also in stressful times. My parents Ute and Ralf have always supported me in my endeavors, and I am grateful for that. Contents 1 Introduction 1 1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 The Impact of Output Revocability on Computability 7 2.1 Output Revocability . . . . . . . . . . . . . . . . . . . . . 8 2.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Notions of Correctness . . . . . . . . . . . . . . . . . . . . 14 2.4 Distributed Oracles . . . . . . . . . . . . . . . . . . . . . . 17 2.5 Problem Zoo . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.6 Proof of Theorem 2.3. . . . . . . . . . . . . . . . . . . . . 53 3 The Role of Randomness 55 3.1 Preliminaries and Genuine Solvability . . . . . . . . . . . 56 3.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.3 The Case for Infinity . . . . . . . . . . . . . . . . . . . . . 60 3.4 Dealing with (In)finity . . . . . . . . . . . . . . . . . . . . 67 3.5 Fibrations and 2-Hop Colorings . . . . . . . . . . . . . . . 75 4 The Cost of Randomness 77 4.1 Broadcast Model and Target Functions. . . . . . . . . . . 79 4.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.3 Tailor-Made 2-Hop Coloring . . . . . . . . . . . . . . . . . 82 4.4 Trade-off Lower Bound . . . . . . . . . . . . . . . . . . . . 88 5 Local Checking 95 5.1 Local Checkability in (Un)directed Graphs. . . . . . . . . 98 5.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.3 Checking Network Properties . . . . . . . . . . . . . . . . 102 5.4 Port Numbers vs. s-t Reachability . . . . . . . . . . . . . 113