Algorithmic performance in large scale distributed networks:
1Complex distributed networks like the Internet, the World Wide Web, peer-to-peer systems, and even biological networks appear in applications driving today`s technology. The main focus of my work is in relating the performance of basic network communication tasks to structural characteristics of such networks, and developing protocols that reinforce and exploit such characteristics. In particular, in this talk we relate searching and topology maintenance in peer-to-peer networks to the conductance and the spectrum of the underlying graph (which, in turn, measure good global connectivity). We compare the performance of the traditional method of searching by flooding to searching by random walks and further hybrid schemes. We isolate cases of practical interest, such as clustered and dynamic network topologies, where the latter have superior performance. The improvement in the performance can be directly quantified in terms of the conductance of the underlying graph. We propose new protocols for maintaining peer-to-peer networks with good conductance and low network overhead.