More Web Proxy on the site http://driver.im/

research-article

Specifying Graceful Degradation

Authors:

J. M. WingAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 2, Issue 1

Pages 93 - 104

https://doi.org/10.1109/71.80192

Published: 01 January 1991 Publication History

Abstract

A description is given of the relaxation lattice method, a new approach to specifyinggraceful degradation for a large class of programs. A relaxation lattice is a lattice ofspecifications parameterized by a set of constraints, where the stronger the set ofconstraints, the more restrictive the specification. While a program is able to satisfy itsstrongest set of constraints, it satisfies its preferred specification, but if changes to theenvironment force it to satisfy a weaker set, then it will permit additional weaklyconsistent computations which are undesired but tolerated. The use of relaxation latticesis illustrated by specifications for programs that tolerate (1) faults, such as site crashesand network partitions, (2) timing anomalies, such as attempting to read a value too soonafter it was written, (3) synchronization conflicts, such as choosing the oldest unlockeditem from a queue, and (4) security breaches, such as acquiring unauthorized capabilities.

References

[1]

{1} M. Ahamad and M.H. Ammar, "Performance characterization of quorum-consensus algorithms for replicated data," Tech. Rep. GITICS-86/23, School of Inform. and Comput. Sci., Georgia Institute of Technol., Sept. 1986.

[2]

{2} D.E. Bell and L. J. LaPadula, "Secure computer systems: Unified exposition and multics interpretation," Tech. Rep. ESD-TR-75-306, The MITRE Corp., Bedford, MA, Mar. 1976.

[3]

{3} P. A. Bernstein and N. Goodman, "The failure and recovery problem for replicated databases," in Proc. 2nd ACM SIGACT-SIGOPS Symp. Principles Distributed Comput., Montreal, P.Q., Canada, 1983.

[4]

{4} K. P. Birman, "Replication and fault-tolerance in the isis system," in Proc. 10th Symp. Oper. Syst. Principles, Dec. 1985. Also TR 85-668, Cornell Univ. Comput. Sci. Dep.

[5]

{5} A. D. Birrell, R. Levin, R. Needham, and M. Schroeder, "Grapevine: An exercise in distributed computing," Commun. ACM, vol. 25, no. 14, pp. 260-274, Apr. 1982.

Digital Library

[6]

{6} J. Chang and N. F. Maxemchuk, "Reliable broadcast protocols," ACM Trans. Comput. Syst., vol. 2, no. 3, pp. 251-273, Aug. 1984.

Digital Library

[7]

{7} F. Cristian, "A rigorous approach to fault-tolerant system development," Tech. Rep. RJ 4008, IBM Res. Lab., Sept. 1983.

[8]

{8} I. Durham and M. Shaw, "Specifying reliability as a software attribute," Tech. Rep. CS-82-148, Carnegie-Mellon Univ., Dec. 1982.

[9]

{9} K.P. Eswaran, J.N. Gray, R.A. Lorie, and I.L. Traiger, "The notion of consistency and predicate locks in a database system," Commun. ACM, vol. 19, no. 11, pp. 624-633, Nov. 1976.

Digital Library

[10]

{10} M. Fischer and A. Michael, "Sacrificing serializability to attain high availability of data in an unreliable-network," in proc. ACM SIGACT-SIGMOD Symp. Principles Database Syst., Mar. 1982.

[11]

{11} H. Garcia-Molina, "Using semantic knowledge for transaction processing in a distributed-database," ACM Trans. Database Syst., vol. 8, no. 2, pp. 186-213, June 1983.

Digital Library

[12]

{12} D. K. Gifford, "Weighted voting for replicated data," in Proc. Seventh Symp. Oper. Syst. Principles, ACM SIGOPS, Dec. 1979.

[13]

{13} J. Gray, Notes on Database Operating Systems. Berlin, Germany: Springer-Verlag, 1978, pp. 393-481.

Digital Library

[14]

{14} J. V. Guttag, J. J. Horning, and J. M. Wing, "The Larch family of specification languages," IEEE Softwure, vol. 2, no. 5, pp. 24-36, Sept. 1985.

Digital Library

[15]

{15} J. V. Guttag, J. J. Horning, and J. M. Wing, "Larch in five easy pieces," Tech. Rep. 5, DEC Systems Research Center, July 1985.

[16]

{16} M. P. Herlihy, "A quorum-consensus replication method for abstract data types," ACM Trans. Comput. Syst., vol. 4, no. 1, Feb. 1986.

Digital Library

[17]

{17} M. P. Herlihy and J. M. Wing, "Specifying graceful degradation in distributed systems," in Proc. Sixth ACM SIGACT-SIGOPS Symp. Principles Distributed Comput. (PODC), Aug. 1987. Also CMU-CS-87-120.

[18]

{18} S. Khosla, T. S. E. Maibaum, and M. Sadler, "Large database specifications from small views," in Proc. Fifth Conf. Foundations software Technol. Theoret. Comput. Science (LNCS 206). Berlin, Germany: Springer-Verlag, 1985, pp. 246-271.

Digital Library

[19]

{19} L. Lambort, "Time, clocks, and the ordering of events in a distributed system," Commun. ACM, vol. 21, no. 7, pp. 558-565, July 1978.

Digital Library

[20]

{20} L. Lambort, "A simple approach to specifying concurrent systems," Commun. ACM, vol. 32, no. 1, pp. 32-45, Jan. 1989.

Digital Library

[21]

{21} B. W. Lampson, "Protection," ACM Oper. Syst. Rev., vol. 19, no. 5, pp. 13-24, Dec. 1985.

[22]

{22} B. Liskov and R. Scheifler, "Guardians and actions: Linguistic support for robust, distributed programs," Trans. Programming languages Syst., vol. 5, no. 3, pp. 381-404, July 1983.

Digital Library

[23]

{23} B. H. Liskov and W.E. Weihl, "Specifications of distributed programs," Distributed Comput., vol. 1, no. 2, pp. 102-118, Apr. 1986.

[24]

{24} G. J. Popek, B. Walker, J. Chow, D. Edwards, C. Kline, G. Rudisin, and G. Thiel, "Locus: A network transparent high reliability distributed system," in Proc. Eighth Symp. Oper. Syst. Principles, Dec. 1981.

Digital Library

[25]

{25} P. M. Schwarz and A. Z. Spector, "Synchronizing shared abstract types," ACM Trans. Comput. Syst., vol. 2, no. 3, pp. 223-250, Aug. 1984.

Digital Library

[26]

{26} W.E. Weihl, "Specification and implementation of atomic data types," Tech. Rep. TR-314, MIT Lab. for Comput. Sci., Mar. 1984.

[27]

{27} W.E. Weihl and B.H. Liskov, "Specification and implementation of resilient, atomic data types," in Proc. SIGPLAN Symp. Programming Language Issues in Sofrware Syst., June 1983.

[28]

{28} J. M. Wing, "A two-tiered approach to specifying programs," Tech. Rep. MIT-LCS-TR-299, MIT Lab. for Comput. Sci., June 1983.

[29]

{29} J. M. Wing, "A specifier's introduction to formal methods," IEEE Comput. Mag., Sept. 1990.

Cited By

Kang EGanlath AMishra SBaiduc FAmmar N(2024)Contract-Driven Runtime AdaptationNASA Formal Methods10.1007/978-3-031-60698-4_17(298-313)Online publication date: 4-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-60698-4_17
Palacios Abad BKoohang MVigil-Hayes MZegura E(2023)Alone and Together: Resilience in a Fluid Socio-Technical-Natural SystemProceedings of the ACM on Human-Computer Interaction10.1145/35794577:CSCW1(1-26)Online publication date: 16-Apr-2023
https://dl.acm.org/doi/10.1145/3579457
Weiss PSteinhorst S(2023)Predictable timing behavior of gracefully degrading automotive systemsDesign Automation for Embedded Systems10.1007/s10617-023-09271-x27:1-2(103-138)Online publication date: 11-Apr-2023
https://dl.acm.org/doi/10.1007/s10617-023-09271-x
Show More Cited By

Recommendations

Graceful Degradation in Algorithm-Based Fault Tolerant Multiprocessor Systems

Algorithm-based fault tolerance (ABFT) is a technique which improves the reliability of a multiprocessor system by providing concurrent error detection and fault location capability to it. It encodes data at the system level and modifies the algorithm ...
Designing masking fault-tolerance via nonmasking fault-tolerance
SRDS '95: Proceedings of the 14TH Symposium on Reliable Distributed Systems

Masking fault-tolerance guarantees that programs continually satisfy their specification in the presence of faults. By way of contrast, nonmasking fault-tolerance does not guarantee as much: it merely guarantees that when faults stop occurring, program ...
Formal methods for the validation of fault tolerance in autonomous spacecraft
FTCS '96: Proceedings of the The Twenty-Sixth Annual International Symposium on Fault-Tolerant Computing (FTCS '96)

One of the major challenges to be faced in the design of new-generation spacecrafts comes with the requirement to increase the capacity of autonomous operation, in particular in presence of abnormal events. Formal methods are becoming more accepted in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 2, Issue 1

January 1991

126 pages

ISSN:1045-9219

Issue’s Table of Contents

Copyright © Copyright © 1991 IEEE. All Rights Reserved.

Publisher

IEEE Press

Publication History

Published: 01 January 1991

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kang EGanlath AMishra SBaiduc FAmmar N(2024)Contract-Driven Runtime AdaptationNASA Formal Methods10.1007/978-3-031-60698-4_17(298-313)Online publication date: 4-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-60698-4_17
Palacios Abad BKoohang MVigil-Hayes MZegura E(2023)Alone and Together: Resilience in a Fluid Socio-Technical-Natural SystemProceedings of the ACM on Human-Computer Interaction10.1145/35794577:CSCW1(1-26)Online publication date: 16-Apr-2023
https://dl.acm.org/doi/10.1145/3579457
Weiss PSteinhorst S(2023)Predictable timing behavior of gracefully degrading automotive systemsDesign Automation for Embedded Systems10.1007/s10617-023-09271-x27:1-2(103-138)Online publication date: 11-Apr-2023
https://dl.acm.org/doi/10.1007/s10617-023-09271-x
Neubert MYoder JGuerra EManns M(2022)Leading a Software Architecture Revolution - "Part 1: Creating Awareness, Preparing and Measuring"Proceedings of the 29th Conference on Pattern Languages of Programs10.5555/3631672.3631699(1-58)Online publication date: 24-Oct-2022
https://dl.acm.org/doi/10.5555/3631672.3631699
Zhang CWagner ROrvalho PGarlan DManquinho VMartins RKang ESpinellis DGousios GChechik MDi Penta M(2021)AlloyMax: bringing maximum satisfaction to relational specificationsProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468587(155-167)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468587
Lin YKulkarni SJhumka A(2019)Automation of fault-tolerant graceful degradationDistributed Computing10.1007/s00446-017-0319-x32:1(1-25)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s00446-017-0319-x
Hajisheykhi RRoohitavaf MKulkarni S(2017)Bounded Auditable Restoration of Distributed SystemsIEEE Transactions on Computers10.1109/TC.2016.259557866:2(240-255)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1109/TC.2016.2595578
Gupta PSchaetz B(2016)Constraint-based graceful degradation in smart gridsProceedings of the 2nd International Workshop on Software Engineering for Smart Cyber-Physical Systems10.1145/2897035.2897043(8-14)Online publication date: 14-May-2016
https://dl.acm.org/doi/10.1145/2897035.2897043
Ebnenasir AKulkarni S(2011)Feasibility of Stepwise Design of Multitolerant ProgramsACM Transactions on Software Engineering and Methodology10.1145/2063239.206324021:1(1-49)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1145/2063239.2063240
Saridakis T(2009)Design patterns for graceful degradationTransactions on Pattern Languages of Programming I10.5555/2172302.2172305(67-93)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.5555/2172302.2172305
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents