Ett centralt tema i distribuerade nätverksalgoritmer handlar om att förstå och hantera frågan om ort. Trots avsevärda framsteg har forskningsinsatser i denna riktning ännu inte resulterat i en solid grund i form av en grundläggande beräkningsmässig komplexitetsteori för orten. Inspirerad av sekventiell komplexitetsteori fokuserar vi på en komplexitetsteori för distribuerade beslutsproblem. I samband med lokalitet, lösa ett beslut problem kräver processorer att självständigt inspektera sina lokala stadsdelar och sedan kollektivt besluta om en given global input instans tillhör vissa angivna språk. Vi betraktar standard LOCAL modellen för beräkning och definierar LD(t) (för lokalt beslut) som den klass av beslutsproblem som kan lösas i t kommunikationsrundor. Vi studerar först den spännande frågan om randomisering hjälper i lokala distribuerade datorer, och i vilken utsträckning. Specifikt definierar vi motsvarande randomiserade klass BPLD(t, p, q), som innehåller alla språk för vilka det finns en randomiserad algoritm som körs i t rundor, accepterar korrekta fall med sannolikhet minst p och avvisar felaktiga sådana med sannolikhet minst q. Vi visar att p 2 + q = 1 är en tröskel för inneslutning av LD(t) i BPLD(t, p, q). Mer exakt visar vi att det finns ett språk som inte tillhör LD(t) för någon t = o(n) men som tillhör BPLD(0, p, q) för någon p, q  på ett sådant sätt att p 2 + q ≤ 1. Å andra sidan visar vi att, begränsad till ärftliga språk, BPLD(t, p, q) = LD( O(t)), för alla funktioner t och alla p, q  på (0, 1] sådan att p 2 + q > 1. Dessutom undersöker vi icke-determinismens inverkan på lokala beslut, och etablerar några strukturella resultat inspirerade av klassisk computational complexory. I synnerhet visar vi att icke-determinism hjälper, men att denna hjälp är begränsad, eftersom det finns språk som inte kan avgöras på ett icke-deterministiskt sätt. Kanske överraskande visar det sig att det är kombinationen av randomisering med icke-determinism som gör det möjligt att bestämma alla språk i konstant tid. Slutligen introducerar vi begreppet lokal minskning och fastställer vissa fullständighetsresultat.
Inspirerad av klassisk beräkning komplexitetsteori REF, föreslog att studien av beslutsproblem kan leda till nya strukturella insikter också i den mer komplexa distribuerade datorinställningen.
Local Distributed Decision
{'venue': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'journal': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Computer Science']}