Reasoning about layered message passing systems
โ Scribed by B. Meenakshi; R. Ramanujam
- Book ID
- 104011830
- Publisher
- Elsevier Science
- Year
- 2004
- Tongue
- English
- Weight
- 470 KB
- Volume
- 30
- Category
- Article
- ISSN
- 1477-8424
No coin nor oath required. For personal study only.
โฆ Synopsis
Lamport diagrams are partial orders which depict computations of message passing systems. It is natural to consider generalizations of linear time temporal logics over such diagrams. In Meenakshi and Ramanujam (Proceedings of ICALP 2000. Lecture Notes in Computer Science, Vol. 1853. 2000. p. 487-98.) we presented a decidable temporal logic with local temporal modalities and a global 'previous' modality to talk of message receipts. It seems reasonable to extend the logic with a global 'next' modality as well, so that sending of messages may also be easily speciรฟed, but this (or other similar attempts) lead to undecidability. Hence, we consider ways of restricting the models so as to obtain decidability, while retaining the expressiveness of global 'next' and global 'previous' modalities. For this, we consider Lamport diagrams presented as a sequence of layers. The layers themselves describe รฟnite communication patterns and a diagram is obtained by sequential composition of such parallel processes. The logic is deรฟned appropriately, with layer formulas describing communications within a layer, and temporal formulas describing the sequence of layers in the computation. When the number of events in layers is uniformly bounded and each layer is communication closed, we get decidability. Alternatively, a stronger uniform bound on what we term channel capacity also yields decidability. We present an example of system speciรฟcation in the logic.
๐ SIMILAR VOLUMES