I den här artikeln undersöker vi distribuerade beräkningar i dynamiska nätverk där nätverkets topologi ändras från rund till rund. Vi anser att en värsta fall modell där kommunikationslänkarna för varje runda väljs av en motståndare, och noder vet inte vilka deras grannar för den aktuella omgången är innan de sänder sina meddelanden. Modellen fångar upp mobila nätverk och trådlösa nätverk, där rörlighet och störningar gör kommunikation oförutsägbar. I motsats till mycket av det befintliga arbetet med dynamiska nät utgår vi inte från att nätverket så småningom slutar att förändras; vi kräver korrekthet och uppsägning även i nät som ständigt förändras. Vi introducerar en stabilitetsfastighet som kallas T-interval konnektivitet (för T ≥ 1), där det anges att för varje T på varandra följande rundor finns en stabil ansluten spännviddsdel. För T = 1 betyder detta att grafen är ansluten i varje v, men ändras godtyckligt mellan rundorna. Vi visar att i 1-interval anslutna grafer är det möjligt för noder att bestämma storleken på nätverket och beräkna alla beräkningsbara funktioner av deras initiala ingångar i O(n 2 ) rundor med meddelanden av storlek O(log n + d), där d är storleken på indata till en enda nod. Vidare, om grafen är T - interval ansluten för T > 1, kan beräkningen påskyndas med en faktor av T, och alla funktioner kan beräknas i O (n + n 2 /T ) rundor med meddelanden av storlek O (log n + d). Vi ger också två lägre gränser på token spridning problem, vilket kräver noderna för att sprida k bitar av information till alla noder i nätverket. Den T-interval anslutna dynamiska grafmodellen är en ny modell, som vi tror öppnar nya vägar för forskning i teorin om distribuerade datorer i trådlösa, mobila och dynamiska nätverk.
I REF är det också bevisat att om ingen begränsning av meddelandenas storlek krävs, kan räkneproblemet enkelt lösas i O(n) tid när noder har ID.
Distributed computation in dynamic networks
{'venue': "STOC '10", 'journal': None, 'mag_field_of_study': ['Computer Science']}