(1 + ε)-approximate sparse recovery
Eric Price, David P. Woodruff
FOCS 2011
An implementation of a shared object O is t-tolerant if the object remains correct and wait-free even when up to t base objects (objects used in the implementation of O) fail. The implementation is gracefully degrading if, no matter how many base objects fail, O does not fail more severely than its base objects. For the omission failure mode, we derive a lower bound on the space complexity of a gracefully degrading t-tolerant implementation. This result lets us conclude that, for omission failures, graceful degradation can be achieved only at the cost of increased space complexity.
Eric Price, David P. Woodruff
FOCS 2011
Lixi Zhou, Jiaqing Chen, et al.
VLDB
Michael Ray, Yves C. Martin
Proceedings of SPIE - The International Society for Optical Engineering
Robert G. Farrell, Catalina M. Danis, et al.
RecSys 2012