The term Autonomic Communication (AC) refers to self-managing systems which are capable of supporting self-configuration, self-healing and self-optimization. However, information reflection and collection, lack of centralized control, non-cooperation and so on are just some of the challenges within AC systems. We have considered these problems in theory and practice and reached the following conclusion; in order to build an ideal system for autonomic communication, there are three key problems to be solved. Motivated by the need for AC, we have designed an efficient and low-cost Peer-to-Peer (P2P) overlay called Maya-Pyramid overlay (MPO) and combined merits of unstructured P2P with those of structured P2P overlays. Differing from the traditional hierarchical P2P (i.e. tree-like structure) overlay, (1) MPO is composed of levels and layers, which uses small world characteristic to improve efficiency, and the maintenance cost is decreased because update and backup only take place in two neighboring levels or layers instead of recursively perform in higher levels. (2) Unlike normal redundant mechanisms for solving the single fault problem: Tri-Information Center (Tri-IC) mechanism is presented in order to improve robustness by alleviating the load of cluster heads in a hierarchical P2P overlay. (3) A source ranking mechanism is proposed in order to discourage free riding and whitewashing and to encourage frequent information exchanges between peers. (4) Inspired by Pastry's ID structure for a structured DHT algorithm, a 3D unique ID structure is presented in the unstructured P2P overlay. This will guarantee anonymity in routing, and will be, not only more efficient because it applies the DHT-like routing algorithm in the unstructured P2P overlay, but also more adaptive to suit AC. Evaluation proved that MPO is robust, highly efficient and of a low-cost.