Vi studerar den distribuerade komplexiteten i att beräkna en maximal oberoende uppsättning (MIS) i radionätverk med helt okänd topologi, asynkron vakna upp, och ingen kollision detekteringsmekanism tillgängliga. Specifikt föreslår vi en ny randomiserad algoritm som beräknar en MIS i tiden O(log 2 n) med hög sannolikhet, där n är antalet noder i nätverket. Detta förbättrar avsevärt på de bästa tidigare kända lösningarna. En lägre gräns för  ska (log 2 n/ log log n) som anges i [11] innebär att vår algoritms körtid är nära optimal. Vårt resultat visar att den hårda radionätmodellen endast innebär en ytterligare O(log n) faktor jämfört med Lubys MIS algoritm i den meddelandepasserande modellen. Detta har viktiga konsekvenser i samband med ad hoc- och sensornätverk vars egenskaper är nära fångade av radionätsmodellen.
Detta förbättrades senare i REF till O(log 2 n).
Maximal independent sets in radio networks
{'venue': "PODC '05", 'journal': None, 'mag_field_of_study': ['Computer Science']}