Abstrakt. Detta dokument handlar om meddelandets komplexitet när det gäller sändningar i godtyckliga kommunikationsnät från punkt till punkt. Sändning är en uppgift som initieras av en enda processor som vill förmedla ett meddelande till alla processorer i nätverket. Den allmänt accepterade modellen av kommunikationsnät, där varje processor till en början känner till sina grannars identitet men inte känner till hela nätverkets topologi, antas. Även om det verkar uppenbart att antalet meddelanden som krävs för sändning i denna modell motsvarar antalet länkar, har inget bevis för detta grundläggande faktum lämnats tidigare. Det visas att meddelandets komplexitet beror på den exakta komplexitetsåtgärden. Om meddelanden av obunden längd räknas till enhetskostnad, då sändning kräver 8( 1 VI ) meddelanden, där V är uppsättningen processorer i nätverket. Det bevisas att om man räknar meddelanden med begränsad längd, så kräver sändningen 8 (1 E 1) meddelanden, där E är uppsättningen av kanter i nätverket. Om man utgår från en mellanliggande modell där varje vertex känner till nätets topologi inom radien p 2 1 från sig själv, visas motsvarande övre och nedre gränser för G(min 1 E 1, 1 V 1 '+e(')'p) för det antal meddelanden med begränsad längd som krävs för sändning. Både de övre och nedre gränserna håller för både synkrona och asynkrona nätverksmodeller. Samma resultat håller för byggandet av spännande träd, och olika andra globala uppgifter.
Om t.ex. varje nod känner till nätets topologi inom radien ρ av det, visas det i REF (min {m, n 1+ och 1)/ρ }) det minsta antalet meddelanden med begränsad längd som gör det möjligt att väcka ett nätverk med n noder och m-kanter.
A trade-off between information and communication in broadcast protocols
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}