A Learning Based Scheme for Fair Timeliness in Sparse Gossip Networks
Purbesh Mitra Sennur Ulukus
We consider a gossip network, consisting of $n$ nodes, which tracks the
information at a source. The source updates its information with a Poisson
arrival process and also sends updates to the nodes in the network. The nodes
themselves can exchange information among themselves to become as timely as
possible. However, the network structure is sparse and irregular, i.e., not
every node is connected to every other node in the network, rather, the order
of connectivity is low, and varies across different nodes. This asymmetry of
the network implies that the nodes in the network do not perform equally in
terms of timelines. Due to the gossiping nature of the network, some nodes are
able to track the source very timely, whereas, some nodes fall behind versions
quite often. In this work, we investigate how the rate-constrained source
should distribute its update rate across the network to maintain fairness
regarding timeliness, i.e., the overall worst case performance of the network
can be minimized. Due to the continuous search space for optimum rate
allocation, we formulate this problem as a continuum-armed bandit problem and
employ Gaussian process based Bayesian optimization to meet a trade-off between
exploration and exploitation sequentially.