This paper describes our Gnutella compatible P2P system Gridella which is based on the P-Grid approach. P-Grid has several advantages over the standard Gnutella infrastructure, for example, that probabilistic estimates can be given for successful search requests and that it scales gracefully in the total number of nodes and data items. Gridella is designed for interoperability with Gnutella and the long-term goal is to replace the existing Gnutella infrastructure with Gridella to make it more self-organizing and get around known problems of Gnutella. On the basis of an analysis of Gnutella we describe the P-Grid approach and the mapping algorithm that form the algorithmic foundations of Gridella. We present Gridella’s architecture and communication patterns and compare it with Gnutella.