Abstract-This paper initierar studien av självjusterande nätverk (eller distribuerade datastrukturer) vars topologier dynamiskt anpassar sig till ett kommunikationsmönster σ. Vi presenterar en helt decentraliserad självjusterande lösning som kallas SplayNet. Ett SplayNet är en distribuerad generalisering av det klassiska spelträdskonceptet. Det säkerställer korta vägar (som kan hittas med hjälp av lokal-grå routing) mellan kommunikationspartners samtidigt minimera topologiska omläggningar. Vi härleder en övre gräns för den amorterade kommunikationskostnaden för ett SplayNet baserat på empiriska entropier av σ, och visar att SplayNets har flera intressanta konvergensegenskaper. Till exempel, SplayNets har en påvisbar online optimalitet under speciella förfrågningar scenarier. Vi undersöker också det optimala statiska nätverket och visar olika lägre gränser för den genomsnittliga kommunikationskostnaden baserat på graf skärningar och den empiriska entropin i kommunikationsmönstret σ. Från dessa lägre gränser följer det, t.ex., att SplayNets är optimala i scenarier där förfrågningarna följer en produktdistribution också. Slutligen, detta papper visar att i motsats till minimi Linear Arrangemang problem som i allmänhet NP-hård, det optimala statiska trädnätverket kan beräknas i polynom tid för någon gäst graf, trots exponentiellt stora graf familj. Vi kompletterar vår formella analys med en liten simuleringsstudie på en Facebook-graf.
Närmast till vårt arbete är ovan nämnda papper av REF, där en helt decentraliserad generalisering av spelträd som kallas SplayNet presenteras.
Locally Self-Adjusting Tree Networks
{'venue': '2013 IEEE 27th International Symposium on Parallel and Distributed Processing', 'journal': '2013 IEEE 27th International Symposium on Parallel and Distributed Processing', 'mag_field_of_study': ['Computer Science']}