I en stor del av den teoretiska litteraturen om trådlösa algoritmer behandlas frågor om meddelandespridning tillsammans med frågor om tvistehantering. Denna kombination leder till komplicerade algoritmer och analyser, och gör det svårt att utvidga arbetet till svårare kommunikationsproblem. I det här dokumentet presenterar vi resultat från ett aktuellt projekt som syftar till att förenkla algoritmer och analyser genom att dela upp behandlingen i två nivåer, med hjälp av abstrakta "MAC-lager"-specifikationer för att inkapsla innehållshanteringen. Vi använder två olika abstrakta MAC-lager: det grundläggande i [14, 15] och ett nytt probabilistiskt lager. Vi presenterar först en typisk randomiserad stridshanteringsalgoritm för en vanlig grafbaserad radionätsmodell Vi visar att den implementerar båda abstrakta MAC-lager. Vi kombinerar denna algoritm med giriga algoritmer för singlemessage och multi-message global sändning och analyserar kombinationen med hjälp av båda abstrakta MAC-lager som mellanlager. Med hjälp av det grundläggande MAC-skiktet, visar vi en gräns för O(D log( n ) log  för tiden att leverera ett enda meddelande överallt med sannolikhet 1 −, där D är nätverksdiametern, n är antalet noder, och  till är den maximala nodgraden. Med hjälp av det probabilistiska skiktet, visar vi en gräns för O((D + log( n )) log  en), som matchar den mest kända gränsen för single-message som sänds över den fysiska nätverksmodellen. För multi-meddelandesändning får vi gränser för O((D + k en) log( n ) log  en) med hjälp av * Forskning som stöds av AFOSR kontrakt FA9550-08-1-0159 och NSF beviljar CCF-0726514, CNS-0715397 och CCF-0937274. † Denna författares arbete stöddes av NSERC:s postdoktorala stipendium. Den här författarens arbete stöddes av forskningsrådet för teknik och fysik [bidragsnummer EP/G023018/1, EP/H018816/1]. 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. DIALM-POMC'10 september 16, 2010, Cambridge, MA, USA. Upphovsrätt 2010 ACM 978-1-4503-0413-9/10/09...$10.00. baslager och O((D + k till log( n )) log  en) med det probabilistiska lagret, för tiden att leverera ett meddelande överallt i närvaro av som mest k samtidiga meddelanden.
Dessutom antogs det allmänt att noderna känner till några eller alla nätverksparametrar, t.ex. Δ och D. Enligt denna modell har de mest kända randomiserade distribuerade resultaten tidskomplexitet min{O(k log n log Δ + (D + n/ log n) log n log Δ), O(kΔ log n + D) log Δ} [1], REF.
Decomposing broadcast algorithms using abstract MAC layers
{'venue': "DIALM-POMC '10", 'journal': None, 'mag_field_of_study': ['Computer Science']}