The proliferation of cheap portable, wireless computing devices (e.g., cell phones and PDAs) promises the availability of
a large number of computing devices in a relatively small geographic region. Researchers have proposed using such an ensemble
of wireless devices to create a wireless ad-hoc lattice computer (WAdL) to harness the collective computing capabilities of
the devices for the common cause of scientific computing via analogical simulations. Faulty devices or lack of wireless coverage
leads to “gaps” in a WAdL, rendering it ineffective for analogical simulations.
In this paper we discuss our soultion to the problem of bridging gaps in WAdLs by assigning active devices on the perimeter
of the gap as proxies for the defective devices in the gap. We establish lower bounds on the communication dilation witnessed
by such proxy assignments for single-row gaps and general row-column convex gaps, and present dilation-optimal, constant time
algorithms for computing proxy assignments for single-row gaps and gaps that are rectangular in shape.
This research was supported, in part, by the European Research Project Algorithmic Principles for Building Efficient Overlay Computers (AEOLUS). Most of the work reported here was performed while Professor A. Shende visited the Department of Computer Science,
University of Rome “La Sapienza”. Support through a Visiting Fellowship from the University of Rome “La Sapienza” is gratefully
acknowledged.