Because many algorithms that process inputs for noisy data sources are already designed to tolerate noisy and missing data, it is possible (and useful) to provide programming language facilities to specify tolerable value deviations, value losses, and latency distortions.

 

M is a programming model and its embodiment in a language implementation, for systems composed of large numbers of failure-prone, resource-constrained ele- ments, interconnected in error-prone networks. The programming model enables partitioning without replication, of applications, across multiple devices with constrained memory resources. It permits programs to specify the amount of error (value deviation) tolerable in individual variables, as well as tolerable latencies and erasures on communications. The value deviation con- straints facilitate compile-time transformations for for- ward error correction; these transformations enable the value deviations in individual variables to be kept within program-specified bounds, in the presence of an assumed distribution of logic upsets in hardware. To account for situations in which such assumptions may be violated, language constructs enable the change of control-flow in response to tolerance constraint violations. The language model and implementation are targeted primarily at con- current failure-prone embedded systems, such as sensor networks..

 

Status: This is an ongoing project. It was dormant for several years because all our papers got rejected (we got many reviews along the lines of "The authors argue for specifying the kinds of hardware errors a program can tolerate with new programming language type annotations. Why would anyone want to do that??!!"). If you are interested in collaborating on some of the unsolved problems or applications, please get in touch!

Collaborations: This is joint work with Diana Marculescu (CMU).

 

Publications

  1. P. Stanley-Marbell. "Encoding Efficiency of Digital Number Representations under Deviation Constraints". Proceedings of the IEEE Information Theory Workshop, 2009.
  2. P. Stanley-Marbell. "A Programming Model and Language Implementation for Error-Tolerant Networks of Computation". Technische Universiteit Eindhoven, TU/e ES Tech Report, Number ESR-2008-03, 2008.
  3. P. Stanley-Marbell and D. Marculescu. "Deviation-Tolerant Computation in Concurrent Failure-Prone Hardware". Technische Universiteit Eindhoven, TU/e ES Tech Report, Number ESR-2008-01, 2008.
  4. P. Stanley-Marbell. "Encoding Efficiency Bounds for Digital Number Representations Under Value Deviation Constraints". Technische Universiteit Eindhoven, TU/e ES Tech Report, Number ESR-2008-02, 2008.
  5. P. Stanley-Marbell. "Programming Unreliable Networks of Computation". Ph.D. dissertation, Carnegie Mellon University, 2007.
  6. P. Stanley-Marbell and D. Marculescu. "A Programming Model and Language Implementation for Concurrent Failure-Prone Hardware". In Workshop on Programming Models for Ubiquitous Parallelism (PMUP 06), Seattle, WA.