Formalization and correctness of the PALS architectural pattern for distributed real-time systems

José Meseguer, Peter Csaba Ölveczky

Research output: Contribution to journalArticle

Abstract

Many Distributed Real-Time Systems (DRTSs), such as integrated modular avionics systems and distributed control systems in motor vehicles, are made up of a collection of components communicating asynchronously among themselves and with their environment that must change their state and respond to environment inputs within hard real-time bounds. Such systems are often safety-critical and need to be certified; but their certification is currently hard due to their distributed nature. The Physically Asynchronous Logically Synchronous (PALS) architectural pattern can greatly reduce the design and verification complexities of achieving virtual synchrony in a DRTS. This work presents a formal specification of PALS as a formal model transformation that maps a synchronous design, together with a set of performance bounds of the underlying infrastructure, to a formal DRTS specification that is semantically equivalent to the synchronous design. This semantic equivalence is proved, showing that the formal verification of temporal logic properties of the DRTS in CTL * can be reduced to their verification on the much simpler synchronous design. An avionics system case study is used to illustrate the usefulness of PALS for formal verification purposes.

Original languageEnglish (US)
Pages (from-to)1-37
Number of pages37
JournalTheoretical Computer Science
Volume451
DOIs
StatePublished - Sep 14 2012

Keywords

  • Distributed real-time systems
  • Formally verified architectural patterns
  • Model checking
  • Rewriting logic
  • Synchronizers

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Formalization and correctness of the PALS architectural pattern for distributed real-time systems'. Together they form a unique fingerprint.

  • Cite this