Document Open Access Logo

On the Succinctness of Idioms for Concurrent Programming

Authors David Harel, Guy Katz, Robby Lampert, Assaf Marron, Gera Weiss

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2015.85.pdf
  • Filesize: 428 kB
  • 15 pages

Document Identifiers

Author Details

David Harel
Guy Katz
Robby Lampert
Assaf Marron
Gera Weiss

Cite As Get BibTex

David Harel, Guy Katz, Robby Lampert, Assaf Marron, and Gera Weiss. On the Succinctness of Idioms for Concurrent Programming. In 26th International Conference on Concurrency Theory (CONCUR 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 42, pp. 85-99, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.CONCUR.2015.85

Abstract

The ability to create succinct programs is a central criterion for comparing programming and specification methods. Specifically, approaches to concurrent programming can often be thought of as idioms for the composition of automata, and as such they can then be compared using the standard and natural measure for the complexity of automata, descriptive succinctness. This measure captures the size of the automata that the evaluated approach needs for expressing the languages under discussion. The significance of this metric lies, among other things, in its impact on software reliability, maintainability, reusability and simplicity, and on software analysis and verification. Here, we focus on the succinctness afforded by three basic concurrent programming idioms: requesting events, blocking events and waiting for events. We show that a programming model containing all three idioms is exponentially more succinct than non-parallel automata, and that its succinctness is additive to that of classical nondeterministic and "and" automata. We also show that our model is strictly contained in the model of cooperating automata à la statecharts, but that it may provide similar exponential succinctness over non-parallel automata as the more general model - while affording increased encapsulation. We then investigate the contribution of each of the three idioms to the descriptive succinctness of the model as a whole, and show that they each have their unique succinctness advantages that are not subsumed by their counterparts. Our results contribute to a rigorous basis for assessing the complexity of specifying, developing and maintaining complex concurrent software.

Subject Classification

Keywords
  • Descriptive Succinctness
  • Module Size
  • Automata
  • Bounded Concurrency

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. R. Alur and D. Dill. A Theory of Timed Automata. Theoretical Computer Science, 126(2):183-235, 1994. Google Scholar
  2. J. Birget. Two-Way Automata and Length-Preserving Homomorphisms. Mathematical Systems Theory, 29(3):191-226, 1996. Google Scholar
  3. A. Chandra, D. Kozen, and L. Stockmeyer. Alternation. J. Assoc. Comput. Mach., 28(1):114-133, 1981. Google Scholar
  4. W. Damm and D. Harel. LSCs: Breathing Life into Message Sequence Charts. J. on Formal Methods in System Design, 19(1):45-80, 2001. Google Scholar
  5. D. Drusinsky and D. Harel. On the Power of Bounded Concurrency I: Finite Automata. J. Assoc. Comput. Mach., 41:517-539, 1994. Google Scholar
  6. P. Eugster, P. Felber, R. Guerraoui, and A. Kermarrec. The Many Faces of Publish/Subscribe. ACM Computing Surveys, 35(2):114-131, 2003. Google Scholar
  7. M. Gordon, A. Marron, and O. Meerbaum-Salant. Spaghetti for the Main Course? Observations on the Naturalness of Scenario-Based Programming. In Proc. 17th Conf. on Innovation and Technology in Computer Science Education (ITICSE), pages 198-203, 2012. Google Scholar
  8. D. Harel. Statecharts: A Visual Formalism for Complex Systems. Science of Computer Programming, 8(3):231-274, 1987. Google Scholar
  9. D. Harel, A. Kantor, G. Katz, A. Marron, L. Mizrahi, and G. Weiss. On Composing and Proving the Correctness of Reactive Behavior. In Proc. 13th Int. Conf. on Embedded Software (EMSOFT), pages 1-10, 2013. Google Scholar
  10. D. Harel, G. Katz, R. Lampert, A. Marron, and G. Weiss. On the Succinctness of Idioms for Concurrent Programming: Supplementary Material. URL: http://www.wisdom.weizmann.ac.il/~bprogram/doc/Concur15Sup.pdf.
  11. D. Harel, G. Katz, A. Marron, and G. Weiss. Non-Intrusive Repair of Safety and Liveness Violations in Reactive Programs. Trans. on Computational Collective Intelligence, 16:1-33, 2014. Google Scholar
  12. D. Harel, G. Katz, A. Marron, and G. Weiss. The Effect of Concurrent Programming Idioms on Verification. In Proc. 3rd Int. Conf. on Model-Driven Engineering and Software Development (MODELSWARD), 2015. Google Scholar
  13. D. Harel, A. Marron, and G. Weiss. Behavioral programming. Comm. Assoc. Comput. Mach., 55(7):90-100, 2012. Google Scholar
  14. T. Hirst and D. Harel. On the Power of Bounded Concurrency II: Pushdown Automata. J. Assoc. Comput. Mach., 41:540-559, 1994. Google Scholar
  15. M. Holzer and M. Kutrib. Descriptional and Computational Complexity of Finite Automata - a Survey. Information and Computation, 209(3):456-470, 2011. Google Scholar
  16. J. Hromkovič and G. Schnitger. Lower Bounds on the Size of Sweeping Automata. Journal of Automata, Languages and Combinatorics, 14(1):23-13, 2009. Google Scholar
  17. O. Kupferman, A. Ta-Shma, and M. Vardi. Counting With Automata, 1999. Tech. Report. Google Scholar
  18. E. Leiss. Succinct Representation of Regular Languages by Boolean Automata. Theoretical Computer Science, 13:323-330, 1981. Google Scholar
  19. A. Meyer and M. Fischer. Economy of Description by Automata, Grammars, and Formal Systems. In Proc. 12th Sym. on Switching and Automata Theory (SWAT), pages 188-191, 1971. Google Scholar
  20. J. Musa. Software Reliability Engineered Testing. McGraw-Hill, 1998. Google Scholar
  21. D. Parnas. On the Criteria to be used in Decomposing Systems into Modules. Comm. Assoc. Comput. Mach., 15(12):1053-1058, 1972. Google Scholar
  22. M. Rabin and D. Scott. Finite Automata and Their Decision Problems. IBM Journal of Research and Development, 3(2):114-125, 1959. Google Scholar
  23. S. Safra and M. Vardi. On ω-Automata and Temporal Logic. In Proc. 21st Sym. on Theory of Computing (STOC), pages 127-137, 1989. Google Scholar
  24. W. Sakoda and M. Sipser. Nondeterminism and the Size of Two Way Finite Automata. In Proc. 10th Sym. on Theory of Computing (STOC), pages 275-286, 1978. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact