Static Typing for a Faulty Lambda Calculus Export

@inproceedings{citeulike:4071646, abstract = {A transient hardware fault occurs when an energetic particle strikes a transistor, causing it to change state. These faults do not cause permanent damage, but may result in incorrect program execution by altering signal transfers or stored values. While the likelihood that such transient faults will cause any significant damage may seem remote, over the last several years transient faults have caused costly failures in high-end machines at America Online, eBay, and the Los Alamos Neutron Science Center, among others [6, 44, 15]. Because susceptibility to transient faults is proportional to the size and density of transistors, the problem of transient faults will become increasingly important in the coming decades.This paper defines the first formal, type-theoretic framework for studying reliable computation in the presence of transient faults. More specifically, it defines λzap, a lambda calculus that exhibits intermittent data faults. In order to detect and recover from these faults, λzap programs replicate intermediate computations and use majority voting, thereby modeling software-based fault tolerance techniques studied extensively, but informally [10, 20, 30, 31, 32, 33, 41].To ensure that programs maintain the proper invariants and use λzap primitives correctly, the paper defines a type system for the language. This type system guarantees that well-typed programs can tolerate any single data fault. To demonstrate that λzap can serve as an idealized typed intermediate language, we define a type-preserving translation from a standard simply-typed lambda calculus into λzap.}, address = {New York, NY, USA}, author = {Walker, David and Mackey, Lester and Ligatti, Jay and Reis, George A. and August, David I.}, booktitle = {ICFP '06: Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming}, citeulike-article-id = {4071646}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1159803.1159809}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1159803.1159809}, citeulike-linkout-2 = {http://www.cs.princeton.edu/~dpw/papers/lambdazap-icfp06.pdf}, doi = {10.1145/1159803.1159809}, isbn = {1-59593-309-3}, keywords = {fault-tolerance, lambda-calculus, static-checking, type-checking, type-safety}, location = {Portland, Oregon, USA}, pages = {38--49}, posted-at = {2009-05-06 11:18:00}, priority = {2}, publisher = {ACM}, title = {Static Typing for a Faulty Lambda Calculus}, url = {http://dx.doi.org/10.1145/1159803.1159809}, year = {2006} }

TY - CONF ID - citeulike:4071646 L3 - citeulike-article-id:4071646 N2 - A transient hardware fault occurs when an energetic particle strikes a transistor, causing it to change state. These faults do not cause permanent damage, but may result in incorrect program execution by altering signal transfers or stored values. While the likelihood that such transient faults will cause any significant damage may seem remote, over the last several years transient faults have caused costly failures in high-end machines at America Online, eBay, and the Los Alamos Neutron Science Center, among others [6, 44, 15]. Because susceptibility to transient faults is proportional to the size and density of transistors, the problem of transient faults will become increasingly important in the coming decades.This paper defines the first formal, type-theoretic framework for studying reliable computation in the presence of transient faults. More specifically, it defines λzap, a lambda calculus that exhibits intermittent data faults. In order to detect and recover from these faults, λzap programs replicate intermediate computations and use majority voting, thereby modeling software-based fault tolerance techniques studied extensively, but informally [10, 20, 30, 31, 32, 33, 41].To ensure that programs maintain the proper invariants and use λzap primitives correctly, the paper defines a type system for the language. This type system guarantees that well-typed programs can tolerate any single data fault. To demonstrate that λzap can serve as an idealized typed intermediate language, we define a type-preserving translation from a standard simply-typed lambda calculus into λzap. CY - Portland, Oregon, USA SN - 1-59593-309-3 AD - New York, NY, USA EP - 49 TI - Static Typing for a Faulty Lambda Calculus PB - ACM T2 - ICFP '06: Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming SP - 38 KW - fault-tolerance KW - lambda-calculus KW - static-checking KW - type-checking KW - type-safety AU - Walker, David AU - Mackey, Lester AU - Ligatti, Jay AU - Reis, George AU - August, David PY - 2006/// UR - http://dx.doi.org/10.1145/1159803.1159809 ER -