On Compressing Interchange Classes of Events in a Concurrent System

The use of strings is standard in modeling the temporal ordering of events in a sequential computation. A recent prize-winning paper in the computer architecture literature applies a grammar-based lossless data compression algorithm to the sequence of events that transpire while a computer program runs and utilizes the resulting grammar to better understand the program's dynamic behavior and improve its performance. Lossless data compression is most suitable for this purpose when there is a well-defined total ordering of event occurrences. In concurrent systems, i.e., systems involving multiple processes, there is a partial ordering of events. Trace theory employs congruence or interchange classes of words over partially commutative alphabets as a way to generalize strings to executions of concurrent processes. We consider universal compression schemes for a rate distortion problem in which the goal is to reproduce a string which is equivalent to the original string and we show that for a large collection of dependence alphabets we can asymptotically attain the interchange entropy, i.e., the rate distortion limit.