Abstract-Gossip algoritmer har nyligen fått stor uppmärksamhet, främst eftersom de utgör enkla och robusta system för meddelande-passing för distribuerad information bearbetning över nätverk. Men för många topologier som är realistiska för trådlösa ad-hoc- och sensornätverk (som rutnät och slumpmässiga geometriska grafer), konvergerar det vanliga närmaste granne skvaller så långsamt som översvämningar (O(n 2 ) meddelanden). En nyligen föreslagen algoritm som kallas geografiskt skvaller förbättrar skvallereffektiviteten genom en p n faktor, genom att utnyttja geografisk information för att möjliggöra multihop långdistanskommunikation. Detta papper bevisar att en variation av geografiskt skvaller som medelvärder längs rutten vägar, förbättrar effektiviteten med en ytterligare p n faktor, och är ordning optimal (O(n) meddelanden) för rutnät och slumpmässiga geometriska grafer med hög sannolikhet. Vi utvecklar en allmän teknik (travel agentur metod) baserad på Markov kedja blandning tid ojämlikheter som kan ge gränser för prestanda av randomiserade meddelande-passing algoritmer som arbetar över olika graf topologier.
Benezit m.fl. REF visade att en utvidgning av geografiskt skvaller som genomsnitt längs rutten kan ytterligare minska konvergenstiden till O(n log n) som är optimal för slumpmässiga geometriska grafer och rutnät.
Order-Optimal Consensus Through Randomized Path Averaging
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science', 'Mathematics']}