I CONGEST-modellen är ett kommunikationsnät en oriktad graf vars n noder är processorer och vars m-kanter är kommunikationslänkarna mellan processorer. Vid varje given tidpunkt kan ett meddelande av storlek O(log n) skickas av varje nod till var och en av sina grannar. Vi visar för synkron modell: Om alla noder börjar i samma runda, och varje nod vet sitt ID och ID: s av sina grannar, eller i fallet med MST, de distinkta vikterna av dess incident kanter och vet n, då det finns Monte Carlo algoritmer som lyckas w.h.p. För att fastställa en minsta spännviddsskog (MST) och en spännskog (ST) med hjälp av O(n log 2 n/ log log n) meddelanden för MST och O(n log n) meddelanden för ST, resp. Dessa resultat motsäger den "folkteorem" som noterades i Awerbuch, et.al., JACM 1990 att den distribuerade konstruktionen av ett sändningsträd kräver  och m) meddelanden. Denna nedre gräns har visats där och i andra tidningar för vissa CONGEST modeller; vårt protokoll visar gränserna för dessa modeller. Ett dynamiskt distribuerat nätverk är ett nätverk som genomgår kantinsättningar eller raderingar online. Vi visar också hur man reparerar en MST eller ST i ett dynamiskt nätverk med asynkron kommunikation. En kantradering kan behandlas i O(n log n/ log log n) förväntade meddelanden i MST, och O(n) förväntade meddelanden för ST- problemet, medan en kantinsättning använder O(n) meddelanden i värsta fall. Vi kallar detta "impromptu" uppdatering eftersom vi antar att mellan bearbetning av edge uppdateringar det inte finns någon förbehandling eller lagring av * Forskning som stöds av Simons Institute för teorin om tillstånd att göra digitala eller hårda kopior av hela eller en del av detta arbete för personligt eller klassrum användning beviljas utan avgift förutsatt att kopior inte görs eller distribueras för vinst eller kommersiella fördelar och att kopior bär detta meddelande och den fullständiga citering på första sidan. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, eller återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Begär tillstånd från authoritys@acm.org.
Nyligen, King et al. REF visade ett överraskande och elegant resultat: i KT 1-modellen kan man ge en randomiserad Monte Carlo-algoritm för att konstruera en MST i Õ (n) meddelanden ( och n) är ett meddelande lägre bundet) och i Õ (n) tid.
Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication
{'venue': "PODC '15", 'journal': None, 'mag_field_of_study': ['Computer Science']}