DISTRIBUTED TIMESTAMP GENERATION IN PLANAR LATTICE NETWORKS

Timestamps are considered for distributed environments in which inform ation flow is restricted to one direction through a planar lattice imp osed on a network. For applications in such networks, existing timesta mping algorithms require extension and modification. For example, in s ecure environments, typical timestamps provide a potential signaling c hannel between incomparable levels. In hierarchical databases, typical timestamps cause peripheral sites to unnecessarily affect the behavio r 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 di scuss ways to safely relax the requirement that the network be a latti ce. By example, we show how to modify a simple nonplanar lattice so th at the generation algorithm can be applied. Uses of the timestamp gene ration algorithm in the motivating applications are outlined.