4.Lucy Zhu4 minEditSuppose that the underlying communication system guarantees FIFO ordering ofmessages. How will you exploit this feature to reduce the communication complexity of thevector clock algorithm? Give an expression for overhead savings if your scheme is used insteadof the traditional vector clock algorithm. Assume that any process can send at most m messages.(Hint: You should use only O(n) storage at each process.)ge

To make the communication difficulty of vector clock method less complicated, we may take use of the…

Answered: messages. How will you exploit this…

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Related questions

Question

4.
Lucy Zhu
4 min
Edit
Suppose that the underlying communication system guarantees FIFO ordering of
messages. How will you exploit this feature to reduce the communication complexity of the
vector clock algorithm? Give an expression for overhead savings if your scheme is used instead
of the traditional vector clock algorithm. Assume that any process can send at most m messages.
(Hint: You should use only O(n) storage at each process.)
ge

Expert Solution

Step 1

To make the communication difficulty of vector clock method less complicated, we may take use of the FIFO ordering for messages.
Consider a system having n processes, each of which is capable of sending a maximum of m messages. The sequence of events at every process may be tracked using a conventional vector clock technique. However, we can also use a scheme where each process only stores the vector clock of the last message it received. This scheme has the advantage that it only requires O(n) storage at each process, instead of O(nm) storage for the traditional vector clock algorithm.
The overhead savings for this scheme can be expressed as follows.
Traditional vector clock algorithm: O(nm)
Reduced vector clock algorithm: O(n)
Overhead savings: O(nm - n) = O(n(m-1))
Thus, we can save O(n(m-1)) in storage overhead by using the reduced vector clock algorithm.

Explanation:

One way to exploit the FIFO ordering of messages is to use a timestamp-based vector clock algorithm. A timestamp variable of length n, where n is the total number of processes, is maintained by each process in this approach. Process's most recent communication is reflected there in timestamp vector by its own time stamp. A process's timestamp vector is included in every message it sends. A process compares its timestamp vector in such a message with its personal timestamp vector to update its very own timestamp vector when it gets one. When a timestamp vector in a message is later than that of the process's internal timestamp vector, the program adjusts its very own timestamp vector to match the timestamp vector there in message. This algorithm has the advantage of being very simple to implement, and it requires only O(n) storage at each process.
The disadvantage of this algorithm is that it is not very efficient. In particular, it requires O(n) time to update the timestamp vector at each process, and it requires O(n) space to store the timestamp vector at each process.
A more efficient way to exploit the FIFO ordering of messages is to use a log-based vector clock algorithm. The quantity of processes there in system determines the amount of the log kept by each process in this method. The log documents the last time any given process communicated with the system. Every time a process transmits a message, it also logs the message's transmission in its own history.
Each process keeps its own log and, when receiving a message, compares the log there in message to its own log to make any necessary adjustments. The process will update its very own log to match the log there in message if the message's log is more recent. The efficiency of this approach is improved over the timestamp-based vector clocks algorithm. In particular, updating the log at every process takes just O(1) time, while storing the log takes only O(n) space.