P2PImpulse - Fully Decentralized Estimation of Global Properties of Peer-to-Peer Networks

A peer-to-peer system is essentially a network of applications used to communicate and share resources. The nodes in this network, generally called "peers," are typically interconnected through point-to-point overlay links. A fundamental feature of peer-to-peer networks is that each peer maintains only a local view of the network. Although this absence of a centralized point of control is very advantageous, sometimes it is still necessary or desirable that peers be able to measure some global properties of the network. The general goal of this project is to study ways to measure some global properties of a peer-to-peer network in a completely decentralized and efficient manner. Specifically, we propose to study properties of peer-to-peer networks that can be derived from the spectrum of the network. By spectrum of the network we mean the eigenvalues of a chosen descriptive matrix closely related to the adjacency matrix of the network graph. For example, the mixing time of a network -- the minimal length of a random walk necessary to obtain a desired approximation of the asymptotic visitation probabilities -- can be derived from the second eigenvalue of the transition-probability matrix. The starting point of this research is the intuition that each peer in a network can, with a simple efficient and fully decentralized algorithm, compute the impulse response of a particular linear dynamic system whose state-transformation matrix corresponds to the chosen descriptive matrix derived from the network graph. In other words, a peer can not see or use the whole network graph (efficiently) but can compute the impulse response of a dynamic system whose behavior is defined by the structure of that graph. The impulse response can then be used to compute the desired salient spectral properties of the network graph by applying well-established identification and realization techniques developed within the theory of dynamic systems. In general, a complete and exact identification would require a very large number of steps of the impulse response (at least n for a network of n peers). However, a much shorter, truncated impulse response might still reveal useful information, as it could effectively distill the dominant properties of the network. In synthesis, we view a peer-to-peer network as a large linear dynamic system whose impulse response can be computed efficiently, and we propose to research the applicability of system-identification theory to estimate some global properties of the network.