GLOBALLY CONSISTENT EVENT ORDERING IN ONE DIRECTIONAL DISTRIBUTED ENVIRONMENTS

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 deco mposed databases. Although the most general one-directional communicat ion structure is a partial order, partial orders do not enjoy the prop erty of being consistently ordered, a formalization of the notion that local ordering decisions are ensured to be globally consistent. Our m ain result is that the crown-free property is necessary and sufficient for a communication structure to be consistently ordered. We discuss the computational complexity of detecting crowns and sketch typical ap plications.