Dynamic Networks. Large real-world networks are inherently very dynamic: the participants in peer-to-peer (P2P) networks change over time, mobile nodes in wireless networks move in and out of each other's transmission range, and, in distributed data center networks, faulty machines need to be replaced by new machines without interrupting the operation of the remaining network. Furthermore, they are resource-constrained, unreliable, and vulnerable to attacks. For example, in P2P networks, peers (nodes) join and leave at a high rate and the underlying network topology also changes continuously over time; these networks are bandwidth-constrained, unreliable due to the high node turnover, and the open admission nature of these systems allows malicious behaviour by nodes. Performing efficient computation in dynamic networks is much more challenging than in traditional static networks. First, one has to deal with "failures" (nodes getting inserted or deleted or communication links changing continuously) as part of the "normal" mode of operation rather than as exceptions. Second, time and communication constraints are much more severe, and hence it will be too expensive or even infeasible to run a static algorithm from scratch every time that the topology changes. Dynamic networks especially need efficient distributed algorithms, since unlike static networks, pre-processing (via centralized algorithms) is not usually possible. Furthermore, nodes typically have only local knowledge (which is also changing continuously with changing neighbours and links) which necessitates localized distributed algorithms. Hence a new theory is needed to understand and perform robust, efficient, and secure distributed computation in such systems.
展开▼
