On reducing the complexity of matrix clocks

✍ Scribed by Lúcia M.A. Drummond; Valmir C. Barbosa

• Book ID: 104304251
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 140 KB
• Volume: 29
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(03)00066-8

✦ Synopsis

Matrix clocks are a generalization of the notion of vector clocks that allows the local representation of causal precedence to reach into an asynchronous distributed computationÕs past with depth x, where x P 1 is an integer. Maintaining matrix clocks correctly in a system of n nodes requires that every message be accompanied by Oðn x Þ numbers, which reflects an exponential dependency of the complexity of matrix clocks upon the desired depth x. We introduce a novel type of matrix clock, one that requires only nx numbers to be attached to each message while maintaining what for many applications may be the most significant portion of the information that the original matrix clock carries. In order to illustrate the new clockÕs applicability, we demonstrate its use in the monitoring of certain resource-sharing computations.