P-Grid is a truly decentralized structured P2P system for distributed information management beyond mere file-sharing which does not require central coordination or knowledge and it is based purely on randomized algorithms and local interactions.