I detta dokument, studerar vi distribuerade samförstånd i radionätverk inställning. Vi producerar nya övre och nedre gränser för detta problem i en abstrakt MAC-lagermodell som fångar de viktigaste garantierna från de flesta trådlösa MAC-lager. Mer i detalj generaliserar vi först den välkända omöjligheten av deterministiskt samförstånd med ett enda kraschfel [15] från den asynkrona meddelande passerar modellen till vår trådlösa inställning. Genom att utgå från att det inte finns några fel undersöker vi sedan den mängd nätverkskunskap som krävs för att lösa samförståndet i vår modell-en viktig fråga med tanke på att dessa nätverk ofta sätts in på ett ad hoc-sätt. Vi bevisar samförstånd är omöjligt utan unika id:er eller utan kunskap om nätverksstorlek (i multihop topologier). Vi visar också en lägre gräns på optimal tids komplexitet. Vi matchar sedan dessa nedre gränser med ett par nya deterministiska konsensusalgoritmer-en för enstaka humle topologier och en för multihop topologier-framställa en omfattande karakterisering av konsensus problemet i den trådlösa inställningen. Ur ett teoretiskt perspektiv ger våra resultat ny insikt i nätverksinformationens roll och kraften i MAC-skiktets abstraktioner för att lösa distribuerat samförstånd. Ur ett praktiskt perspektiv, med tanke på den abstraktionsnivå som används av vår modell, kan våra övre gränser enkelt implementeras i riktiga trådlösa enheter på befintliga MAC-lager samtidigt som deras korrekthet garanterar att utvecklingen av trådlösa distribuerade system underlättas.
Andra arbeten som tar hänsyn till samförstånd i modeller med begränsad kommunikation inkluderar REF, som studerar överenskommelser i radionätmodellen för trådlös kommunikation.
Consensus with an abstract MAC layer
{'venue': "PODC '14", 'journal': None, 'mag_field_of_study': ['Computer Science']}