In this paper, we provide a novel efficient Distributed Multiple Replicas Data Possession Checking (DMRDPC) scheme
to validate the availability and data integrity in the cloud computing environment. In the DMRDPC scheme, the problem of
Finding an Optimal Spanning Tree in a Complete Bidirectional Directed Graph (the FOSTCBDG problem) is vital, since the optimal spanning tree can be used to improve communication efficiency by optimizing the partial order of scheduling multiple
replicas data possession checking. Particularly, on the Internet, data routing often aims to minimize the number of hops; but
in a clouds environment, multi-hop among clouds may be more efficient than a single hop. With the increasing number of
clouds, the FOSTCBDG problem is becoming more and more critical to improve the performance of cloud computing. Thus,
we provide basic theories for the FOSTCBDG problem. We also propose an efficient Replace the Smallest Bandwidth Edge
(RSBE) algorithm to approximately resolve the FOSTCBDG problem. The effectiveness of our proposed DMRDPC is validated
by an experimental study, where bandwidths of a CBDG are simulated by checking the download speeds of several Google
websites from the non-Google clouds at multiple locations around the world.
JCSS Special Issue: Cloud Computing 2011