Sorting on a Mesh-Connected Computer with Delaying Links

A mesh-connected processor array is considered in which the links are faulty in the following sense: Each attempt by two neighboring processors to communicate by exchanging messages may fail with some constant probability. A message sent across a link and not delivered is said to be delayed by the link. It is assumed that all the links delay with the same fixed delay probability, independently of each other. The problem of sorting is addressed in this model. It is proved that an $n \times n$ mesh can be sorted in the expected time $O( n )$ with large probability. More precisely, it is shown that there are two constants $c > 0$ and $r > 1$, depending on the delay probability, such that the $n \times n$ mesh is sorted in time $cn + t$ with the probability at least $1 - r^{ - t} $. One specific algorithm is considered, but the analysis shows that many known algorithms could sort in the expected time $O( n )$, after some natural modifications.