Distributed timestamp generation in planar lattice networks

Timestamps are considered for distributed environments in which information flow is restricted to one direction through a planar lattice imposed on a network. For applications in such networks, existing timestamping algorithms require extension and modification. For example, in secure environments, typical timestamps provide a potential signaling channel between incomparable levels. In hierarchical databases, typical timestamps cause peripheral sites to unnecessarily affect the behavior at main sites. Algorithms are presented by which a network node may generate and compare timestamps using timestamp components maintained at dominated nodes in the network. The comparison relation is shown to be acyclic for timestamps produced by the generation algorithm. We discuss ways to safely relax the requirement that the network be a lattice. By example, we show how to modify a simple nonplanar lattice so that the generation algorithm can be applied. Uses of the timestamp generation algorithm in the motivating applications are outlined.