If you wanted to synchronize your watch with all your friends and all of you did not have access to a universal time source, how would you proceed?  The first step would probably be figuring out a method in which to communicate with all of your friends in order to relay the exact time displayed on your local watch.  But, as you would quickly discover, communicating simultaneously with all of your friends would be very difficult.  Additionally, each person would take a variable amount of time before they were able to adjust their watch appropriately.  In the end, the times between you and your friends’ watches would remain out of sync!
This dilemma of synchronizing time is actually relevant to the synchronization of nodes in a distributed and connected network. Building a model of the situation with nodes, edges and times in a graph of the network helps to prove and illustrate some interesting facts—something that we have been doing in Networks with other network models.  According to a paper authored by two MIT professors it is impossible to synchronize processes in a network completely, unless strong assumptions about the network are made.  But, it is possible to prove that synchronization can only be achieved to within a certain value and no better, no matter what algorithm is used.
The Lundelius-Lynch model assumes a distributed and completely connected system of processes that can only communicate by sending messages to one another.  As we learned in class, a completely connected graph is one where every node  is connected to the others via a direct path.  Within each process there is a physical clock, which is not controlled by the process but can be read by the process.  It is important to note that the physical clock cannot be set and continually advances. Additionally, the entire network is defined to contain n processes, which can be represented as vertices in our complete communication graph.  Also, each process is allowed to know the positions of other nodes in the network and the size of the network itself.  Further, a process can take an indeterminate amount of time to read its incoming messages.  Thus, some processes read their messages immediately while others wait until they are ready to process the message, adding an element of uncertainty.  We can represent the edges between nodes as having a message time plus an for uncertainty.  After analysis in the paper, it is shown that time cannot be synced completely across all nodes!

We could relate this process to the spread and mutation of an epidemic (something we have touched on in class), and find bounds for how much the disease could transform.  How good does a vaccine have to be so that it could accommodate at least the minimum ‘sync’ of the disease?  The network could be represented as a proximity network like we did in class, where sending a “message” or disease with an uncertain mutation would not be a decision, just like sending a message when syncing is required.  Along the same lines, what happens if the system of nodes we consider is faulty?  For example, what if there is a probability, just like in the spread of disease, that a node does not receive the message (perhaps disease).  The introduction of a probability and faulty systems are potential fields of explorations, and our knowledge of networks provides a strong foundation to embarking on solving these problems.

Referenced Paper:

ti.tuwien.ac.at/ecs/people/schmid/Mypapers/MS06.pdf