Abstract
Device miniaturization is pointing towards tolerating imperfect hardware provided it is “good enough”. Software design theories will have to face the impact of such a trend sooner or later.
A school of thought in software design is relational: it expresses specifications as relations and derives programs from specifications using relational algebra.
This paper proposes that linear algebra be adopted as an evolution of relational algebra able to cope with the quantification of the impact of imperfect hardware on (otherwise) reliable software.
The approach is illustrated by developing a monadic calculus for component oriented software construction with a probabilistic dimension quantifying (by linear algebra) the propagation of imperfect behaviour from lower to upper layers of software systems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Backhouse, R., Michaelis, D.: Exercises in quantifier manipulation. In: Uustalu, T. (ed.) MPC 2006. LNCS, vol. 4014, pp. 69–81. Springer, Heidelberg (2006)
Barbosa, L.: Towards a Calculus of State-based Software Components. JUCS 9(8), 891–909 (2003)
Barbosa, L., Oliveira, J.: Transposing Partial Components — An Exercise on Coalgebraic Refinement. Theor. Comp. Sci. 365(1), 2–22 (2006), http://dx.doi.org/10.1016/j.tcs.2006.07.030
Beck, J.: Distributive laws. In: Eckmann, B. (ed.) Seminar on Triples and Categorical Homology Theory. Lecture Notes in Mathematics, vol. 80, pp. 119–140. Springer (1969)
Bird, R., de Moor, O.: Algebra of Programming. Series in Computer Science. Prentice-Hall International (1997)
Bonchi, F., Bonsangue, M., Boreale, M., Rutten, J., Silva, A.: A coalgebraic perspective on linear weighted automata. Inf. & Comp. 211, 77–105 (2012)
Brink, C., Kahl, W., Schmidt, G. (eds.): Relational methods in computer science. Springer-Verlag New York, Inc., New York (1997)
Coecke, B. (ed.): New Structures for Physics. Lecture Notes in Physics, vol. 831. Springer (2011)
Cortellessa, V., Grassi, V.: A modeling approach to analyze the impact of error propagation on reliability of component-based systems. In: Schmidt, H.W., Crnković, I., Heineman, G.T., Stafford, J.A. (eds.) CBSE 2007. LNCS, vol. 4608, pp. 140–156. Springer, Heidelberg (2007)
Erwig, M., Kollmansberger, S.: Functional pearls: Probabilistic functional programming in Haskell. J. Funct. Program. 16, 21–34 (2006)
Frias, M., Baum, G., Haeberer, A.: Fork algebras in algebra, logic and computer science. Fundam. Inform., 1–25 (1997)
Hasuo, I., Jacobs, B., Sokolova, A.: Generic trace semantics via coinduction. Logical Methods in Computer Science 3(4), 1–36 (2007)
Kahl, W.: Refinement and development of programs from relational specifications. ENTCS 44(3), 4.1–4.43 (2003)
Kerstan, H., König, B.: Coalgebraic trace semantics for probabilistic transition systems based on measure theory. In: Koutny, M., Ulidowski, I. (eds.) CONCUR 2012. LNCS, vol. 7454, pp. 410–424. Springer, Heidelberg (2012)
Kock, A.: Strong functors and monoidal monads. Archiv der Mathematik 23(1), 113–120 (1972), http://dx.doi.org/10.1007/BF01304852
Lingamneni, A., Enz, C., Palem, K., Piguet, C.: Synthesizing parsimonious inexact circuits through probabilistic design techniques. ACM Trans. Embed. Comput. Syst. 12(2s), 93:1–93:26 (2013)
Macedo, H., Oliveira, J.: Typing linear algebra: A biproduct-oriented approach. Science of Computer Programming 78(11), 2160–2191 (2013)
Marić, O., Sprenger, C.: Verification of a transactional memory manager under hardware failures and restarts (2013), conference paper (submitted)
McIver, A., Morgan, C.: Abstraction, Refinement and Proof for Probabilistic Systems. Monographs in Computer Science. Springer (2005)
Murta, D., Oliveira, J.N.: Calculating risk in functional programming. CoRR abs/1311.3687 (2013)
Oliveira, J.: Towards a linear algebra of programming. Formal Aspects of Computing 24(4-6), 433–458 (2012)
Oliveira, J.: Weighted automata as coalgebras in categories of matrices. Int. Journal of Found. of Comp. Science 24(06), 709–728 (2013)
Panangaden, P.: Labelled Markov Processes. Imperial College Press (2009)
Rutten, J.: Universal coalgebra: A theory of systems. Theor. Comp. Sci. 249(1), 3–80 (2000); Revised version of CWI Techn. Rep. CS-R9652 (1996)
Schmidt, G.: Relational Mathematics. Encyclopedia of Mathematics and its Applications, vol. 132. Cambridge University Press (November 2010)
Sokolova, A.: Probabilistic systems coalgebraically: A survey. Theor. Comput. Sci. 412(38), 5095–5110 (2011)
Stamatelatos, M., Dezfuli, H.: Probabilistic Risk Assessment Procedures Guide for NASA Managers and Practitioners, NASA/SP-2011-3421, 2nd edn (December 2011)
Tanaka, M.: Pseudo-Distributive Laws and a Unified Framework for Variable Binding. Ph.D. thesis, School of Informatics, University of Edinburgh (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Oliveira, J.N. (2014). Preparing Relational Algebra for “Just Good Enough” Hardware. In: Höfner, P., Jipsen, P., Kahl, W., Müller, M.E. (eds) Relational and Algebraic Methods in Computer Science. RAMICS 2014. Lecture Notes in Computer Science, vol 8428. Springer, Cham. https://doi.org/10.1007/978-3-319-06251-8_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-06251-8_8
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06250-1
Online ISBN: 978-3-319-06251-8
eBook Packages: Computer ScienceComputer Science (R0)