Frågan om vad som kan beräknas, och hur effektivt, är kärnan i datavetenskapen. Det är inte förvånande att en lika grundläggande fråga i distribuerade system och nätverksforskning är vad som kan beräknas på ett distribuerat sätt. Mer exakt, om noder av ett nätverk måste basera sitt beslut på information i deras lokala grannskap bara, hur väl kan de beräkna eller approximera ett globalt (optimering) problem? I detta papper ger vi den första polylogaritmiska lägre gräns på sådana lokala beräkningar för (optimering) problem inklusive minimal vertex cover, minimal (anslutna) dominerande uppsättning, maximal matchning, maximal oberoende uppsättning, och maximal matchning. Dessutom presenterar vi en ny distribuerad algoritm för att lösa allmänna täckande och förpackning linjära program. För vissa problem är denna algoritm tight med de nedre gränserna, medan för andra är det ett distribuerat approximationssystem. Tillsammans etablerar våra nedre och övre gränser den lokala beräkningsbarheten och approximabiliteten för en stor klass av problem, som karakteriserar hur mycket lokal information som krävs för att lösa dessa uppgifter. direkt kommunicera endast till ett litet antal angränsande noder. De flesta människor kommunicerar till exempel mellan bekanta eller inom familjen, och neuroner är direkt kopplade till ett relativt litet antal andra neuroner. Å andra sidan, trots att varje nod i sig är "nära-synt", dvs. begränsad till lokal kommunikation, förväntas hela systemet arbeta mot något slags globalt mål, lösning eller jämvikt. I detta arbete undersöker vi möjligheterna och begränsningarna med lokal beräkning, det vill säga i vilken utsträckning lokal information är tillräcklig för att lösa globala uppgifter. Många uppgifter kan lösas helt lokalt, till exempel, bestämma hur många vänner man har. Det är uppenbart att det bara krävs lokal kommunikation för att besvara denna fråga. Många andra uppgifter är naturligt globala, till exempel, räkna det totala antalet noder eller bestämma diametern på systemet. För att lösa sådana globala problem måste viss information spridas över hela nätverket. Finns det naturliga uppgifter som är mitt uppe i dessa två ytterligheter, uppgifter som varken är helt lokala eller till sin natur globala? I detta dokument besvarar vi denna fråga på ett positivt sätt. Anta, till exempel, att noderna vill organisera sig; vissa noder bör vara herrar, och de andra kommer att vara slavar. Reglerna är att inga två herrar skall vara direkta grannar, men varje slav måste ha minst en herre som direkt granne. I grafteorin är detta problem känt som maximal oberoende uppsättning (MIS) problem. Till en början verkar detta problem lokalt eftersom reglerna är helt lokala. Följaktligen kan man hoppas på en lösning där varje nod kan kommunicera med sina grannar några gånger, och tillsammans kan de bestämma vem som skall bli herre och vem som skall bli slav. Men som vi visar i den här artikeln är denna intuition vilseledande. Även om problemet kan definieras på ett rent lokalt sätt kan det inte lösas enbart med hjälp av lokal information! Oavsett hur systemet hanterar problemet, oavsett vilket protokoll eller algoritm noderna använder, är ickelokal information avgörande för att lösa uppgiften. Å andra sidan är problemet inte heller globalt: Midrange-information räcker för att lösa problemet. Som sådan etablerar MIS-problemet ett exempel som varken är lokalt eller globalt, utan mellan dessa ytterligheter. När det visar sig vara polylogaritmiskt i antalet noder, kallar vi det polylog-lokalt. Med hjälp av lokal-bevarande minskningar kan vi visa att det finns en hel klass av polylog-lokala problem. Vi visar att denna klass av polylog-lokala problem också inkluderar approximativa varianter av olika kombinatoriella optimeringsproblem, såsom minimal vertex cover, minimalt dominerande set, eller maximal matchning. I sådana problem måste varje nod basera sitt beslut (t.ex. om man vill ansluta sig till den dominerande uppsättningen) endast på information om sin lokala stadsdel, och målet är ändå att kollektivt uppnå en god approximation till den globalt optimala lösningen. Att studera sådana lokala approximationsalgoritmer är särskilt intressant eftersom det belyser avvägningen mellan mängden tillgänglig lokal information och den resulterande globala optimaliteten. Specifikt karakteriserar det den mängd information som behövs i distribuerat beslutsfattande: vad kan göras med den information som är tillgänglig i någon fast storlek grannskap av en nod. Positiva och negativa resultat för lokala algoritmer kan därför tolkas som informationsteoretiska övre och nedre gränser; de ger insikt i informationens värde. Vi tror att studier av de grundläggande möjligheterna och begränsningarna i lokal beräkning är av intresse för teoretiker i approximationsteori, distribuerad databehandling och grafteori. Dessutom kan våra resultat vara av intresse för ett brett spektrum av vetenskapliga områden, till exempel dynamiska system som förändras över tid. Vår teori visar att små förändringar i ett dynamiskt system kan orsaka en mellanliggande (eller polylog-lokal) "butterfly effekt", och det ger icke-triviala gränser för självläkande eller självorganiserande system, såsom självmontering robotar. Den fastställer också gränser för ytterligare tillämpningsområden, initialt inom ingenjörsvetenskap och datorteknik, eventuellt utvidgande av lokal beräkning: Lower and Upper Bounds 17:3 till andra områden som studerar storskaliga system, till exempel samhällsvetenskap, finans, neurala nätverk, eller myrkolonier. Lokala beräkningar: Vi anser att ett distribuerat system där distribuerade beslutsfattare vid noderna i en graf måste basera sina beräkningar och beslut på kunskap om sina lokala stadsdelar i grafen. Formellt får vi en graf G = (V, E),  på V = n, och en parameter k (k kan bero på n eller någon annan egenskap hos G). Vid varje nod v V finns det en oberoende agent (för enkelhetens skull identifierar vi agenten på node v med v också). Varje nod v  på V har en unik identifierare id(v) 1 och eventuellt några ytterligare indata. Vi antar att varje nod v  på V kan lära sig hela grannskapet k (v) upp till avstånd k i G (se nedan för en formell definition av k (v)). Baserat på denna information, alla noder måste göra oberoende beräkningar och måste individuellt besluta om sina resultat utan att kommunicera med varandra. Därför kan utdata från varje nod v  på V beräknas som en funktion av dess k grannskap k (v). Synkron meddelande Passing Model: Den beskrivna graf-teoretiska lokala beräkningsmodellen är likvärdig med den klassiska meddelande passerar modell distribuerad dator allmänt känd som LOCAL-modellen [Peleg 2000; Linial 1992 ]. I denna modell, är det distribuerade systemet modelleras som en punkt-till-punkt kommunikationsnätverk, beskrivs av en oriktad graf G = (V, E), där varje vertex v V representerar en nod (värd, enhet, processor,. ..) av nätverket, och en kant (u, v) E är en dubbelriktad kommunikationskanal som ansluter de två noderna. Inledningsvis, noder har ingen kunskap om nätverket grafen; de bara känner till sin egen identifierare och potentiella ytterligare ingångar. Alla noder vaknar upp samtidigt och beräkningen fortsätter i synkrona rundor. I varje omgång kan varje nod sända ett godtyckligt långt budskap till var och en av sina grannar. Eftersom vi överväger point-to-point nätverk, kan en nod skicka olika meddelanden till olika grannar i samma runda. Dessutom får varje nod utföra lokala beräkningar baserade på information som erhållits i meddelanden från tidigare rundor. Kommunikationen är tillförlitlig, dvs. varje meddelande som skickas under en kommunikationsrunda tas emot korrekt i slutet av omgången. En algoritms tid komplexitet definieras som antalet kommunikationsrundor tills alla noder slutar. 2 LOCAL-modellen som definieras ovan är den starkaste möjliga modellen när man studerar inverkan av lokalt begränsad kunskap på beräkningsbarhet, eftersom den helt fokuserar på lokaliseringen av distribuerade problem och abstrakterar andra problem som uppstår i utformningen av distribuerade algoritmer (t.ex. behov av små meddelanden, snabba lokala beräkningar, trängsel, asynkroni och paketförlust). Det är alltså den mest grundläggande modellen för att bevisa lägre gränser för lokal beräkning [Linial 1992], eftersom en lägre gräns är en verklig följd av lokala begränsningar. Det finns en en-till-ett-korrespondens mellan tids komplexiteten av distribuerade algoritmer i LOCAL-modellen och den graf-teoretiska uppfattningen av grannskapsinformation. I synnerhet, en distribuerad algoritm med tids komplexitet k (dvs., där varje nod utför k kommunikation rundor) är likvärdig med ett scenario där distribuerade beslutsfattare vid noderna i en graf måste basera sitt beslut på (fullständig) kunskap om deras k-hop grannskap k (v) endast. Detta är sant eftersom, med obegränsad storlek 1 Alla våra resultat håller för alla möjliga ID utrymme inklusive standard fall där ID är siffrorna 1,..., n. 2 Observera att denna synkrona meddelande passerar modellen fångar många praktiska system, inklusive till exempel Googles Pregel-system, en praktiskt genomförd beräkningsmodell lämplig för datorproblem i stora grafer [Malewicz et al. År 2010 )...........................................................................................................
Å andra sidan, Kuhn m.fl. REF visade en nedre gräns för (min { log n/ log log n, log / log  på}), även för LOCAL- modellen.
Local Computation: Lower and Upper Bounds
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}