Proxy Assignments for Filling Gaps in Wireless Ad-hoc Lattice Computers

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 singlerow gaps and general row-column convex gaps, and present dilationoptimal, constant time algorithms for computing proxy assignments for single-row gaps and gaps that are rectangular in shape. © Springer-Verlag Berlin Heidelberg 2007.