Solving Intersections by Marzullo’s Way

In the real-world scenario, we know that a distributed database system has to make a tradeoff between Consistency and Availability when a Partition occurs. Now while designing a system that supports high availability and partition tolerance, a consistency issue arises. We may need to consider different consistency patterns such as Weak Consistency, Eventual Consistency, and Strong consistency while achieving high availability and partition tolerance. When there is no centralized server to maintain some clocking mechanism to synchronize all nodes in a distributed system, the Network Time Protocol comes into play. Network Time Protocol is used to achieve Strong Consistency where nodes adjust their clocks based on the node’s local time and the average time difference with other nodes. Marzullo’s Algorithm is an agreement algorithm used in Network Time Protocol to select sources for estimating accurate time from a number of noisy time sources. It is also used to calculate the relaxed intersection of source intervals, where the best estimate is the smallest interval that is consistent with the largest number of resources.

Now consider we have following estimates 8 ± 2, 9 ± 4, 12 ± 3, 14 ± 2, 17 ± 4 then the intervals become [6, 10], [5, 13], [9, 15], [12, 16], [13, 21] which intersects to form [13, 15] or 14 ± 1 consistent with largest number of sources. More than one consistent intervals may be possible in some cases.

Let's have a look at some coding problems where we deal with the intervals

[Q] Write a program that finds the maximum number of events that occurred at a time, given a list of events and their arrival and departure times

For example, suppose you had ten employees who arrived and left at the times listed below (for example, employee 6 arrived at 10:00 am and departed at 3:00 pm):

There was a maximum of 8 employees at work at the time 2 p.m. Our task is to code a program that determines the start and finish times of the time block with the most events.

[Q] Given an array of meeting time intervals consisting of start and end times, find the minimum number of conference rooms required.

Way -1: We can solve this problem using Heap logic that requires O(n log n) time complexity.

Algorithm-

1. Sort the input array based on the start time
2. Create a minheap to store the end times of meetings that have has rooms assigned to
3. Start pushing the end time of the first meeting to the heap
4. Loop through the rest of the array: (i) compare the start time of the current meeting with the top element of the min-heap: if they do not overlap, pop that element out from the heap. (ii) Push end time of the current meeting into min-heap
5. Return length of the remaining heap

Way-2: We can use Marzullo’s Algorithm to solve the problem that required O(n) time complexity

Marzullo’s approach is both space and time-efficient. Asymptotic space consumption is O(n), where n is the number of sources. In terms of asymptotic time, the process can be thought of as building the table, sorting it, and searching it. Sorting takes O(n log n) time, which dominates the constructing and searching stages, which take linear time. As a result, Marzullo’s algorithm has a time efficiency of O(n log n). Remember that if you have a very large time interval, the size of thecounts_per_hour array will be larger.

Once the table has been generated and sorted, the interval for one source can be updated in linear time (when new information is received). As a result, updating data for one source and determining the appropriate interval can be accomplished in O(n) time. Hence it is good to use Marzullo’s algorithm to solve the intersection problems when the input window is limited.