Timestamping messages and events in a distributed system using synchronous communication |
| |
Authors: | Vijay K Garg Chakarat Skawratananond Neeraj Mittal |
| |
Affiliation: | (1) Department of Electrical and Computer Engineering, The University of Texas at Austin, Austin, TX 78712, USA;(2) eServer Solutions, IBM Austin, Inc., Austin, TX 78758, USA;(3) Department of Computer Science, The University of Texas at Dallas, Richardson, TX 75083, USA |
| |
Abstract: | Determining order relationship between events of a distributed computation is a fundamental problem in distributed systems
which has applications in many areas including debugging, visualization, checkpointing and recovery. Fidge/Mattern’s vector-clock
mechanism captures the order relationship using a vector of size N in a system consisting of N processes. As a result, it incurs message and space overhead of N integers. Many distributed applications use synchronous messages for communication. It is therefore natural to ask whether it is possible to reduce the timestamping overhead for such applications.
In this paper, we present a new approach for timestamping messages and events of a synchronously ordered computation, that is, when processes communicate using synchronous messages. Our approach depends on decomposing edges in the communication
topology into mutually disjoint edge groups such that each edge group either forms a star or a triangle. We show that, to accurately capture the order relationship between
synchronous messages, it is sufficient to use one component per edge group in the vector instead of one component per process.
Timestamps for events are only slightly bigger than timestamps for messages. Many common communication topologies such as
ring, grid and hypercube can be decomposed into edge groups, resulting in almost 50% improvement in both space and communication overheads. We prove that the problem of
computing an optimal edge decomposition of a communication topology is NP-complete in general. We also present a heuristic
algorithm for computing an edge decomposition whose size is within a factor of two of the optimal. We prove that, in the worst
case, it is not possible to timestamp messages of a synchronously ordered computation using a vector containing fewer than
components when N ≥ 2. Finally, we show that messages in a synchronously ordered computation can always be timestamped in an offline manner
using a vector of size at most .
An earlier version of this paper appeared in 2002 Proceedings of the IEEE International Conference on Distributed Computing
Systems (ICDCS).
The author V. K. Garg was supported in part by the NSF Grants ECS-9907213, CCR-9988225, an Engineering Foundation Fellowship.
This work was done while the author C. Skawratananond was a Ph.D. student at the University of Texas at Austin. |
| |
Keywords: | Synchronous communication Timestamping messages and events Vector clocks Edge decomposition Vertex cover |
本文献已被 SpringerLink 等数据库收录! |
|