  On-demand resource provisioning in cloud computing provides tailor-made
resource packages (typically in the form of VMs) to meet users' demands. Public
clouds nowadays provide more and more elaborated types of VMs, but have yet to
offer the most flexible dynamic VM assembly, which is partly due to the lack of
a mature mechanism for pricing tailor-made VMs on the spot. This work proposes
an efficient randomized auction mechanism based on a novel application of
smoothed analysis and randomized reduction, for dynamic VM provisioning and
pricing in geo-distributed cloud data centers. This auction, to the best of our
knowledge, is the first one in literature that achieves (i) truthfulness in
expectation, (ii) polynomial running time in expectation, and (iii)
$(1-\epsilon)$-optimal social welfare in expectation for resource allocation,
where $\epsilon$ can be arbitrarily close to 0. Our mechanism consists of three
modules: (1) an exact algorithm to solve the NP-hard social welfare
maximization problem, which runs in polynomial time in expectation, (2) a
perturbation-based randomized resource allocation scheme which produces a VM
provisioning solution that is $(1-\epsilon)$-optimal, and (3) an auction
mechanism that applies the perturbation-based scheme for dynamic VM
provisioning and prices the customized VMs using a randomized VCG payment, with
a guarantee in truthfulness in expectation. We validate the efficacy of the
mechanism through careful theoretical analysis and trace-driven simulations.
