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.
While traditional distributed algorithms research has focused on computation in static networks, the analysis of dynamic network topologies has gained importance both in practice and theory. @cite_7 offer an extensive review of this literature.
@cite_7
2139322472
The study of influential members of human networks is an important research question in social network analysis. However, the current state-of-the-art is based on static or aggregated representation of the network topology. We argue that dynamically evolving network topologies are inherent in many systems, including real online social and technological networks: fortunately the nature of these systems is such that they allow the gathering of large quantities of finegrained temporal data on interactions amongst the network members. In this paper we propose novel temporal centrality metrics which take into account such dynamic interactions over time. Using a real corporate email dataset we evaluate the important individuals selected by means of static and temporal analysis taking two perspectives: firstly, from a semantic level, we investigate their corporate role in the organisation; and secondly, from a dynamic process point of view, we measure information dissemination and the role of information mediators. We find that temporal analysis provides a better understanding of dynamic processes and a more accurate identification of important people compared to traditional static methods.