The algebraic connectivity of the graph Laplacian plays an essential role in various multi-agent control systems. In many cases a lower bound of this algebraic connectivity is necessary in order to achieve a certain performance. Lately, several methods based on distributed Power Iteration have been proposed for computing the algebraic connectivity of a symmetric Laplacian matrix. However, these methods cannot give any lower bound of the algebraic connectivity and their convergence rates are often unclear. In this paper, we present a distributed algorithm for estimating the algebraic connectivity for undirected graphs with symmetric Laplacian matrices. Our method relies on the distributed computation of the powers of the adjacency matrix and its main interest is that, at each iteration, agents obtain both upper and lower bounds for the true algebraic connectivity. Both bounds successively approach the true algebraic connectivity with the convergence speed no slower than O(1/k). (C) 2014 Elsevier Ltd. All rights reserved.