๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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


Snap-stabilization in message-passing sy
โœ Sylvie Delaรซt; Stรฉphane Devismes; Mikhail Nesterenko; Sรฉbastien Tixeuil ๐Ÿ“‚ Article ๐Ÿ“… 2010 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 478 KB