Distribuerade datormodeller förutsätter vanligtvis tillförlitlig kommunikation mellan processorer. Även om sådana antaganden ofta gäller konstruerade nätverk, t.ex. på grund av underliggande felkorrigeringsprotokoll, är deras relevans för biologiska system, där meddelanden ofta förvrängs innan de når sin destination, ganska begränsad. I denna studie syftar vi till att överbrygga denna klyfta genom att noggrant analysera en kommunikationsmodell i stora anonyma populationer som består av enkla medel som interagerar genom korta och mycket opålitliga meddelanden. Vi fokuserar på problemet med ryktesspridning och problemet med majoritetskonsensus, två grundläggande uppgifter inom distribuerad datorteknik, och initierar deras studie under kommunikationsbuller. Vår modell för kommunikation är extremt svag och följer push skvaller kommunikation paradigm: I varje synkron runda varje agent som vill skicka information levererar ett meddelande till en slumpmässig anonym agent. Detta meddelande är dessutom begränsat till att endast innehålla en del (i huvudsak ett yttrande). Slutligen antas systemet vara så bullriga att biten i varje meddelande som skickas vänds oberoende med sannolikhet 1/2 −, för några små > 0. Även i denna starkt begränsade, stokastiska och bullriga miljö ger vi naturliga protokoll som löser de bullriga ryktesspridningen och de bullriga majoriteten-samförståndsproblemen effektivt. Våra protokoll körs i O(log n/ 2 ) rundor och använder O(n log n/ 2 ) meddelanden / bitar totalt, där n är antalet agenter. Dessa gränser är asymptotiskt optimala och är i själva verket lika snabba och budskap effektiva som om varje agent skulle * Incumbent av Shlomo och Michla Tomarin karriärutveckling ordförande. samtidigt har informerats direkt av källan. Våra effektiva, robusta och enkla algoritmer föreslår balans mellan tystnad och överföring, synkronisering och majoritetsbaserade beslut som viktiga ingredienser för att förstå kollektiva kommunikationssystem i anonyma och bullriga populationer.
Författarna till REF-studien rykte sprids och samförstånd i extremt felaktiga nätverk där lite i ett meddelande kan vändas med sannolikhet 1/2-ε.
Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication
{'venue': "PODC '14", 'journal': None, 'mag_field_of_study': ['Computer Science']}