Globally consistent event ordering in one-directional distributed environments

Paul Ammann, Sushil Jajodia, Phyllis G. Frankl

    Research output: Contribution to journalArticlepeer-review


    We consider communication structures for event ordering algorithms in distributed environments where information flows only in one direction. Example applications are multilevel security and hierarchically decomposed databases. Although the most general one-directional communication structure is a partial order, partial orders do not enjoy the property of being consistently ordered, a formalization of the notion that local ordering decisions are ensured to be globally consistent. Our main result is that the crown-free properly is necessary and sufficient for a communication structure to be consistently ordered. We discuss the computational complexity of detecting crowns and sketch typical applications.

    Original languageEnglish (US)
    Pages (from-to)665-670
    Number of pages6
    JournalIEEE Transactions on Parallel and Distributed Systems
    Issue number6
    StatePublished - 1996


    • Crowns
    • Databases
    • Distributed networks
    • Graph algorithms
    • Hierarchically decomposed databases
    • Multilevel
    • Partial orders
    • Security

    ASJC Scopus subject areas

    • Signal Processing
    • Hardware and Architecture
    • Computational Theory and Mathematics


    Dive into the research topics of 'Globally consistent event ordering in one-directional distributed environments'. Together they form a unique fingerprint.

    Cite this