Matthias Kaiserswerth
IEEE/ACM Transactions on Networking
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.
Matthias Kaiserswerth
IEEE/ACM Transactions on Networking
Rafae Bhatti, Elisa Bertino, et al.
Communications of the ACM
Liat Ein-Dor, Y. Goldschmidt, et al.
IBM J. Res. Dev
B. Wagle
EJOR