Title: An Efficient Implementation of Vector Clocks in Dynamic Systems
Abstract:A system of vector clocks is strongly consistent and it captures the happened before relations among events in the system. These clocks underlie solutions to a number of problems in distributed system...A system of vector clocks is strongly consistent and it captures the happened before relations among events in the system. These clocks underlie solutions to a number of problems in distributed systems including, among others, detecting global predicates, debugging distributed programs, causally ordering multicast messages, and implementing a distributed shared memory. In general, a data structure of size n, where n is the number of processes in the system, has to be maintained at each process and attached with each message communicated in the system to implement vector clocks. This is a considerable communication overhead in large systems. A differential technique has been proposed to reduce this required communication overhead for static systems with FIFO channels. In this study, the differential technique is improved to further reduce the required communication overhead. A protocol is proposed to maintain a virtual network topology of a logical ring combined with multiple computation trees so that the differential technique can be applied to dynamic systems. When a process leaves the clock maintained at this process is taken over by another one in the system. At the time a process joins the system, it will inherits the causality relations maintained at the process that creates the new process. Correctness of the protocol and the clock properties are proved as well.Read More
Publication Year: 2006
Publication Date: 2006-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 7
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot