Abstract : Arigatoni is a structured multi-layer overlay network that provides various services with variable guarantees, and promotes an intermittent participation in the overlay because peers can appear, disappear, and organize themselves dynamically. Arigatoni provides a very powerful decentralized, asyn-chronous, and scalable resource discovery mechanism within an overlay with a dynamic network topology. In the first version of Arigatoni, the network topology was tree-or forest-based. This paper makes a significant step by weaving the network topology with general dynamic graph properties. As an immediate consequence, the Arigatoni protocols must be reconsidered in order to take into accounts routing loops when updating routing tables, for dealing with resource overbooking, and resource discovery loops.