Paper Info
Title
Decentralized Management of Random Walks over a Mobile Phone Network
Abstract
Gossip learning is a form of decentralized stochastic gradient descent search that is implemented through randomized walks within a network. Our goal is to enable one to deploy gossip learning in open distributed systems, for example, in overlay networks formed by mobile devices, where different data mining tasks could be launched by many users. Among the many problems this long term goal raises, here we focus on the problem of running many random walks simultaneously. This is a challenging problem in itself in a decentralized setting because all the walks have to be persistent (they have to perform many hops) and agile (they need to move quickly). At the same time, the solution must take hard bandwidth constraints into account. Here, we propose a protocol to manage O(n) random walks in a network of n nodes. Although our motivation is gossip learning, this protocol may be viewed as a general middleware service for the management of walks over networks. A key element of our protocol is a multi-level restarting mechanism designed to prevent the failure of random walks due to node churn, while respecting a set of bandwidth constraints. Here, we simulate our solution using a trace collected from real smartphones. We demonstrate that the random walks are kept alive and are run at close to optimal speed under the given bandwidth constraints.
Year
DOI
Venue
2017
10.1109/PDP.2017.73
2017 25th Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP)
Keywords
Field
DocType
decentralized data mining,gossip,churn,random walks,mobile phone networks
Middleware,Stochastic gradient descent,Random walk,Computer science,Gossip,Computer network,Mobile device,Gossip protocol,Mobile phone,Overlay network,Distributed computing
Conference
ISSN
ISBN
Citations 
1066-6192
978-1-5090-6059-7
0
PageRank 
References 
Authors
0.34
14
2
Name
Order
Citations
PageRank
Árpád Berta140.75
Márk Jelasity21732102.28