Vi studerar problemet med mängden kunskap om ett kommunikationsnät som måste ges till dess noder för att effektivt sprida information. Medan tidigare resultat om kommunikation i nätverk använt särskilt partiell information tillgänglig för noder, såsom kunskap om grannskapet eller kunskap om nätverket topologi inom någon radie, vår strategi är kvantitativ: vi undersöker det minsta totala antalet bitar av information (minimum oracle storlek) som måste vara tillgängliga för noder för att utföra effektiv kommunikation. Det visar sig att den minsta orakelstorlek för vilken en distribuerad uppgift kan utföras effektivt, kan tjäna som ett mått på svårigheten med denna uppgift. Vi använder denna åtgärd för att göra en kvantitativ åtskillnad mellan svårigheten hos två till synes liknande grundläggande kommunikationsprimära: sändningen och uppvaknandet. I båda av dem en framstående nod, som kallas källan, har ett meddelande, som måste överföras till alla andra noder i nätverket. I uppvaknandet kan endast noder som redan fått källmeddelandet (dvs. är vakna) skicka meddelanden till sina grannar och på så sätt väcka dem. I sändningen kan alla noder skicka styrmeddelanden redan innan de får källkoden, vilket kan underlätta dess framtida spridning. I båda fallen är vi intresserade av att utföra kommunikationsuppgiften med optimal meddelande komplexitet, dvs. att använda ett antal meddelanden linjärt i antalet noder. Vi visar att minsta oraklet storlek tillåter * Stöds av projekten PairAPair av ACI Masses de Données, och FRAGILE av ACI Sécurité Informatique. Ytterligare stöd från INRIA-projektet "Grand Large". † Stöds delvis av NSERCs forskningsanslag och av forskningsprofessuren i Distributed Computing vid Université du Québec en Outaouais. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Uppvakna med ett linjärt antal meddelanden i ett n-node-nätverk, är  till (n log n), medan sändningen med ett linjärt antal meddelanden kan uppnås med ett orakle av storlek O(n). Vi visar också att den senare orakelstorleken är nästan optimal: ingen orakel av storlek o(n) kan tillåta att sända med ett linjärt antal meddelanden. Ett effektivt uppvaknande kräver alltså strikt mer information om nätverket än en effektiv sändning.
I REF jämförde författarna den minsta mängd rådgivning som krävs för att lösa två problem med informationsspridning med hjälp av ett linjärt antal meddelanden.
Oracle size: a new measure of difficulty for communication tasks
{'venue': "PODC '06", 'journal': None, 'mag_field_of_study': ['Computer Science']}