SOME COMBINATORIAL ASPECTS OF TIME-STAMP SYSTEMS

The aim of this paper is to outline a combinatorial structure appearing in distributed computing, namely a directed graph in which a certain family of subsets with k vertices have a successor. It has been proved that the number of vertices of such a graph is at least 2k - 1 and an effective construction has been given which needs k2k - 1 vertices. This problems is issued from some questions related to the labeling of processes in a system for determining the order in which they were created. By modifying some requirements on the distributed system, we show that there arise other combinatorial structures leading to the construction of solutions the size of which becomes a linear function of the input. © 1993 Academic Press, Inc.