Clock Synchronization in Distributed System| Process Synchronization in Distributed System

Introduction:

Synchronization in distributed systems is often much more difficult compared to synchronization in uni-processor or multi-processor systems. Synchronization is all about doing the right thing at the right time. In process synchronization we make sure that one process waits for another to complete its operation.

A problem in distributed systems, and computer networks in general, is that there is no notion of a globally shared clock. In other words, processes on different machines have their own idea of what time it is.

There are various way to synchronize clocks in a distributed system, but all methods are essentially based on exchanging clock values, while taking into account the time it takes to send and receive messages. Variations in communication delays and the way those variations are dealt with, largely determine the accuracy of clock synchronization algorithms.

An important class of synchronization algorithms is that of distributed mutual exclusion. These algorithms ensure that in a distributed collection of processes, at most one process at a time has access to a shared resource. Distributed mutual exclusion can easily be achieved if we make use of a coordinator that keeps track of whose turn it is.

Time in a Distributed System:

Time is an important practical issue in distributed system. For example, we require computers around the world to timestamp electronic commerce transactions consistently. Time is also an important theoretical construct in understanding how distributed executions unfold. But time is problematic in distributed systems.

Local clocks invariably drift and need periodic resynchronization to support a common notion of time across the entire distributed system. Each computer may have its own physical clock, but the clocks typically deviate, and we cannot synchronize them perfectly. Time is an important and interesting issue in distributed systems, for several reasons.

First, time is a quantity we often want to measure accurately. In order to know at what time of day a particular event occurred at a particular computer it is necessary to synchronize its clock with an authoritative, external source of time. For example, an eCommerce transaction involves events at a merchant’s computer and at a bank’s computer. It is important, for auditing purposes that those events are timestamped accurately.

Second, algorithms that depend upon clock synchronization have been developed for several problems in distribution [Liskov 1993]. These include maintaining the consistency of distributed data, checking the authenticity of a request sent to a server, and eliminating the processing of duplicate updates.

Clock, Event and Process States:

Clocks, events, and process states are fundamental concepts in distributed systems that help in understanding system behavior, synchronization, and coordination. Here’s an overview of each:

Clocks:

Physical Clocks: Physical clocks are hardware-based mechanisms that track time based on real-world phenomena, such as the oscillations of a quartz crystal or the ticks of a system timer. Physical clocks provide a measure of absolute time and are typically synchronized to a reference time source, such as a network time protocol (NTP) server.

Logical Clocks: Logical clocks are software-based mechanisms used in distributed systems to order events causally. Unlike physical clocks, logical clocks do not represent real time but rather provide a partial ordering of events based on their logical relationships. Lamport’s logical clocks and vector clocks are common examples of logical clock algorithms used in distributed systems.

Vector Clocks: Vector clocks extend Lamport’s logical clocks to capture causality relationships between processes in a distributed system. Each process maintains a vector of logical timestamps, with each entry representing the local time of a process. Vector clocks are used to detect causality relationships between events and resolve conflicts in distributed systems.

Events:

Event: An event is a significant occurrence or action that happens at a particular point in time within a distributed system. Examples of events include process startup, message transmission, message reception, process termination, and critical section entry/exit.

Causality: Causality refers to the relationship between events where one event influences or causes another event to occur. Understanding causality is crucial in distributed systems for reasoning about the ordering of events and maintaining consistency.

Process States:

Process: In a distributed system, a process is an instance of a running program or application that performs computations, communicates with other processes, and interacts with the system’s resources.

Process State: The state of a process represents its current condition or progress within the system. Common process states include:

Running: The process is actively executing instructions on the CPU.
Blocked: The process is waiting for a particular event or resource, such as I/O completion or message arrival.
Ready: The process is ready to execute but is waiting for CPU time.
Terminated: The process has completed its execution and has been terminated.

Concurrency Control: Process states and their transitions are managed by the operating system or runtime environment to ensure proper synchronization, resource allocation, and system stability. Techniques such as mutual exclusion, semaphores, and monitors are used for concurrency control in distributed systems.

Computer Clocks and Timing Events:

Each computer in a Distributed System has its own internal clock used by local processes to obtain the value of the current time. Processes on different computers can timestamp their events. But clocks on different computers may give different times.

Even if clocks on all computers in a distributed system are set to the same time, their clocks will eventually vary quite significantly unless corrections are applied. Computer clocks drift from perfect time and their drift rates differ from one another.

Clock Skew and Clock Drift:

Clock Skew is the difference between the times on two clocks (at any instant). The instantaneous difference between the readings of any two clocks is called their skew. Also, the crystal-based clocks used in computers are, like any other clocks, subject to clock drift, which means that they count time at different rates, and so diverge.

Clock drift rate- the relative amount that a computer clock differs from a perfect clock. A clock’s drift rate is the change in the offset (difference in reading) between the clock and a nominal perfect reference clock per unit of time measured by the reference clock.

Coordinated Universal Time:

Coordinated Universal Time (UTC) is the primary time standard by which the world regulates clocks and time. All the computers are generally synchronized to a standard time called Coordinated Universal Time. Coordinated Universal Time – abbreviated as UTC is an international standard for timekeeping. It serves as the reference time scale against which time zones and local times are defined globally.

The time keeping in UTC is based on atomic clocks. UTC signals are regularly broadcast from satellites as well as many radio stations.

Computer servers and online services with UTC receivers can be synchronized by satellite broadcasts. Many popular synchronization protocols in distributed systems use UTC as a reference time to synchronize clocks of computers.

UTC is defined by the International Telecommunication Union (ITU) and maintained by the International Bureau of Weights and Measures (BIPM). It is calculated by atomic clocks located in various laboratories around the world, which measure the vibrations of atoms to define precise time intervals.

UTC is widely recognized and accepted as the standard time reference for international communication, aviation, maritime navigation, scientific research, and other applications requiring precise timekeeping. It provides a common reference point for coordinating activities across different time zones and regions.

UTC is used by a wide range of organizations and industries worldwide, including telecommunications networks, internet protocols, financial markets, and global navigation systems like GPS. It serves as the basis for coordinating time-sensitive activities and ensuring synchronization across distributed systems.

Overall, Coordinated Universal Time (UTC) plays a crucial role in modern society, providing a standardized and universally accepted reference for timekeeping and synchronization. Its accuracy, stability, and global adoption make it an essential component of international communication, commerce, and scientific research.

Clock Synchronization:

Clock synchronization is the mechanism to synchronize the time of all the computers in the distributed environments or system.

Assume that there are three systems present in a distributed environment. To maintain the data i.e. to send, receive and manage the data between the systems with the same time in synchronized manner you need a clock that has to be synchronized. This process to synchronize data is known as Clock Synchronization.

Synchronization in distributed system is more complicated than in centralized system because of the use of distributed algorithms. As the distributed systems has its own clock. The time among the clocks may also vary. So, it is possible to synchronize all the clocks in distributed environment.

Types of Clock Synchronization

· Physical Clock Synchronization

· Logical Clock Synchronization

Synchronizing Physical Clocks:

In physical clock synchronization, all the computers will have their own clocks. The physical clocks are needed to adjust the time of nodes. All the nodes in the system can share their local time with all other nodes in the system. The time will be set based on UTC (Universal Coordinate Timer).

The availability of synchronized clocks simplifies many problems in distributed systems. Air-traffic control systems rely on accurate timekeeping to monitor flight paths and avoid collisions. Some security mechanisms depend on the physical times of events, so a loss of synchronization may be a potential security lapse.

Three main problems have been studied in the area of physical clock synchronization:

External Synchronization:

External Synchronization synchronizes each clock in the distributed system with a UTC. The goal of external synchronization is to maintain the reading of each clock as close to the UTC as possible. A time server is a machine that provides accurate time information to be used as a reference by other machines. The NTP (Network Time Protocol) is an external synchronization protocol that runs on the Internet and coordinates a number of time servers. This enables a large number of computers connected to the Internet to synchronize their local clocks to within a few milliseconds from the UTC. NTP takes appropriate recovery measures against possible failures of one or more servers as well as the failure of links connecting the servers

Internal Synchronization:

Internal synchronization synchronizes the clocks in the distributed system with one another. The goal of internal synchronization is to keep the readings of a system of autonomous clocks closely synchronized with one another, despite the failure or malfunction of one or more clocks. These clock readings may not have any connection with UTC or GPS time—mutual consistency is the primary goal.

Phase synchronization:

Many distributed computations run in phases: in a given phase, all processes execute some actions, which are followed by the next phase. A phase clock is an integer-valued variable that is incremented each time a phase completes. Each process has its own copy of the phase clock.

In the clock phase synchronization problem, we assume a synchronous model where all phase clock variables are incremented in unison, as if all of them are driven by the same clock. Clearly, once all the phase variables are equal, they remain so forever, and synchronization becomes unnecessary. However, due to transient failures, phase clocks may occasionally differ, so that while all the nonfaulty clocks tick as 1,2,3,4,…, the faulty clock might tick as 6,7,8,9,… during the same time.

A clock phase synchronization algorithm guarantees that starting from an arbitrary configuration, eventually the values of all the phase clocks become identical.

Algorithms for Physical Clock Synchronization:

Clocks are one of the most important components of computers and other devices. However, for various factors, these clocks may drift from standard frequency or degrade and may gain or loose time with respect to the reference clock and this time difference between the two clocks is called clock skew.

This clock skew may gradually increase and eventually cause de-synchronization of the computer clock from the reference clock, which could affect their normal operation. Therefore it requires synchronization of the computer clock with the reference clock to minimize clock skew.

Several algorithm and protocols proposed for synchronizing physical clocks:

· Cristian Algorithm
· Berkeley Algorithm
· Network Time Protocol (NTP)

Cristian Algorithm:

The Cristian Algorithm is a simple protocol used for time synchronization in distributed systems. It addresses the problem of coordinating time among processes in a distributed environment where each process operates with its own local clock, which may be unsynchronized with other clocks in the system.

In this method, a client obtains the data from a special host (called the time server) that contains the reference time obtained from some precise external source. Upon request, the server process supplies the time according to its clock. The main idea behind the Cristian Algorithm is to use a time server as a reference point to synchronize the clocks of other processes in the system.

Cristian observed that while there is no upper bound on message transmission delays in an asynchronous system, the round-trip times for messages exchanged between pairs of processes are often reasonably short – a small fraction of a second. He describes the algorithm as probabilistic: the method achieves synchronization only if the observed round-trip times between client and server are sufficiently short compared with the required accuracy.

Here’s how the algorithm works:

Initialization: One of the processes in the distributed system is designated as the time server. The time server is assumed to have a relatively accurate and reliable clock, such as an atomic clock or a network time server.
Request for Time: When a client process needs to synchronize its clock, it sends a request to the time server for the current time.
Response from Time Server: Upon receiving the time request, the time server replies with its current time according to its own clock.
Time Adjustment: The client process adjusts its local clock based on the time received from the time server. Since network latency may introduce a delay in the transmission of the time request and response, the client process typically estimates the network delay and compensates for it when adjusting its clock.
Accuracy Considerations: The accuracy of time synchronization using the Cristian Algorithm depends on factors such as network latency, the stability of the time server’s clock, and the frequency of time synchronization requests. To achieve higher accuracy, clients may perform multiple time synchronization requests and average the results.

Basic Idea of Cristian Algorithm: If client wants to correct its time as per server time, then it will make the request to the time server and correct accordingly.

Cristian Algorithm is based on client-server concept makes use of RPC (remote Procedure Call)

It makes use of UTC, i.e., Co-ordinated Universal Time.

The process on the client issues RPC to the time server at time T₀ to obtain the time.

The client process fetches the response from the clock server at time T₁and calculates the new synchronized client clock time by-

T_CLIENT = T_SERVER + (T₁ – T₀)/2

Where T_CLIENT denotes the synchronized clock time, T_SERVER denotes the clock time returned by the server, T₀ denotes the time at which the client process sent the request and T₁ denotes the time at which the client process received the response.

Synchronized time on the client:

Here,

T₀ = 10:25:10

T_SERVER= 10:25:13

T₁= 10:25:14

T_CLIENT= T_SERVER + (T₁-T₀)/2

= 10:25:13 + (10:25:14-10:25:10)/2

= 10:25:13 + 00:00:04/2

= 10:25:13 + 00:00:02

= 10:25:15

Discussion of Cristian’s Algorithm:

Cristian’s method suffers from the problem associated with all services implemented by a single server: that the single time server might fail and thus render synchronization temporarily impossible. Cristian suggested, for this reason, that time should be provided by a group of synchronized time servers, each with a receiver for UTC time signals. For example, a client could multicast its request to all servers and uses only the first reply obtained. The problem of dealing with faulty clocks is partially addressed by the Berkeley algorithm.

Berkley Algorithm:

Berkley Algorithm is a physical clock synchronization algorithm used in distributed system. A well-known algorithm for internal synchronization is the Berkeley algorithm. The Berkeley Algorithm, developed by Gustavo Alonso, Vincent Shoup, and Charles T. Price in 1989, is a time synchronization algorithm for distributed systems. Similar to the Cristian Algorithm, the Berkeley Algorithm addresses the problem of clock synchronization among processes in a distributed environment where each process operates with its own local clock, which may be unsynchronized with other clocks in the system. However, the Berkeley Algorithm extends the idea by introducing a more sophisticated mechanism for time synchronization.

The Berkeley Algorithm offers several advantages over simpler time synchronization algorithms like the Cristian Algorithm. By collecting clock offset information from multiple processes and computing an average offset value, the Berkeley Algorithm can compensate for variations in clock skew among different processes, resulting in more accurate and reliable time synchronization.

Overall, the Berkeley Algorithm provides a robust mechanism for time synchronization in distributed systems, particularly in scenarios where higher accuracy and reliability are required. However, it may introduce additional overhead due to the collection and processing of clock offset information from multiple processes.

In Berkeley algorithm, an individual node is chosen as the master node. This node is the main node in the network which acts as a master and rest of the nodes act as a slave. If master node fails any slave in the network can take over.

Master node periodically request time from all its slave nodes. When the slave nodes send their responses, master nodes calculates average time difference between all the clock times received and the clock time given by master’s system itself.

This average time difference is added to the current time at master’s system clock and broadcasted over the network. Thus synchronization is achieved.

Pass 1: The master node requests timestamps from all the slave nodes.

Pass 2: Slave nodes respond their timestamps to master node.

Pass 3: Master node calculates average time difference between all the clock times received and the clock time given by master’s system itself.

= (+10+20+0-10)/4

= 20/4

= 5

Pass 4: This average time difference is added to the current time at master’s system clock and broadcasted over the network.

The Berkeley algorithm eliminates readings from faulty clocks. Such clocks could have a significant adverse effect if an ordinary average was taken so instead the master takes a fault-tolerant average. That is, a subset is chosen of clocks that do not differ from one another by more than a specified amount, and the average is taken of readings from only these clocks.

Network Time Protocol (NTP):

NTP Algorithm is a physical clock synchronization algorithm used in distributed system. It is a protocol that helps the computer clock times to be synchronized in a network. NTP is an elaborate external synchronization mechanism designed to synchronize clocks on the internet with the UTC.

The Network Time Protocol (NTP) is a widely used protocol for synchronizing the clocks of computer systems over a network. It is designed to achieve high accuracy and reliability in time synchronization, allowing distributed systems to maintain consistent and accurate time across different devices and networks.

It is not practical to equip every computer with atomic clocks or GPS satellite receivers. Cost is a major factor. So, these computers use the NTP to synchronize the clocks. The NTP service is provided by a network of servers located across the Internet. Primary servers are connected directly to a time source such as a radio clock receiving UTC; secondary servers are synchronized, ultimately with primary servers. The servers are connected in a logical hierarchy called a synchronization subnet whose levels are called strata. Primary servers occupy stratum 1: they are at the root. Stratum 2 servers are secondary servers that are synchronized directly with the primary servers; stratum 3 servers are synchronized with stratum 2 servers, and so on. The lowest-level (leaf) servers execute in users’ workstations.

The NTP network is organized into a hierarchical structure, with multiple levels of time servers. At the top of the hierarchy are stratum 0 servers, which are directly connected to highly accurate reference clocks. Stratum 0 servers synchronize with each other and serve as sources of time for stratum 1 servers. Stratum 1 servers, in turn, synchronize with stratum 0 servers and serve as sources of time for stratum 2 servers, and so on. In general, stratum i computers act as time servers for the stratum (i + 1) computers. The synchronization subnet can reconfigure as servers become unreachable or failures occur. If, for example, a primary server’s UTC source fails, then it can become a stratum 2 secondary server. If a secondary server’s normal source of synchronization fails or becomes unreachable, then it may synchronize with another server.

Stratum 0 servers provide the most accurate time reference, followed by stratum 1 servers, stratum 2 servers, and so on. Client devices typically synchronize with stratum 2 or higher servers to obtain accurate time information.

The Network Time Protocol (NTP) provides a robust and scalable solution for time synchronization in distributed systems, enabling accurate and reliable timekeeping across diverse networks and devices. NTP is widely used in various applications, including network infrastructure, telecommunications, financial services, and scientific research, where precise time synchronization is essential.

Logical Time and Logical Clocks:

In distributed systems, there is no global clock exists rather it uses logical clocks to synchronize the events in the system. Logical Clocks refer to implementing a protocol on all machines within distributed system, so that the machines are able to maintain consistent ordering of events within some virtual time span.

A logical clock is a mechanism for capturing chronological and causal relationships in a distributed system. Distributed systems may have no physically synchronous global clock, so a logical clock allows global ordering on events from different processes in such systems.

The Logical Time in distributed system is used to maintain the consistent ordering of events. Logical time is not based on timing but on the ordering of events.

Logical clocks do not need exact time. So, absolute time is not a concern in logical clocks. Logical clocks just bothers about the message to be delivered or not about the timings of the events occurred.

The most common logical clock synchronization algorithm for distributed system is Lamport’s algorithm. It is used in the situation where ordering is important not the time.

In a classic paper, Lamport (1978) showed that although clock synchronization is possible, it need not be absolute. If two processes do not interact, it is not necessary that their clocks be synchronized because the lack of synchronization would not be observable and thus could not cause problems. Furthermore, he pointed out that what usually matters is not that all processes agree on exactly what time it is, but rather that they agree on the order in which events occur.

Happened–Before Relation:

The “happened-before” relation is a concept used in distributed systems to define a partial ordering of events based on their causality. It helps establish the order of events in a distributed system even when events occur concurrently across different processes or components. The happened-before relation is a fundamental concept in logical clock algorithms such as Lamport clocks and vector clocks. The happened-before relation establishes a partial ordering of events in a distributed system. It does not necessarily provide a total ordering of events but instead defines a set of rules for comparing the ordering of events based on their causality.

In distributed system, the happened-before relation (denoted: ->) is a relation between the result of two events, such that if one event should happen before another event, the result must reflect that, even if those events are in reality executed out of order (usually to optimize program flow). This involves ordering events based on the potential causal relationship of pairs of events in a concurrent system, specially asynchronous distributed systems. It was formulated by Leslie Lamport.

The happened-before relation is formally defined as the least strict partial order on events such that:

· If a and b are events in the same process, and a occurs before b, then a ->b is true.

· If a is the event of a message being sent by one process, and b is the event of the message being received by another process, then a -> b is also true. A message cannot be received before it is sent, or even at the same time it is sent, since it takes a finite, nonzero amount of time to arrive.

If two events happen in different isolated processes (that do not exchange messages directly or indirectly via third-party processes), then the two processes are said to be concurrent, that is neither a->b nor b->a is true.

Rules for Establishing Happened-Before:

Within the Same Process: If event A occurs before event B within the same process, then A happened-before B. This is straightforward and reflects the natural temporal order of events within a process.
Message Ordering: If event A is the sending of a message and event B is the receipt of the same message, then A happened-before B. This rule ensures that message receipt events occur after their corresponding message sending events.
Transitivity: If event A happened-before event B, and event B happened-before event C, then event A also happened-before event C. This rule ensures the consistency of the happened-before relation across multiple events.

Happens-before is a transitive relation, so if a->b and b -> c, then a -> c. If two events, x and y, happen in different processes that do not exchange messages (not even indirectly via third parties), then x->y is not true, but neither is y -> x. These events are said to be concurrent, which simply means that nothing can be said (or need be said) about when the events happened or which event happened first.

The happened-before relation, denoted by -> is illustrated for the case of three processes p₁, p₂ and p₃ in figure above. It can be seen that a->b, since the events occur in this order at process p₁ and similarly c->d. Furthermore, b->c, since these events are the sending and reception of message m1, and similarly d->f. Combining these relations, we may also say that, for example, a->f.

Lamport Clocks:

Lamport clocks, named after computer scientist Leslie Lamport, are a logical clock algorithm used in distributed systems to order events based on their potential causality. They provide a way to timestamp events in a distributed system, allowing processes to reason about the ordering of events even in the absence of a global clock. Lamport clocks are simple and lightweight, making them suitable for various distributed systems applications.

Back in the late 1970’s Leslie Lamport wrote a paper in which he introduced logical clocks. The paper had three main points: firstly, if a distributed system is built up of multiple independent servers, and some of the servers never interact with each other, then there is little theotical need for the non-interacting server clocks to be sychronised since any difference would never be observed. Secondly, in distributed systems, he showed that time is less important than agreement across components of the order of events in which things occur. And finally, he provided algorithms for partial causal ordering and an extension which provides total ordering.

Lamport clocks are event counters that are incremented with every interaction. They are incremented and sent as a part of a message by a sending process and are in turn incremented by a receiving process before it sends it on to the business logic. The value produced by a Lamport clock is a Lamport timestamp. Lamport clocks cannot tell us if a message was concurrent, and cannot be used to infer causality between events. Vector clocks are a more sophisticated variant which gives us more guarantees, including knowledge of concurrency & causal history.

Overall, Lamport clocks provide a practical and effective means of ordering events in distributed systems based on potential causality. Their simplicity, scalability, and independence from clock synchronization mechanisms make them a valuable tool for maintaining consistency and correctness in distributed computations.

Advantages of Lamport clocks:

Partial Ordering of Events: Lamport clocks establish a partial ordering of events in a distributed system. While Lamport clocks may not reflect the exact chronological order of events, they ensure that events are ordered according to potential causality. This partial ordering is crucial for maintaining consistency and correctness in distributed computations.
Causality Tracking: Lamport clocks enable processes to track the causality relationships between events. By assigning a Lamport timestamp to each event, processes can determine whether one event causally precedes, follows, or is concurrent with another event. This information is valuable for reasoning about dependencies and enforcing consistency in distributed systems.
Lightweight and Scalable: Lamport clocks are lightweight and scalable, as each process only needs to maintain a single integer timestamp. The overhead of Lamport clock maintenance remains low even as the size of the distributed system grows, making Lamport clocks suitable for large-scale distributed deployments.
FIFO Message Ordering: Lamport clocks ensure First-In-First-Out (FIFO) message ordering among processes. If a process sends multiple messages, Lamport timestamps are used to order the messages at the receiving end. This property helps maintain message ordering consistency and prevents out-of-order message delivery.
Synchronization Independence: Lamport clocks are independent of clock synchronization mechanisms and do not rely on synchronized physical clocks. This independence makes Lamport clocks robust to variations in clock speeds, network delays, and clock drift, ensuring consistent behavior across different environments.
Simple Implementation: Implementing Lamport clocks is relatively straightforward, requiring only the assignment and comparison of integer timestamps. This simplicity makes Lamport clocks easy to understand, implement, and integrate into distributed systems.

Vector Clocks

A vector clock is a mechanism used in distributed systems to capture causality relationships between events occurring at different nodes. It extends the concept of Lamport timestamps by associating a vector with each process or node in the system. Each element of the vector corresponds to a process, and the value of each element represents the number of events that have occurred at that process. Vector clocks are used to determine the partial ordering of events across distributed nodes.

Vector clocks are a logical clock algorithm used in distributed systems to capture causality relationships between events across different processes. They provide a mechanism for ordering events in a distributed system, even when there is no global clock available. Vector clocks are commonly used in distributed databases, distributed file systems, and other distributed systems where tracking event causality is essential.

Vector clocks are a powerful tool for tracking event causality in distributed systems and are widely used in various distributed algorithms, including distributed snapshot algorithms, conflict resolution mechanisms, and distributed consensus protocols.

Overall, vector clocks provide a flexible and efficient mechanism for tracking causality, detecting concurrency, resolving conflicts, and capturing consistent snapshots in distributed systems. They play a crucial role in ensuring consistency, correctness, and scalability in distributed computations and are widely used in various distributed algorithms and protocols.

Here’s how vector clocks work:

Initialization: Each process in the distributed system maintains a vector clock, which is an array with an entry for each process/node in the system. Initially, all entries in the vector clock are set to zero.
Event Timestamping: When a process performs an event (e.g., sends a message, receives a message, or enters a critical section), it increments its own entry in the vector clock, indicating that the event occurred.
Message Exchange: When a process sends a message to another process, it includes its current vector clock in the message.
Message Reception: When a process receives a message with a vector clock from another process, it compares each element of the received vector clock with its own vector clock. For each element in the received vector clock, the process updates its corresponding entry in its own vector clock to be the maximum value between the two corresponding entries.
Causality Comparison: To compare the causality relationship between two events, each process compares its vector clock with the vector clock associated with the events. If the vector clock of event A is less than or equal to the vector clock of event B for all components and at least one component is strictly less than in B, then event A causally precedes event B.
Event Ordering: Based on the causality comparison, events can be partially ordered. If event A causally precedes event B, then A is considered to have occurred before B. If event A and event B are concurrent (neither causally precedes the other), then neither event is considered to have occurred before the other.

Advantages of Vector Clock:

Vector clocks offer several advantages in distributed systems, primarily related to their ability to capture causal relationships between events across processes. Here are some key advantages:

Causality Tracking: Vector clocks provide a mechanism for tracking causality relationships between events in a distributed system. By maintaining a vector of integer counters, each representing the number of events observed by a particular process, vector clocks allow processes to determine the causal relationship between events accurately.

Partial Ordering of Events: With vector clocks, distributed systems can establish a partial ordering of events that respects causality. This partial ordering enables processes to reason about the dependencies and relationships between events, allowing for consistency and correctness in distributed computations.

Concurrency Detection: Vector clocks help in detecting concurrency among events in a distributed system. If two events have overlapping but non-identical vector clocks, they are considered concurrent. This information is valuable for detecting and resolving conflicts in distributed systems, such as concurrent updates to shared data.

Conflict Resolution: Vector clocks can be used to resolve conflicts that arise in distributed systems due to concurrent updates or operations. By comparing vector clocks associated with conflicting events, processes can determine the causal relationship between events and apply conflict resolution strategies accordingly.

Distributed Snapshotting: Vector clocks are commonly used in distributed snapshot algorithms to capture consistent global snapshots of distributed systems. By incorporating vector clocks into snapshot recording and aggregation, distributed systems can capture a consistent view of the system’s state, even in the absence of a global clock.

Scalability: Vector clocks scale well with the size of the distributed system. Since each process maintains its own vector clock, the overhead of vector clock maintenance remains proportional to the number of processes in the system rather than the total number of events or messages exchanged.

Vector Clock versus Lamport Clock:

Lamport clocks and Vector clocks are both logical clock algorithms used in distributed systems to order events and capture causal relationships between them. Lamport clocks are simpler and more lightweight, making them suitable for scenarios where only partial ordering of events is required. Vector clocks, on the other hand, provide more detailed information about event dependencies and are better suited for applications that require accurate causality tracking and concurrency detection in distributed systems.

Here’s a comparison between Lamport clocks and Vector clocks:

Representation:

Lamport Clocks: Lamport clocks are represented by a single integer timestamp associated with each event. The Lamport timestamp is typically denoted as a Lamport logical time.
Vector Clocks: Vector clocks are represented by a vector of integer counters, with each counter corresponding to a process in the distributed system. Each process maintains its own vector clock, and the vector clock of an event reflects the local time of each process at the time of the event.

Causality Relationship:

Lamport Clocks: Lamport clocks establish a partial ordering of events based on their Lamport timestamps. If event A has a lower Lamport timestamp than event B, then event A occurred before event B. Lamport clocks provide a total ordering of events only if all events are totally ordered.
Vector Clocks: Vector clocks also establish a partial ordering of events, but they do so by comparing vector timestamps rather than individual Lamport timestamps. Vector clocks provide a more accurate representation of causality relationships by capturing the dependencies between events across multiple processes. If the vector clock of event A is less than or equal to the vector clock of event B for all components and at least one component is strictly less than in B, then event A causally precedes event B.

Concurrency Detection:

Lamport Clocks: Lamport clocks cannot directly detect concurrency between events. Concurrent events may have identical Lamport timestamps, making it challenging to determine their relationship.
Vector Clocks: Vector clocks can detect concurrency between events. If two events have overlapping but non-identical vector clocks, they are considered concurrent. Vector clocks provide more information about the causal relationships between events, allowing for more precise concurrency detection.

Message Ordering:

Lamport Clocks: Lamport clocks ensure First-In-First-Out (FIFO) message ordering among processes. Lamport timestamps are used to order events at the receiving end based on message receipt.
Vector Clocks: Vector clocks also ensure FIFO message ordering. However, they provide more flexibility in handling concurrent messages and resolving conflicts based on vector timestamp comparisons.

Complexity:

Lamport Clocks: Lamport clocks are simpler and require less overhead than vector clocks. They consist of single integer timestamps and are easy to implement and understand.
Vector Clocks: Vector clocks are more complex than Lamport clocks due to the maintenance of vector timestamps. However, they provide more information about event dependencies and enable more precise reasoning about causality relationships.

Global States:

The global state of a distributed system consists of the local states of its component processes. Any computation that needs to compute the global state at a given time has to read the local states of every component process at that time. “Global State” refers to the collective state of all processes and communication channels in the system at a particular point in time. It represents a snapshot of the distributed system’s configuration, including the states of individual processes, the messages in transit between processes, and the state of communication channels.

The global state of a distributed system is the set of local states of each individual processes involved in the system plus the state of the communication channel.

Global Snapshot= Global State=

Individual state of each process in the distributed system

Individual state of each communication channel in the distributed system

Global State:

· Capture the instantaneous state of each process

· Capture the instantaneous state of each communication channel, i.e., messages in transit on the channels

It is often desirable to determine whether a particular property is true of a distributed system as it executes. We’d like to use logical time to construct a global view of the system state and determine whether a particular property is true. A few examples are as follows:

Distributed garbage collection: An object is considered to be garbage if there are no longer any references to it anywhere in the distributed system. The memory taken up by that object can be reclaimed once it is known to be garbage. To check that an object is garbage, we must verify that there are no references to it anywhere in the system.

In above figure process p₁ has two objects that both have references – one has a reference within p₁ itself, and p₂has a reference to the other. Process p₂ has one garbage object, with no references to it anywhere in the system. It also has an object for which neither p₁ nor p₂ has a reference, but there is a reference to it in a message that is in transit between the processes. This shows that when we consider properties of a system, we must include the state of communication channels as well as the state of the processes.

Distributed termination detection: The problem here is how to detect that a distributed algorithm has terminated. Detecting termination is a problem that sounds deceptively easy to solve: it seems at first only necessary to test whether each process has halted. To see that this is not so, consider a distributed algorithm executed by two processes p₁ and p₂, each of which may request values from the other. A process is either active or passive – a passive process is not engaged in any activity of its own but is prepared to respond with a value requested by the other. Suppose we discover that p₁is passive and that p₂ is passive (Figure below). To see that we may not conclude that the algorithm has terminated, consider the following scenario: when we tested p₁ for passivity, a message was on its way from p₂, which became passive immediately after sending it. On receipt of the message, p₁ became active again – after we had found it to be passive. The algorithm had not terminated.

Cut in a Distributed System:

In distributed systems, a “cut” refers to a logical separation between processes or components within the system. It is a way to conceptually divide the system into two or more disjoint subsets, often for analysis or reasoning about system properties, behaviors, or failures. Cuts play a crucial role in understanding distributed systems and are used in various scenarios, including fault tolerance, consistency, and scalability analysis.

Cuts provide a powerful abstraction for understanding and reasoning about the behavior and properties of distributed systems. By partitioning the system into logical subsets, cuts enable the analysis of complex interactions, dependencies, and failure scenarios, ultimately leading to the design of more robust, scalable, and efficient distributed systems.

Here are a few common types of cuts in a distributed system:

Global State Cut: A global state cut divides the distributed system into two subsets such that all events that occurred before the cut are considered as part of one subset, and all events that occur after the cut are considered as part of another subset. Global state cuts are often used in distributed snapshot algorithms, such as the Chandy-Lamport Algorithm, to capture a consistent snapshot of the system’s state.

Failure Cut: A failure cut divides the distributed system into subsets based on the occurrence of failures. For example, in a system where processes can fail independently, a failure cut might partition the system into subsets containing failed and non-failed processes. Failure cuts are useful for analyzing fault tolerance mechanisms, such as replication, redundancy, or recovery strategies.

Consistency Cut: A consistency cut divides the distributed system into subsets based on the consistency properties of data or operations. For example, in a distributed database, a consistency cut might partition the system into subsets representing consistent or inconsistent states of data. Consistency cuts are essential for reasoning about data consistency models, such as eventual consistency, strong consistency, or causal consistency.

Communication Cut: A communication cut divides the distributed system into subsets based on communication patterns or message flows. For example, in a messaging system, a communication cut might partition the system into subsets representing sender-receiver pairs or message exchanges between processes. Communication cuts are useful for analyzing message delivery, latency, and reliability in distributed systems.

Chandy Lamport Algorithm:

Chandy and Lamport [1985] describe a ‘snapshot’ algorithm for determining global states of distributed systems. The Chandy-Lamport Algorithm, also known as the Distributed Snapshot Algorithm, is a distributed algorithm used to capture a consistent global snapshot of a distributed system. It allows for the observation of distributed computations at a specific point in time, providing a consistent view of the system’s state across all participating processes. The algorithm is commonly used in distributed debugging, monitoring, and checkpointing.

The Chandy-Lamport Algorithm guarantees that the captured snapshot is globally consistent, meaning that it reflects a valid system state where no inconsistencies arise due to message ordering or concurrency issues. Applications of the Chandy-Lamport Algorithm include distributed debugging, distributed deadlock detection, and distributed checkpointing for fault tolerance.

Here’s an overview of how the Chandy-Lamport Algorithm works:

Initiation: The algorithm starts when a process, known as the initiator, triggers the snapshot process by initiating a local snapshot at its own state.
Marker Propagation: The initiator process sends a special control message called a marker to all its outgoing communication channels. Upon receiving a marker, each process records its local state and continues propagating the marker to its outgoing channels.
Recording Local State: Upon receiving a marker, each process records its local state. This includes the process’s current state and the state of all incoming communication channels at that moment.
Channel State Recording: Each process also records the state of incoming communication channels upon receiving a marker. This ensures that the snapshot captures the state of messages in transit.
Termination Detection: Once a process has recorded its local state and the state of all incoming channels, it can determine if it has completed the snapshot process. This is done by checking if it has received markers from all incoming channels and if it has sent markers on all outgoing channels.
Snapshot Construction: After all processes have completed their snapshot recording, the collected states are aggregated to form a consistent global snapshot of the distributed system. This snapshot captures the states of all processes and communication channels at a specific point in time.