Generalized interface automata with multicast synchronization

Abstract

Interface automata are one of the prominent formalisms for specifying interface behaviors of componentbased systems. However, only one-to-one communication is allowed in the composition of interface automata. This paper presents multicast interface automata which generalize the classic interface automata and accommodate multicast communication mechanism. The multicast interface automata endorse both bottom-up and top-down design methodologies. Theoretical results on compatibility and refinement are established for incremental design and independent implementability.

Keywords

interface automata / multicast communication / component interaction / verification

References

[1] Alfaro L D, Henzinger T A. Interface automata. In: Proceedings of the 8th European Software Engineering Conference Held Jointly with 9th ACM SIGSOFT International Symposium on Foundations of Software Engineering. 2001, 109-120

[2] Alfaro L D, Henzinger T A. Interface-based design. Engineering Theories of Software-intensive Systems, 2005, 195: 83-104

[3] Lynch N A, Tuttle M R. Hierarchical correctness proofs for distributed algorithms. In: Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing. 1987, 137-151

[4] Lynch N A, Tuttle M R. An introduction to input/output automata. CWI-Quarterly, 1989, 2(3): 219-246

[5] Lynch N A. Distributed Algorithms. Morgan Kaufmann Publishers, San Mateo, CA, 1996.

[6] Kaynar D K, Lynch N A, Segala R, Vaandrager F. Timed I/O automata: a mathematical framework for modeling and analyzing realtime systems. In: Proceedings of the 24th IEEE Real-Time Systems Symposium. 2003, 166-177

[7] Kaynar D K, Lynch N A, Segala R, Vaandrager F. The theory of timed I/O automata. Synthesis Lectures on Computer Science, 2006, 1(1): 1-114

[8] Wu S H, Smolka S A, Stark E W. Composition and behaviors of probabilistic I/O automata. Theoretical Computer Science, 1997, 176(1-2): 1-38

[9] Stark E W, Smolka S A. Compositional analysis of expected delays in networks of probabilistic I/O automata. In: Proceedings of the 13th Annual IEEE Symposium on Logic in Computer Science. 1998, 466-477

[10] Stark E W, Cleaveland R, Smolka S A. A process-algebraic language for probabilistic I/O automata. Lecture Notes in Computer Science, 2003, 2761: 193-207

[11] Lynch N A, Segala R, Vaandrager F W. Hybrid I/O automata. Information and Computation, 2003, 185(1): 105-157

[12] Alfaro L D, Henzinger T A. Interface theories for component based design. Lecture Notes in Computer Science, 2001, 2211: 148-165

[13] Wen Y J, Wang J, Qi Z C. Bridging refinement of interface automata to forward simulation of I/O automata. In: Proceedings of the 6th International Conference on Formal Engineering Methods. 2004, 259-273

[14] Wen Y J, Wang J, Qi Z C. 2/3 alternating simulation between interface automata. In: Proceedings of 7th International Conference on Formal Engineering Methods. 2005, 173-187.

[15] Chakrabarti A, Alfaro L D, Henzinger T A, Jurdzinski M, Mang F Y C. Interface compatibility checking for software modules. Lecture Notes in Computer Science, 2002, 2404: 428-441

[16] Chakrabarti A, Alfaro L D, Henzinger T A, Mang F Y C. Synchronous and bidirectional component interfaces. Lecture Notes in Computer Science, 2002, 2404: 414-427

[17] Alfaro L D, Henzinger T A, Stoelinga M. Timed interfaces. Lecture Notes in Computer Science, 2002, 2491: 108-122

[18] Chakrabarti A, Alfaro L D, Henzinger T A, Stoelinga M. Resource interfaces. Lecture Notes in Computer Science, 2003, 2855: 117-133

[19] Alfaro L D, Silva L D D, Faella M, Legay A, Roy P, Sorea M. Sociable interfaces. Lecture Notes in Computer Science, 2005, 3717: 81-105

[20] Alur R, Henzinger T A, Kupferman O, Vardi M. Alternating refinement relations. Lecture Notes in Computer Science, 1998, 1466: 163-178

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg