Layering techniques for development of parallel systems: An algebraic approach

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    5 Citations (Scopus)

    Abstract

    A process language is presented which makes a clear distinction between temporal order and causal order. This allows for several algebraic laws that are particularly interesting for the design of concurrent systems. One of these is an algebraic formulation of the communication closed layers principle by [EF82]. These laws suffice to rewrite process terms that avoid specification of temporal ordering into a unique normal form. Other transformations allow for gradually imposing temporal ordering on an already functionally correct design. The combination of such laws enables a design strategy where architecture independent designs are transformed towards a form that matches a particular implementation architecture. We apply this style of design to various distributed algorithms, including an algorithm for the “point-in-polygon” problem transformed to a form suitable for pipelined execution on a tree network, and the Floyd-Warshall algorithm for the all-points shortest path transformed to a form suitable for execution on a SIMD architecture.

    Original languageEnglish
    Title of host publicationComputer Aided Verification
    Subtitle of host publicationFourth International Workshop, CAV 1992, Proceedings
    EditorsDavid Karl Probst, Gregor von Bochmann
    PublisherSpringer
    Pages16-29
    Number of pages14
    ISBN (Electronic)978-3-540-47572-9
    ISBN (Print)978-3-540-56496-6
    DOIs
    Publication statusPublished - 1 Jan 1993
    Event4th Workshop on Computer-Aided Verification, CAV 1992 - Montreal, Canada
    Duration: 29 Jun 19921 Jul 1992
    Conference number: 4

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume663 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference4th Workshop on Computer-Aided Verification, CAV 1992
    Abbreviated titleCAV
    CountryCanada
    CityMontreal
    Period29/06/921/07/92

    Fingerprint Dive into the research topics of 'Layering techniques for development of parallel systems: An algebraic approach'. Together they form a unique fingerprint.

    Cite this