Title :
k-Dependency Vectors: a scalable causality-tracking protocol
Author :
Baldoni, Roberto ; Melideo, Giovanna
Author_Institution :
Dipt. di Informatica e Sistemistica, Universita "La Sapienza", Roma, Italy
Abstract :
In this paper we present a scalable causality-tracking protocol, called k-Dependency Vectors, which piggybacks on each application message a constant number k of integers (with k /spl les/ n). These integers are selected from a vector of size n which is local at each process. By reducing the size of the piggybacked information, only a subset of the causal dependencies can be "on-the-fly" detected by the checker The other dependencies need an extra computation time to be rebuilt (detection delay). This delay is influenced by the adopted selection strategy. In the paper several selection strategies are proposed and evaluated with respect to the detection delay experienced by the checker.
Keywords :
concurrency theory; distributed algorithms; protocols; causal dependencies; detection delay; k-Dependency Vectors; piggybacked information; scalable causality-tracking protocol; Clocks; Computational modeling; Computer applications; Debugging; Delay; Distributed computing; Protocols; Scalability; Size control;
Conference_Titel :
Parallel, Distributed and Network-Based Processing, 2003. Proceedings. Eleventh Euromicro Conference on
Conference_Location :
Genova, Italy
Print_ISBN :
0-7695-1875-3
DOI :
10.1109/EMPDP.2003.1183592