  As a Distributed Hash Table (DHT), Skip Graph routing overlays are exploited
in several peer-to-peer (P2P) services, including P2P cloud storage. The fully
decentralized replication algorithms that are applicable to the Skip
Graph-based P2P cloud storage fail on improving the performance of the system
with respect to both the availability of replicas as well as their response
time. Additionally, they presume the system as homogeneous with respect to the
nodes' latency distribution, availability behavior, bandwidth, or storage. In
this paper, we propose Pyramid, which is the first fully decentralized utility-
and locality-aware replication approach for Skip Graph-based P2P cloud storage
systems. Pyramid considers the nodes as heterogeneous with respect to their
latency distribution, availability behavior, bandwidth, and storage. Pyramid is
utility-aware as it maximizes the average available bandwidth of replicas per
time slot (e.g., per hour). Additionally, Pyramid is locality-aware as it
minimizes the average latency between nodes and their closest replica. Our
simulation results show that compared to the state-of-the-art solutions that
either perform good in utility-awareness, or in locality-awareness, our
proposed Pyramid improves both the utility- and locality-awareness of replicas
with a gain of about 1.2 and 1.1 times at the same time, respectively.
