The Polymathic Engineer

Share this post

Clocks

newsletter.francofernando.com

Clocks

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

Franco Fernando
Mar 6
2
Share this post

Clocks

newsletter.francofernando.com

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

Thanks for reading The Polymathic Engineer! Subscribe for free to receive new posts and support my work.

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:

  1. follow the definition and get each number as sum of the one above left and the one above right

  2. 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.

Twitter avatar for @oliverjumpertz
Oliver Jumpertz @oliverjumpertz
Software development is a field where even 50 years of experience don't make you a pro in everything. Even funnier: Technology often advances faster than you can keep up. Lessons: - Build a broad foundation - Pick your niche -> specialize - Don't burn out trying to catch up
1:35 PM ∙ Feb 28, 2023
239Likes38Retweets

Test coverage is a metric that can be faked. What's more important is that the tests you write make sense.

Twitter avatar for @mjovanovictech
Milan Jovanović @mjovanovictech
100% test coverage should never be your goal. I've worked on a project where 90%+ was a requirement, and I found it enjoyable. But pushing for more would've been a pain. Aiming for 100% test coverage can lead to a false sense of security.
8:16 AM ∙ Feb 28, 2023
63Likes2Retweets

Software engineering is a career where you must constantly put in the effort to keep your level. But this is also what I love about it.[

Twitter avatar for @TAbrodi
Tiger Abrodi @TAbrodi
Software engineering is one of the few careers where you can excel super fast by putting in hard work. I don't know any other career where you can boost yourself up to 6-figures within two years.
6:00 AM ∙ Feb 27, 2023
47Likes4Retweets

Thanks for reading The Polymathic Engineer! Subscribe for free to receive new posts and support my work.

Share this post

Clocks

newsletter.francofernando.com
Comments
TopNewCommunity

No posts

Ready for more?

© 2023 Franco Fernando
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing