I detta arbete studerar vi protokoll så att populationer av distribuerade processer kan bygga nätverk. För att lyfta fram de grundläggande principerna för distribuerade nätkonstruktioner håller vi modellen minimal i alla avseenden. I synnerhet antar vi finita-state processer som alla börjar från samma ursprungliga tillstånd och alla utför samma protokoll. Dessutom antar vi parvisa interaktioner mellan de processer som planeras av en rättvis motståndare. För att processerna ska kunna bygga nätverk låter vi dem aktivera och avaktivera sina parvisa anslutningar. När två processer interagerar, tar protokollet som ingång tillstånden i processerna och tillståndet för deras anslutning och uppdaterar dem alla. Inledningsvis är alla anslutningar inaktiva och målet är att processerna, efter att ha interagerat och aktiverat/avaktiverat anslutningar ett tag, ska sluta med ett önskat stabilt nätverk. Vi ger protokoll (optimala i vissa fall) och lägre gränser för flera grundläggande nätverk konstruktionsproblem såsom spännvidd linje, spännvidd ring, spännande stjärna, och regelbundet nätverk. Den förväntade tiden för konvergens av våra protokoll analyseras under en enhetlig slumpmässig schemaläggare. Slutligen bevisar vi flera universalitet resultat genom att presentera generiska protokoll som kan simulera en Turing Machine (TM) och utnyttja den för att bygga en stor klass av nätverk. Vi visar dessutom hur man delar upp befolkningen i k supernodes, var och en är en rad av log k noder, för den största sådan k. Denna mängd lokalt minne är tillräcklig för supernoderna för att få unika namn och utnyttja deras namn och deras minne för att förverkliga icke-triviala konstruktioner.
I REF, Michail och Spirakis ge protokoll för flera grundläggande nätverkskonstruktion problem, och de bevisar flera universalitet resultat genom att presentera generiska protokoll som kan simulera en Turing Machine och utnyttja den för att stabilt bygga en stor klass av nätverk, i avsaknad av krasch fel.
Simple and efficient local codes for distributed stable network construction
{'venue': "PODC '14", 'journal': None, 'mag_field_of_study': ['Computer Science']}