Fully Decentralized Estimation of Some Global Properties of a Network
It is often beneficial to architect networks and overlays as fully decentralized systems, in the sense that any computation (e.g., routing or search) would only use local information, and no single node would have a complete view or control over the whole network. Yet sometimes it also important to compute global properties of the network. In this paper, the authors propose a fully decentralized algorithm to compute some global properties that can be derived from the spectrum of the network. More specifically, they compute the most significant eigen-values of a descriptive matrix closely related to the adjacency matrix of the network graph.