Proxy assignments for filling gaps in wireless ad-hoc lattice computers

Tiziana Calamoneri, Emanuele G. Fusco, Anil M. Shende, Sunil M. Shende

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationStructural Information and Communication Complexity - 14th International Colloquium, SIROCCO 2007, Proceedings
PublisherSpringer Verlag
Pages208-221
Number of pages14
ISBN (Print)9783540729181
DOIs
StatePublished - 2007
Event14th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2007 - Castiglioncello, Italy
Duration: Jun 5 2007Jun 8 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4474 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other14th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2007
CountryItaly
CityCastiglioncello
Period6/5/076/8/07

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Proxy assignments for filling gaps in wireless ad-hoc lattice computers'. Together they form a unique fingerprint.

  • Cite this

    Calamoneri, T., Fusco, E. G., Shende, A. M., & Shende, S. M. (2007). Proxy assignments for filling gaps in wireless ad-hoc lattice computers. In Structural Information and Communication Complexity - 14th International Colloquium, SIROCCO 2007, Proceedings (pp. 208-221). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4474 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-72951-8_17