Abstract
The Abstract State Machine (ASM) formalism has proved an effective and durable foundation for the formal semantics of SDL. The distributed ASMs that underpin the SDL semantics are defined in terms of agents that execute ASM programs concurrently, acting on partial views of a global state. The discrete identities of successive global states are ensured by allowing input from the external world only between steps, and by having all agents refer to an external global time. But distributed systems comprising independent agents do not have a natural global time. Nor do they have natural global states. This paper takes well-known concepts from relativity and applies them to ASMs. The spacetime in which an ASM exists and moves is defined, and some properties that must be preserved by transformations of the frame of reference of an ASM are identified. Practical implications of this approach are explored through reservation and web service examples.
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
Gurevich, Y.: Evolving Algebras 1993: Lipari Guide. In: Specification and Validation Methods, pp. 9–36. Oxford University Press (1995)
G.Y.: Evolving Algebras 1993. Lipari Guide, 2005 version with table of contents and footnote, http://research.microsoft.com/en-us/um/people/gurevich/opera/103.pdf
Börger, E., Stärk, R.: Abstract State Machines – a Method for High-Level System Design and Analysis. Springer (2003)
Börger, E.: The ASM Refinement Method. Formal Aspects of Computing 15, 237–257 (2003)
Blass, A., Gurevich, Y.: Abstract State Machines Capture Parallel Algorithms. ACM Transactions on Computational Logic 4(4), 578–651 (2003)
Blass, A., Gurevich, Y.: Abstract State Machines Capture Parallel Algorithms: Correction and Extension. ACM Transactions on Computational Logic 9(3), Article 19 (2008)
Glässer, U., Gurevich, Y., Veanes, M.: Abstract Communication Model for Distributed Systems. IEEE Transactions on Software Engineering 30(7) (2004)
Glausch, A., Reisig, W.: Distributed Abstract State Machines and Their Expressive Power. Humboldt University Berlin (2006)
Glausch, A., Reisig, W.: An ASM-Characterization of a Class of Distributed Algorithms. In: Abrial, J.-R., Glässer, U. (eds.) Rigorous Methods for Software Construction and Analysis. LNCS, vol. 5115, pp. 50–64. Springer, Heidelberg (2009)
Börger, Cisternino, A., Gervasi, V.: Ambient Abstract State Machines with applications. Journal of Computer and System Sciences 78(3), 939–959 (2011)
Blass, A., Gurevich, Y.: Persistent Queries in the Behavioral Theory of Algorithms. ACM Transactions on Computational Logic 12(2), Article 16 (2011)
International Telecommunication Union (ITU): Recommendation Z.100 Annex F1 (11/00) SDL formal definition – General overview. http://www.itu.int/rec/T-REC-Z.100-200011-S!AnnF1/en
Glässer, U., Gotzhein, R., Prinz, A.: The formal semantics of SDL-2000: Status and perspectives. Computer Networks 42, 343–358 (2003)
Blass, A., Gurevich, Y.: Ordinary Interactive Small-Step Algorithms – I. ACM Transactions on Computational Logic 7(2), 363–419 (2006)
International Telecommunication Union (ITU): Recommendation Z.101 (12/11) – Specification and Description Language - Basic SDL-2010 (2010) http://www.itu.int/rec/T-REC-Z.101-201112-I/en
Norton, J.D.: General Covariance and the foundations of general relativity– eight decades of dispute. Reports on Progress in Physics 56(7), 791–858 (1993)
Graf, S., Prinz, A.: Time in State Machines. Fundamenta Informaticae, 77(1-2), 143–174 (2007)
WSDL and UDDI, http://www.w3schools.com/wsdl/wsdl_uddi.asp
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sherratt, E. (2013). Relativity and Abstract State Machines. In: Haugen, Ø., Reed, R., Gotzhein, R. (eds) System Analysis and Modeling: Theory and Practice. SAM 2012. Lecture Notes in Computer Science, vol 7744. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36757-1_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-36757-1_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36756-4
Online ISBN: 978-3-642-36757-1
eBook Packages: Computer ScienceComputer Science (R0)