Abstrakt. Topologiigenkänning är en av de grundläggande distribuerade uppgifterna i nätverken. Varje nod i ett anonymt nätverk måste deterministiskt producera en isomorf kopia av den underliggande grafen, med alla portar korrekt markerade. Denna uppgift är vanligtvis ogenomförbar utan någon föregående information. Sådan information kan lämnas till noderna som råd. Ett orakel som känner nätverket kan ge en (eventuellt annorlunda) sträng av bitar till varje nod, och alla noder måste rekonstruera nätverket med hjälp av detta råd, efter ett givet antal rundor av kommunikation. Under varje runda kan varje nod utbyta godtyckliga meddelanden med alla sina grannar och utföra godtyckliga lokala beräkningar. Tiden för att slutföra topologi erkännande är antalet rundor det tar, och storleken på råd är den maximala längden på en sträng ges till noder. Vi undersöker kompromisser mellan den tid då topologiigenkänning uppnås och den minsta storleken på råd som måste ges till noder. Vi tillhandahåller övre och nedre gränser på minsta storlek av råd som är tillräckligt för att utföra topologiigenkänning under en given tid, i klassen av alla grafer av storlek n och diameter D ≤ αn, för varje konstant α < 1. I de flesta fall är våra gränser asymptotiskt snäva. Närmare bestämt, om den tilldelade tiden är D − k, där 0 < k ≤ D, då är den optimala storleken på rådgivningen  och (n 2 log n)/(D − k + 1)). Om den tilldelade tiden är D, då är den här optimala storleken  till (n log n). Om den tilldelade tiden är D + k, där 0 < k ≤ D/2, då är den optimala storleken på rådgivningen. (1 + (log n) / k). Den enda återstående klyftan mellan våra gränser är för tid D + k, där D/2 < k ≤ D. I detta tidsintervall förblir vår övre gräns O (1 + (log n) / k), medan den nedre gränsen (som håller för varje tid) är 1. Detta lämnar en lucka om D  och o(log n). Slutligen visar vi att för tid 2D + 1, en bit av råd är både nödvändigt och tillräckligt. Våra resultat visar hur känslig den minsta storleken av råd för den tid som medges för topologi erkännande: tillåter bara en runda mer, från D till D + 1, minskar exponentiellt de råd som behövs för att utföra denna uppgift.
I REF studerades kompromisser mellan tiden för topologiigenkänning och storleken på de råd som gavs till noderna i LOCAL-kommunikationsmodellen.
Use knowledge to learn faster: Topology recognition with advice ⋆
{'venue': 'DISC', 'journal': None, 'mag_field_of_study': ['Computer Science']}