text: We consider information dissemination in a large n -user wireless network in which k users wish to share a unique message with all other users. Each of the n users only has knowledge of its own contents and state information; this corresponds to a one-sided push-only scenario. The goal is to disseminate all messages efficiently, hopefully achieving an order-optimal spreading rate over unicast wireless random networks. First, we show that a random-push strategy-where a user sends its own or a received packet at random-is order-wise suboptimal in a random geometric graph: specifically, Ω(√n) times slower than optimal spreading. It is known that this gap can be closed if each user has “full” mobility, since this effectively creates a complete graph. We instead consider velocity-constrained mobility where at each time slot the user moves locally using a discrete random walk with velocity v(n) that is much lower than full mobility. We propose a simple two-stage dissemination strategy that alternates between individual message flooding (“self promotion”) and random gossiping. We prove that this scheme achieves a close to optimal spreading rate (within only a logarithmic gap) as long as the velocity is at least v(n)=ω(√(logn k)). The key insight is that the mixing property introduced by the partial mobility helps users to spread in space within a relatively short period compared to the optimal spreading time, which macroscopically mimics message dissemination over a complete graph.
  @cite_34: Abstract : This thesis investigates certain fundamental problems in decentralized decision making and computation. We study the problem of whether a set of decision makers (or processors) with different (but related) information may make compatible decisions without communication and we characterize the computational complexity of this problem. We also analyze the complexity of other basic problems of decentralized decision making, such as decentralized detection (hypothesis testing). We then consider a scheme whereby a set of decision makers (processors) exchange and update tentative decisions which minimize a common cost function, given information they possess; we show that they are guaranteed to converge to consensus. Finally, we consider a broad class of asynchronous distributed (deterministic and stochastic) iterative optimization algorithms tolerating communication delays. We associate communication requirements with such algorithms and show that they converge appropriately under certain conditions which are no more severe than those required for their centralized counterparts. Several applications in human organizations, parallel computation and distributed signal processing are indicated. Additional keywords: decision theory. (Author).
  @cite_3: Motivated by applications to sensor, peer-to-peer, and ad hoc networks, we study distributed algorithms, also known as gossip algorithms, for exchanging information and for computing in an arbitrarily connected network of nodes. The topology of such networks changes continuously as new nodes join and old nodes leave the network. Algorithms for such networks need to be robust against changes in topology. Additionally, nodes in sensor networks operate under limited computational, communication, and energy resources. These constraints have motivated the design of "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for an arbitrary network graph, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Designing the fastest gossip algorithm corresponds to minimizing this eigenvalue, which is a semidefinite program (SDP). In general, SDPs cannot be solved in a distributed fashion; however, exploiting problem structure, we propose a distributed subgradient method that solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities derived from the gossip algorithm. We use this connection to study the performance and scaling of gossip algorithms on two popular networks: Wireless Sensor Networks, which are modeled as Geometric Random Graphs, and the Internet graph under the so-called Preferential Connectivity (PC) model.
  @cite_16: 
summary: Finally, we note that gossip algorithms have also been employed and analyzed for other scenarios like distributed averaging, where each node is willing to compute the average of all initial values given at all nodes in a decentralized manner, e.g. @cite_34 @cite_3 . The objective of such distributed consensus is to minimize the total number of computations. It turns out that the convergence rates of both message sharing and distributed averaging are largely dependent on the eigenvalues or, more specifically, the mixing times of the graph matrices associated with the network geometry @cite_3 @cite_16 .