Vi studerar verifieringsproblemet i distribuerade nätverk, som anges på följande sätt. Låt H vara en subgraf av ett nätverk G där varje vertex av G vet vilka kanter incident på det är i H. Vi vill kontrollera om H har vissa egenskaper, t.ex. om det är ett träd eller om det är ansluten (varje nod vet i slutet av processen om H har den angivna egenskapen eller inte). Vi skulle vilja utföra denna verifiering på ett decentraliserat sätt via en distribuerad algoritm. Kontrollens tidsmässiga komplexitet mäts som antalet rundor av distribuerad kommunikation. I detta dokument initierar vi en systematisk studie av distribuerad verifiering, och ger nästan snäva lägre gränser för körtiden för distribuerade verifieringsalgoritmer för många * En fullständig version av detta dokument finns tillgänglig som [5] på http:// arxiv.org/abs/1011.3049 † En del av det arbete som utförts vid Georgia Institute of Technology. Grundläggande problem som konnektivitet, spännvidd för ansluten subgraf och s – t skärverifiering. Vi visar sedan tillämpningar av dessa resultat för att härleda stark villkorslös tid lägre gränser på hårdheten av distribuerad approximation för många klassiska optimeringsproblem inklusive minsta spännvidd träd, kortaste vägar, och minimal skärning. Många av dessa resultat är de första icke-triviala lägre gränserna för både exakt och ungefärlig distribuerad beräkning och de löser tidigare öppna frågor. Dessutom subsumerar och förbättrar vår ovillkorliga nedre gräns av approximering av minsta spännträd (MST) den tidigare hårdheten av approximationen bundet av Elkin [STOC 2004] samt den lägre gränsen för (exakt) MST beräkning av Peleg och Rubinovitj [FOCS 1999]. Vårt resultat innebär att det inte kan finnas någon distribuerad approximationsalgoritm för MST som är betydligt snabbare än den nuvarande exakta algoritmen, för någon approximationsfaktor. Våra lägre bundna bevis visar en intressant koppling mellan kommunikation komplexitet och distribuerad dator som visar sig vara användbara för att fastställa tids komplexiteten av exakt och ungefärlig distribuerad beräkning av många problem.
Observera att alla de nedre gränser som bevisas i REF är av typen och en huvudfråga var om tekniken kan användas för att visa sig vara starkare nedre gränser.
Distributed verification and hardness of distributed approximation
{'venue': "STOC '11", 'journal': None, 'mag_field_of_study': ['Computer Science']}