Abstract: On the basis of the low-rank characteristic of the Internet latency matrix, the in-complete latency matrix completion problem in full-decentralized environment is studied through setting a priori estimation of the l0 norm of this matrix. First, the problem is componentized into a couple of convex optimization problems, thus it can be solved by alternative direction method. Then, to achieve low computation cost along with well generalization, an Adaptive Distributed Matrix Completion (ADMC) algorithm is proposed. ADMC doubles the upper-bound of the iterative step size searching area, and introduces several kinds of loss functions as the latency estimation error measures. Experiments show that, without losing any accuracy, ADMC reduces the computation cost significantly without any additional measurement or communication cost, and the introduced various loss functions also improve the robustness of the algorithm.