An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
• 1995-1999  (2)
Collection
Publisher
Years
Year
• 1
Electronic Resource
Springer
Formal methods in system design 10 (1997), S. 93-125
ISSN: 1572-8102
Keywords: formal verification ; induction proofs ; formal methods ; homomorphic reduction ; modeling of distributed systems ; L-automata
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science
Notes: Abstract Modeling distributed computer systems is known to be a challenging enterprise. Typically, distributed systems are comprised of large numbers of components whose coordination may require complex interactions. Modeling such systems more often than not leads to the nominal intractability of the resulting state space. Various formal methods have been proposed to address the modeling of coordination among distributed systems components. For the most part, however, these methods do not support formal verification mechanisms. By way of contrast, the L-automata/L-processes model supports formal verification mechanisms which in many examples can successfully circumvent state space explosion problems, and allow verification proofs to be extended to an arbitrary number of components. After reviewing L-automata/L-processes formalisms, we present here the formal specification of a fault-tolerant algorithm for a distributed computer system. We also expose the L-automata/L-processes verification of the distributed system, demonstrating how various techniques such as homomorphic reduction, induction, and linearization, can be used to overcome various problems which surface as one models large, complex systems.
Type of Medium: Electronic Resource
Signatur Availability
Others were also interested in ...
• 2
Electronic Resource
Springer
Formal methods in system design 15 (1999), S. 175-199
ISSN: 1572-8102
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science
Notes: Abstract The I/O automaton paradigm of Lynch and Tuttle models asynchrony through an interleaving parallel composition. The recognition that such interleaving models in fact can be viewed as special cases of synchronous parallel composition has been very limited. Let $$\mathcal{A}$$ be any set of finite-state I/O automata drawing actions from a fixed finite set containing a subset Δ. In this article we establish a translation T : $$\mathcal{A} \to \mathcal{P}$$ to a class of ω-automata $$\mathcal{P}$$ closed under a synchronous parallel composition, for which T is monotonic with respect to implementation relative to Δ, and linear with respect to composition. Thus, for A1, ..., A, B1, ..., B ∈ $$\mathcal{A}$$ and A = A1 ‖...‖ A, B = B1 ‖...‖ B, if Δ is the set of actions common to both A and B, then A implements B (in the sense of I/O automata) if and only if the ω-automaton language containment $$\mathcal{L}$$ (T(A1) ⊗ ... ⊗ T(A)) ⊂ $$\mathcal{L}$$ (T(B1) ⊗ ... ⊗ T(B)) obtains, where ‖ denotes the interleaving parallel composition on $$\mathcal{A}$$ and ⊗ denotes the synchronous parallel composition on $$\mathcal{P}$$ . For the class $$\mathcal{P}$$ , we use the L-process model of ω-automata. This result enables one to verify systems specified by I/O automata through model-checkers such as COSPAN or SMV, that operate on models with synchronous parallel composition. The translation technique generalizes to other interleaving models, although in each case, the translation map must match the specific model.
Type of Medium: Electronic Resource
Signatur Availability
Others were also interested in ...
Close ⊗