This paper shows that self-timed meshes can achieve linear speed-up. The per-processor performance of a mesh is the average number of operations per processor per unit time. For synchronous processors, it has been shown that the per-processor performance of a mesh goes to zero as the size of the mesh goes to infinity. This paper shows that for self-timed meshes, the per-processor performance can be bounded below by a positive constant. Thus, self-timed meshes are asymptotically faster than synchronous ones. Furthermore, simulation and analytic results are used to show that analysis based solely on average case times can be optimistic and lead to poor design decisions.