Coordinated randomness in sparse graphs
Usman A. Khan · 2012
We are interested in choosing N distinct objects randomly at N nodes that are inter-connected over a sparse graph. The random assignment should be such that no two nodes are assigned the same object. The challenge in the problem is twofold: (i) there is no central dispatcher; and (ii) the node communication network is not a complete graph. In this setting, each node relies on its neighboring nodes and devises a strategy, uniform across all nodes, such that the resulting assignment is unique, i.e., no two nodes share the same task, and random, i.e., the assignment cannot be predicted beforehand. To this aim, we study some of the existing task-assignment and shuffling problems and note that they are not applicable within the above setup. We then propose a swap and collide algorithm that can achieve the unique and random object assignment in finite-time almost surely (a.s.) The analysis of the proposed approach is based on Markov chain arguments. Parts of this paper are presented in [1].