Summary: Lattice basis reduction is an important problem in the geometry of numbers with applications in combinatorial optimization, computer algebra, and cryptography. The well-known sequential LLL algorithm finds a short vector in \(O(n^{4}\log B)\) arithmetic operations on integers having binary length \(O(n \log B)\), where \(n\) denotes the dimension of the lattice and \(B\) denotes the maximum \(L_{2}\) norm of the initial basis vectors. In this paper a new analysis of the parallel algorithm of Roch and Villard is presented. It is shown that on an \(n\times n\) mesh it needs \(O(n^{2}\log B)\) arithmetic operations on integers having binary length \(O(n\log B)\). This improves the previous analysis and shows that an asymptotical speedup of \(n^{2}\) is possible using \(n^{2}\) processors.