This paper studies the consensus problem of multi-agent systems with nonuniform time-delays and dynamically changing topologies. A linear consensus protocol is introduced to realize local control strategies for these second-order discrete-time agents. By model transformations and applying the properties of nonnegative matrices, sufficient conditions are derived for state consensus of the systems. It is shown that arbitrary bounded time-delays can safely be tolerated, even though the communication structures between agents dynamically change over time and the corresponding directed graphs may not have spanning trees. Finally, a numerical example is included to illustrate the obtained results. Crown Copyright (C) 2009 Published by Elsevier Ltd. All rights reserved.