Clocks

Different types of clock used to sort events in distributed systems. Plus important graphs algorithms.

Franco Fernando

Mar 6

Hi Friends,

Welcome to the 15th issue of the Polymathic Engineer newsletter.

Today we will talk about:

How clocks are implemented in distributed systems
Five important graphs algorithms
Coding challenge
Three interesting tweets

Clocks and Time in Distributed Systems

Time plays a critical role in any distributed software application. For example, time is essential to order events. This task is easy for applications running on a single node since the operating system provides a monotonic clock.

Indeed, a monotonic clock moves only forward from a point in time and can be used to compare timestamps. But in distributed systems, processes run concurrently, and there isn't a global clock. As a result, there is no way to synchronize clocks across different nodes perfectly, and it's impossible to use traditional time clocks for ordering operations.

For this reason, distributed environments use a family of logical clocks. Logical clocks measure time not in absolute but in terms of logical operations. There are two main types of logical clocks: Lamport clock and Vector clock. Both use counters associated with processes.

Lamport clocks

A Lamport clock uses a single counter initialised to 0 for each process. A process increases its counter before each operation. When sending a message, a process attaches a copy of its counter. When receiving a message, a process merges its and the received counter.

The merge takes the maximum of the two counters. This mechanism guarantees an ordering for each pair of related operations. If the counter after operation B is 5 and after operation A is 4, then A happened before B.

However, unrelated operations can have the same counter's value. So if the counter is 1 after operation A and 3 after B, it is not sure that A happened before B. So the order of Lamport clock's counters doesn't guarantee any causal relationship.

Vector clocks

A Vector clock uses a list of N counters for each process, where N is the number of processes. A process increases its counter in its list before each operation. When sending a message, a process attaches a copy of its list.

When receiving a message, a process merges its and the received list. The merge takes the maximum of each counter in the two lists. This mechanism guarantees a partial ordering between lists. The ordering between lists is given comparing corresponding counters.

The order of Vector clocks lists guarantee a causal relationship between the operations. The disadvantage is that the memory requirement grows linearly. However, other variants of vector clocks solve this issue

Five important graph algorithms

Graph algorithms are used in many real-world scenarios. Here are 5 standard graph algorithms and their significant use cases.

Breadth-first search

It's a traversal algorithm implemented using a queue data structure. It starts from a node and first explores all its adjacent nodes. Then it explores all nodes two steps away from the starting one, and so on.

Applications of BFS are:

build web pages indexes in web crawlers
discover neighbour nodes in p2p networks
find neighboring places in GPS navigation systems

Deepth First Search

It's a traversal algorithm implemented using a stack data structure. It starts from a node and explores as far as possible along each path. When no more nodes exist to explore in the current path, it retraces.

Applications of DFS are:

find a path between 2 nodes
detect cycles in a graph
topological sorting
solve maze or sudoku puzzles

Shortest path

It's a traversal algorithm that calculates the shortest path between two nodes. The shortest path minimizes the sum of the weights on the traveled edges. There are two main algorithms: Dijkstra and Bellman–Ford.

Applications of the Shortest path are:

find travelling paths in navigation systems
solve the min-delay path problem in networking
finding the best route from one point to another in video games

Topological Sorting

It's a graph theory algorithm finding an order in which visiting the nodes. It linearly orders the nodes of a directed graph so that for each edge x -> y, vertex x precedes y.

Applications of the Topological sorting are:

scheduling interdependent job
data serialisation and sentence ordering
compilation tasks ordering and symbols dependencies resolution

Minimum spanning tree

It's a graph theory algorithm finding a subset of the edges connecting all the nodes. Such edges have no cycles and minimum sum of weights. Every connected and undirected graph has at least one spanning tree.

Applications of the Minimum spanning tree are:

network design
image registration and object tracking
analysis of graph-based data clusters

Coding challenge

The problem has as input an integer n and asks to return the first n rows of Pascal's triangle. A Pascal's Triangle is a triangle of numbers where each number is the sum of the two numbers directly above.

The problem is straightforward but it requires to properly handle indexes boundaries.

Two approaches are possible:

follow the definition and get each number as sum of the one above left and the one above right
reverse the definition letting each number contributing to the one below left and right

For both approaches, the time complexity is O(N^2) where N is the number of rows (in the last row we need to fill N elements). The space complexity is O(1).

The coding challenge for the next week is Online Stock Span.

Interesting Tweets

What Oliver wrote is true. It’s hard to become really good at something continuously change your niche. There is a huge difference in having 20 years of experience and 1 year of experience repeated 20 times.