Problemet med att beräkna värdens funktioner vid noderna i ett nätverk på ett helt distribuerat sätt, där noderna inte har unika identiteter och fattar beslut baserade enbart på lokal information, har applikationer i sensor, peer-to-peer och ad hoc-nätverk. Uppgiften att beräkna separata funktioner, som kan skrivas som linjära kombinationer av funktioner av enskilda variabler, studeras i detta sammanhang. Kända iterativa algoritmer för medelvärden kan användas för att beräkna normaliserade värden för sådana funktioner, men dessa algoritmer sträcker sig i allmänhet inte till beräkningen av de faktiska värdena för separata funktioner. Det viktigaste bidraget i detta dokument är utformningen av en distribuerad randomiserad algoritm för beräkning av separerbara funktioner. Körtiden för algoritmen visas vara beroende av körtiden för en minsta beräkningsalgoritm som används som subrutin. Använda en randomiserad skvaller mekanism för minsta beräkning som subrutin ger en komplett fullt distribuerad algoritm för att beräkna separerade funktioner. För en grupp av grafer med små spektralgap, såsom rutnätsdiagram, är den tid som algoritmen använder för att beräkna medelvärden av en mindre ordning än den tid som krävs för ett känt iterativt medelvärdesschema.
En stor klass av sådana beräkningar kan också genomföras med hjälp av summan som en primitiv operation; denna gång i en lokal betydelse: noder beräkna summan av värdena hos sina grannar, eller i allmänhet en separat funktion av grannvärdena REF.
Fast Distributed Algorithms for Computing Separable Functions
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science']}