We use network coding to improve the speed of distributed computation in the dynamic network model of Kuhn, Lynch and Oshman [STOC '10]. In this model an adversary adaptively chooses a new network topology in every round, making even basic distributed computations challenging. show that n nodes, each starting with a d-bit token, can broadcast them to all nodes in time O(n^2) using b-bit messages, where b > d + log n. Their algorithms take the natural approach of token forwarding : in every round each node broadcasts some particular token it knows. They prove matching Omega(n^2) lower bounds for a natural class of token forwarding algorithms and an Omega(n log n) lower bound that applies to all token-forwarding algorithms. We use network coding, transmitting random linear combinations of tokens, to break both lower bounds. Our algorithm's performance is quadratic in the message size b, broadcasting the n tokens in roughly d b^2 * n^2 rounds. For b = d = O(log n) our algorithms use O(n^2 log n) rounds, breaking the first lower bound, while for larger message sizes we obtain linear-time algorithms. We also consider networks that change only every T rounds, and achieve an additional factor T^2 speedup. This contrasts with related lower and upper bounds of implying that for natural token-forwarding algorithms a speedup of T, but not more, can be obtained. Lastly, we give a general way to derandomize random linear network coding, that also leads to new deterministic information dissemination algorithms.
@cite_4: Consider a communication network in which certain source nodes multicast information to other nodes on the network in the multihop fashion where every node can pass on any of its received data to others. We are interested in how fast each node can receive the complete information, or equivalently, what the information rate arriving at each node is. Allowing a node to encode its received data before passing it on, the question involves optimization of the multicast mechanisms at the nodes. Among the simplest coding schemes is linear coding, which regards a block of data as a vector over a certain base field and allows a node to apply a linear transformation to a vector before passing it on. We formulate this multicast problem and prove that linear coding suffices to achieve the optimum, which is the max-flow from the source to each receiving node.
@cite_7: In this paper we investigate distributed computation in dynamic networks in which the network topology changes from round to round. We consider a worst-case model in which the communication links for each round are chosen by an adversary, and nodes do not know who their neighbors for the current round are before they broadcast their messages. The model captures mobile networks and wireless networks, in which mobility and interference render communication unpredictable. In contrast to much of the existing work on dynamic networks, we do not assume that the network eventually stops changing; we require correctness and termination even in networks that change continually. We introduce a stability property called T -interval connectivity (for T >= 1), which stipulates that for every T consecutive rounds there exists a stable connected spanning subgraph. For T = 1 this means that the graph is connected in every round, but changes arbitrarily between rounds. We show that in 1-interval connected graphs it is possible for nodes to determine the size of the network and compute any com- putable function of their initial inputs in O(n2) rounds using messages of size O(log n + d), where d is the size of the input to a single node. Further, if the graph is T-interval connected for T > 1, the computation can be sped up by a factor of T, and any function can be computed in O(n + n2 T) rounds using messages of size O(log n + d). We also give two lower bounds on the token dissemination problem, which requires the nodes to disseminate k pieces of information to all the nodes in the network. The T-interval connected dynamic graph model is a novel model, which we believe opens new avenues for research in the theory of distributed computing in wireless, mobile and dynamic networks.
@cite_8: We study the stopping times of gossip algorithms for network coding. We analyze algebraic gossip (i.e., random linear coding) and consider three gossip algorithms for information spreading Pull, Push, and Exchange. The stopping time of algebraic gossip is known to be linear for the complete graph, but the question of determining a tight upper bound or lower bounds for general graphs is still open. We take a major step in solving this question, and prove that algebraic gossip on any graph of size n is O(Δn) where Δ is the maximum degree of the graph. This leads to a tight bound of Θ(n) for bounded degree graphs and an upper bound of O(n2) for general graphs. We show that the latter bound is tight by providing an example of a graph with a stopping time of Ω(n2). Our proofs use a novel method that relies on Jackson's queuing theorem to analyze the stopping time of network coding; this technique is likely to become useful for future research.
@cite_9: Network coding promises to significantly impact the way communications networks are designed, operated, and understood. The first book to present a unified and intuitive overview of the theory, applications, challenges, and future directions of this emerging field, this is a must-have resource for those working in wireline or wireless networking. *Uses an engineering approach - explains the ideas and practical techniques *Covers mathematical underpinnings, practical algorithms, code selection, security, and network management *Discusses key topics of inter-session (non-multicast) network coding, lossy networks, lossless networks, and subgraph-selection algorithms Starting with basic concepts, models, and theory, then covering a core subset of results with full proofs, Ho and Lun provide an authoritative introduction to network coding that supplies both the background to support research and the practical considerations for designing coded networks. This is an essential resource for graduate students and researchers in electronic and computer engineering and for practitioners in the communications industry.
@cite_1: We give a new technique to analyze the stopping time of gossip protocols that are based on random linear network coding (RLNC). Our analysis drastically simplifies, extends and strengthens previous results. We analyze RLNC gossip in a general framework for network and communication models that encompasses and unifies the models used previously in this context. We show, in most settings for the first time, that it converges with high probability in the information-theoretically optimal time. Most stopping times are of the form O(k + T) where k is the number of messages to be distributed and T is the time it takes to disseminate one message. This means RLNC gossip achieves "perfect pipelining". Our analysis directly extends to highly dynamic networks in which the topology can change completely at any time. This remains true even if the network dynamics are controlled by a fully adaptive adversary that knows the complete network state. Virtually nothing besides simple O(kT) sequential flooding protocols was previously known for such a setting. While RLNC gossip works in this wide variety of networks its analysis remains the same and extremely simple. This contrasts with more complex proofs that were put forward to give less strong results for various special cases.
@cite_6: 
@cite_0: The problem of simultaneously disseminating k messages in a large network of n nodes, in a decentralized and distributed manner, where nodes only have knowledge about their own contents, is studied. In every discrete time-step, each node selects a communication partner randomly, uniformly among all nodes and only one message can be transmitted. The goal is to disseminate rapidly, with high probability, all messages to all nodes. It is shown that a random linear coding (RLC) based protocol disseminates all messages to all nodes in time ck+ spl Oscr ( spl radic kln(k)ln(n)), where c<3.46 using pull-based dissemination and c<5.96 using push-based dissemination. Simulations suggest that c<2 might be a tighter bound. Thus, if k spl Gt (ln(n)) sup 3 , the time for simultaneous dissemination RLC is asymptotically at most ck, versus the spl Omega (klog sub 2 (n)) time of sequential dissemination. Furthermore, when k spl Gt (ln(n)) sup 3 , the dissemination time is order optimal. When k spl Lt (ln(n)) sup 2 , RLC reduces dissemination time by a factor of spl Omega ( spl radic k lnk) over sequential dissemination. The overhead of the RLC protocol is negligible for messages of reasonable size. A store-and-forward mechanism without coding is also considered. It is shown that this approach performs no better than a sequential approach when k= spl prop n. Owing to the distributed nature of the system, the proof requires analysis of an appropriate time-varying Bernoulli process.
@cite_5: This book contains a thorough discussion of the classical topics in information theory together with the first comprehensive treatment of network coding, a subject first emerged under information theory in the mid 1990's that has now diffused into coding theory, computer networks, wireless communications, complexity theory, cryptography, graph theory, etc. With a large number of examples, illustrations, and original problems, this book is excellent as a textbook or reference book for a senior or graduate level course on the subject, as well as a reference for researchers in related fields.
@cite_13: We study the gains to be had by using random linear coding (RLC) for simultaneously disseminating k distinct messages in a network of n nodes in a decentralized and distributed manner for arbitrary k and n. The goal is to rapidly disseminate all the messages among all the nodes. Any node can communicate with any of the other nodes but only one at a time, nodes only have knowledge about their own contents, and the bandwidth for every transmission between two nodes is limited (does not scale with k or n). An efficient and well-studied protocol for message dissemination in such a framework is randomized gossip based message dissemination. The problem has been studied extensively without using any coding for message dissemination. We show using analysis and simulation that, in the regime k ges (ln(n))3, RLC based dissemination reduces the dissemination time (the time-steps to disseminate all the messages among all the nodes) by a factor of otimes(ln(n)) as compared to disseminating the messages sequentially (i.e., one after the other) as implicit in most non-coding based technique. In the regime k les (ln(n))2, the dissemination time with RLC goes down by a factor of Omega(radick ln k). More precisely, our results indicate that a RLC based protocol disseminates all the messages among all the nodes in time ck + O(radick ln(k)(ln(n)) for a suitable constant c > 0. Analytical results show that, c < 3.46 using pull based dissemination, and c < 5.96 using push based dissemination, but reported simulations suggest c < 2 might be a tighter bound
@cite_12: We study distributed algorithms, also known as gossip algorithms, for information dissemination in an arbitrary connected network of nodes. Distributed algorithms have applications to peer-to-peer, sensor, and ad hoc networks, in which nodes operate under limited computational, communication, and energy resources. These constraints naturally give rise to "gossip? algorithms: schemes in which nodes repeatedly communicate with randomly chosen neighbors, thus distributing the computational burden across all the nodes in the network and making the computation robust against node failures. Information dissemination based on network coding was introduced by Deb and Medard. They showed the virtue of coding by analyzing a coding algorithm for a complete graph. Although their scheme generalizes to arbitrary graphs, the analysis does not. We present analysis of this algorithm for arbitrary graphs. Specifically, we find that the information dissemination time is naturally related to the spectral properties of the underlying network graph. Our results provide insight into how the graph topology affects the performance of the coding-based information dissemination algorithm.
Next to @cite_7 the line of research most relevant to this work is network coding for gossip problems @cite_13 @cite_0 @cite_8 @cite_12 and most specifically work by Haeupler @cite_1 . Since its introduction @cite_6 @cite_4 network coding has revolutionized the understanding of information flow in networks and found many practical applications (see, e.g., the books @cite_5 @cite_9 ).