Probabilistic models and efficient algorithms for certain large-scale distributed networks

Abstract

Two common topological features have been empirically reported in real-world large-scale distributed networks, such as the Internet, Web and peer-to-peer networks. They are, namely, (a) the small-world phenomenon where any pair of nodes in the network can be connected by a short chain of intermediates, and (b) the scale-free connectivity pattern where the node degrees follow a power law distribution. Modelling these distributed networks can help understand their growth mechanisms and exploit other useful characteristics for applications. However, most existing models are far from being satisfactory in that they all depend on unrealistic assumptions, e.g., each node is supposed to know about the entire network. My research aims to develop effective models that are more suitable for constructing real-world distributed systems.