Vi studerar kodningssystem för multipart interaktiv kommunikation över synkrona nätverk som lider av stokastiskt buller, där varje bit är självständigt vända med sannolikhet ε. Vi analyserar de minimala overhead som måste läggas till av kodningssystemet för att lyckas med att utföra beräkningen trots bullret. Vårt huvudresultat är en lägre gräns för kommunikationen av alla bullertåliga protokoll över ett synkront stjärnnätverk med n-partier (där alla parter kommunicerar i varje runda). Specifikt visar vi en uppgift som kan lösas genom att kommunicera T-bitar över det bullerfria nätverket, men för vilken alla protokoll med framgång sannolikheten för 1 − o(1) måste kommunicera minst  och (T logg n logg n ) bitar när kanalerna är bullriga. Genom ett resultat från 1994 av Rajagopalan och Schulman, den avmattning vi visar är den högsta man kan få på någon topologi, upp till en log n faktor. Vi fullföljer vår nedre gräns med ett matchande kodningssystem som uppnår samma overhead, vilket innebär att kapaciteten hos (synkrona) stjärnnätverk är  och (log log n/ log n). Våra gränser bevisar att, trots flera tidigare kodningssystem med hastighet  och (1) för vissa topologier, inget kodningssystem med konstant hastighet  och (1) existerar för godtyckliga n-part bullriga nätverk.
Nyligen, Braverman et al REF visar en lägre gräns för kodning system för multipart interaktiv kommunikation över synkrona stjärnnätverk som lider av stokastiskt buller.
Constant-rate coding for multiparty interactive communication is impossible
{'venue': 'STOC 2016', 'journal': None, 'mag_field_of_study': ['Computer Science']}