Accession Number : ADA267534


Title :   Causality-Preserving Timestamps in Distributed Programs


Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE


Personal Author(s) : Beguelin, Adam ; Seligman, Erik


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a267534.pdf


Report Date : Jun 1993


Pagination or Media Count : 14


Abstract : A tachyon is an improperly ordered event in a distributed program. Tachyons are most often manifested as messages which are received before they are sent, violating the principle of causality. Although tachyons are not possible in real life, they may appear to occur in distributed parallel program traces due to coarse clock granularity or poor clock synchronization. In this paper, we establish that tachyons do in fact occur commonly in distributed programs on our Ethernet at Carnegie Mellon University, and we discuss some ways of eliminating them from program traces while preserving at least some knowledge of the length of time intervals in our programs. Our methods are based on Lamport-style clock corrections; when a process receives a message stamped with a later sending time, it sets its own clock ahead to a time at least as great as the sending timestamp. We have implemented this both in real time and in a more comprehensive post-processor for Xab


Descriptors :   *COMPUTER PROGRAMMING , *DEBUGGING(COMPUTERS) , CLOCKS , PROBLEM SOLVING , COMPUTER FILES , TRAVEL TIME , CORRECTIONS , MESSAGE PROCESSING , SYNCHRONIZATION(ELECTRONICS) , REAL TIME


Subject Categories : Computer Programming and Software


Distribution Statement : APPROVED FOR PUBLIC RELEASE