Detta dokument fokuserar på att visa time-message kompromisser i distribuerade algoritmer för grundläggande problem som ledarval, sändning, spanning träd (ST), minsta spanning träd (MST), minimal skärning, och många grafverifiering problem. Vi anser att den synkrona CONGEST distribuerade datormodellen och antar att varje nod har initial kunskap om sig själv och identifierarna av sina grannar - den så kallade KT 1-modellen - en välstuderad modell som också naturligt uppstår i många tillämpningar. Nyligen har det fastställts att man kan få (nästan) singulariskt optimala algoritmer, dvs algoritmer som samtidigt har optimal tid och meddelande komplexitet (upp till polylogaritmiska faktorer), för många grundläggande problem i standard KT 0 modellen (där noder har endast lokal kunskap om sig själva och inte sina grannar). Situationen är mindre tydlig i KT 1-modellen. I det här dokumentet presenterar vi flera nya distribuerade algoritmer i KT 1-modellen som skiftar mellan tids- och meddelandekomplex. Våra distribuerade algoritmer är baserade på en enhetlig och allmän strategi som innebär att bygga en sparifierad spännvidd subgraph av den ursprungliga grafen - som kallas en danner - som avskiljer antalet kanter med diametern på sparifieraren. I synnerhet är en viktig ingrediens i vårt tillvägagångssätt en distribuerad randomiserad algoritm som, med tanke på en graf G och alla δ  på [0, 1], med hög sannolikhet 1 konstruerar en danner som har diameter Õ(D + n 1−δ ) och Õ(min {m, n 1+δ }) kanter i Õ(n 1−δ ) rundor medan du använder Õ(min{m, n 1+δ }) meddelanden, där n, m, och D är antalet noder, kanter, och diametern på G, respektive. 2 Med hjälp av vår danner konstruktion, presenterar vi en familj av distribuerade randomiserade algoritmer för olika grundläggande problem som uppvisar en kompromiss mellan budskap och tid komplexitet och som förbättrar jämfört med tidigare resultat. Specifikt visar vi följande resultat (alla håller med hög sannolikhet) i KT 1-modellen, som subsumerar och förbättrar över tidigare gränser i KT 1-modellen (King et al., PODC 2014 och Awerbuch et al., JACM 1990) 2. MST och Connectivity. Dessa problem kan lösas i Õ(D + n 1−δ ) rundor med hjälp av O(min{m, n 1+δ }) meddelanden för alla δ  på [0, 0.5]. Särskilt för δ = 0.5 får vi en distribuerad MST-algoritm som körs i optimala Õ(D + ε n) rundor och använder Õ(min{m, n 3/2 }) meddelanden. Vi noterar att detta förbättrar över den ovanligt optimala algoritmen i KT 0-modellen som använder Õ(D + ε n) rundor och Õ(m) meddelanden. 3. Vad är det som händer? Minsta klippning. O(log n)-ungefärlig minsta nedskärning kan lösas i Õ(D + n 1−δ ) rundor med hjälp av Õ(min{m, n 1+δ }) meddelanden för alla δ  till [0, 0.5].
Det senaste arbetet med Gmyr och Pandurangan REF ger flera nya algoritmer i KT 1-modellen och visar många andra separationer mellan de två modellerna.
Time-Message Trade-Offs in Distributed Algorithms
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}