Clock Synchronization in Decentralized Systems
Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Clock synchronization between different entities in a system has been approached using two main methods, decentralized and centralized synchronization. Examples of centralized synchronization include Network Time Protocol (NTP) and the use of Global Positioning System (GPS) as a central clock. The synchronization of clocks in distributed systems is a well-studied and difficult problem. Current solutions possess a significant convergence delay and a non-perfect synchronization window.
This thesis approaches the problem of clock synchronization in decentralized systems by analysing and using pulse-coupled oscillator models, like the Kuramoto model and the Mirollo-Strogatz firefly model, while leveraging the knowledge of internode latencies to form a biased gradient overlay topology, and creating a custom firefly synchronization model.
The system node coordinates are indicative of internode latencies if they are assigned statically using a latency data set or through a dynamic coordinate protocol, which assigns coordinates according to current internode latencies. The coordinates are then used to create an overlay over the physical topology by having larger number of links with lower internode latency. Neighbours are selected based on an information need basis. Logical time on the nodes is set in sync along with the phase synchronization using fine tuned algorithms to set a common timestamp on each cycle, and to optimize the synchronization window and the convergence time.
The results show that the gradient firefly synchronization is efficient in convergence time as well as synchronization window. The protocol works better with a single cluster of nodes as compared to multiple clusters. It is concluded in the thesis that latency aware gradient firefly synchronization protocols can be used per cluster and the performance can be improved further with the incorporation of dynamic coordinate protocols.
Place, publisher, year, edition, pages
2012. , 67 p.
Engineering and Technology
IdentifiersURN: urn:nbn:se:kth:diva-94141OAI: oai:DiVA.org:kth-94141DiVA: diva2:525462
Subject / course
Information and Communication Technology
Master of Science -Communication Systems
Haridi, Seif, Professor