To address privacy concerns in Online Social Networks (OSNs), we propose to use a distributed, peer-to-peer approach coupled with encryption. To verify the feasibility of such an approach, we designed a two-tiered architecture and protocols that recreate the core features provided by OSNs in a decentralized way. This paper focuses on the description of the prototype built for the P2P infrastructure (as a first step without the encryption part) for social networks and shares early experiences from the prototype and insights gained since first outlining the challenges and possibilities of decentralized alternatives to OSNs.