Timestamping messages in synchronous computations
Tóm tắt
We present a method of timestamping messages and events in synchronous computations that capture the order relationship with vectors of size less than or equal to the size of the vertex cover of the communication topology of the system. Our method is fundamentally different from the techniques of Fidge (1989) and Mattern (1989). The timestamps in our method do not use one component per process but still guarantee that the order relationship is captured accurately. Our algorithm is online and only requires piggybacking of timestamps on program messages. It is applicable to all programs that either use programming languages based on synchronous communication such as CSP or use synchronous remote procedure calls.
Từ khóa
#Distributed computing #Clocks #Concurrent computing #Asynchronous communication #Topology #Programming profession #Remote monitoring #Visualization #Debugging #Fault toleranceTài liệu tham khảo
0, IBM Corporation IBM Distributed Debugger
kohl, 1995, The pvm3.4 tracing facility and xpvm 1.1, Technical report Comp Science and Math Division Oak Ridge National Lab
10.1093/comjnl/40.8.499
10.1145/359545.359563
mattern, 1989, Virtual time and global states of distributed systems, Proceedings of the International Workshop on Parallel and Distributed Algorithms, 215
10.1109/ISADS.1995.398974
10.1016/0012-365X(79)90082-7
10.1016/0020-0190(92)90028-T
10.1145/3959.3962
10.1007/3-540-61769-8_6
10.2307/2371374
10.2307/1969503
garey, 1979, Computers and Intractability A Guide to the Theory of NP-Completeness
fidge, 1989, Partial orders for parallel debugging, Proceedings of the ACM SIGPLAN/SIGOPS Workshop on Parallel and Distributed Debugging, 183
10.1109/71.277788
10.1145/383962.383988
10.1109/ICDCS.1996.507907
10.1007/s004460050018
hoare, 1985, Communicating Sequential Processes
trotter, 1992, Combinatorics and Partially Ordered Sets: Dimension Theory
10.1109/ICDSC.2001.918989
ward, 2000, A framework algorithm for dynamic, centralized, dimension-bounded timestamps, Proceedings of the 2000 CAS Conference
10.1137/0603036