1. INTRODUCTION:

Distributed System is a collection of computers connected via the high-speed communication network. In the distributed system, the hardware and software components communicate and coordinate their actions by message passing. Each node in distributed systems can share their resources with other nodes. So, there is a need for proper allocation of resources to preserve the state of resources and help coordinate between the several processes. To resolve such conflicts, synchronization is used. Synchronization in distributed systems is achieved via clocks.

The physical clocks are used to adjust the time of nodes. Each node in the system can share its local time with other nodes in the system. The time is set based on UTC (Universal Time Coordination). UTC is used as a reference time clock for the nodes in the system.

The clock synchronization can be achieved in 2 ways: External and Internal Clock Synchronization.
 

1. External clock synchronization is the one in which an external reference clock is present. It is used as a reference and the nodes in the system can set and adjust their time accordingly.

 

2. Internal clock synchronization is the one in which each node shares its time with other nodes and all the nodes set and adjust their times accordingly.

 


There are 2 types of clock synchronization algorithms: Centralized and Distributed.
 

1. Centralizedis the one in which a time server is used as a reference. The single-time server propagates it’s time to the nodes and all the nodes adjust the time accordingly. It is dependent on a single time server so if that node fails, the whole system will lose synchronization. Examples of centralized are- Berkeley Algorithm, Passive Time Server, Active Time Server, etc.

 

2. Distributedis the one in which there is no centralized time server present. Instead, the nodes adjust their time by using their local time and then, taking the average of the differences of time with other nodes. Distributed algorithms overcome the issue of centralized algorithms like the scalability and single point failure. Examples of Distributed algorithms are – Global Averaging Algorithm, Localized Averaging Algorithm, NTP (Network time protocol), etc.

 

A distributed system is a collection of one or more processing units connected via a communications network. Each system is an independent unit having its own processor, memory, and devices which can process programs on a stand alone basis. Any unit may break down a large problem into smaller pieces to be concurrently executed upon other units. The communication links allow the units to exchange information, such as status reports. The power behind a distributed system comes from its operating system, concurrent programming language and communications capabilities. The operating system or language must contain the mechanisms and primitives which are used by a distributed program to utilize the features of the distributed system.

1.2 SYNCHRONIZATION In general, when two or more processes share a resource, such as common memory or a device, a mechanism for communication between the processes must exist. This communication is to allow processes to know each other's states so that the use of a resource does not conflict with another process's need for that resource. Such conflicts cause contention of ownership, deadlock or invalid data requisition. Implementations of synchronous commands between processes are called primitives and are discussed in sections four and five.

2. WHY DO WE NEED SYNCHRONIZATION ?

Synchronization between processes is needed to ensure validity of information which is being shared in a distributed system. A typical example is two or more processes attempting to update a common variable, as in figure i.

Process P0 calls two parallel processes, P1 and P2, which each act upon a common variable X. Synchronization is needed to provide mutual exclusion of access to the variable X to ensure the end value of X. Processes P1 and P2 are not atomic operations (not non-divisible). Figure 2 shows an example of the assembler-like code that may be run as processes P1 and P2.

An overview of synchronization techniques

The concurrent processing of P1 and P2 could occur on a single processor system where concurrency is implemented via time slicing, or on a multi-processor architecture where each process runs on its own processor. In either case, there is no way of predicting the final value of X. In the single processor scenario, the expected order of the three lines of assembler code for P1 or P2 could easily be mixed due to time slicing and corrupt the atomic expectation of the process. Figure 3 shows two of the 720 possible interleavings of P1 and P2. In a multi-processor system, the delay in fetching the value of X from the common memory could also cause similar results. A practical application where this situation must be considered is an airline scheduler. A person desiring a reservation typically calls a local reservation office which will assign him a seat on a particular flight and adjust the total seating available for that flight. The airline reservation system is a large distributed system consisting of nodes in many cities and states all attempting to access/update a central database. The distances and multiple systems involved could easily cause information to be updated incorrectly if a synchronization scheme was not in place.

3. LEVELS OF SYNCHRONIZATION

Synchronization can occur at various hardware and software levels. While the intent of this paper is to focus on the software primitives available to a programmer, the topic of clocks and timing deserves to be mentioned lightly.

4. CLOCKS AND TIMING

Various processors in a distributed system may be running at different clock speeds. This situation can cause timing problems between processors and tasks communicating among them. Many proposed solutions have been presented. Some solutions designate a node to be a time server in the distributed system, known as a centralized system concept. This node supplies timing information to all other processors in the distributed system. The information could be an update of the system time to each node to provide time synchronization, or be an unique value to determine ordering among the total processes in the system. Detailed information can be found in [15,20].

5. SOFTWARE IMPLEMENTATIONS

Implementing synchronization primitives such as shared memory access, semaphores, condition critical regions, guarded statements and message passing is non-trivial. Many issues including ease of use, programmer abilities, languages and operating systems are a few of the major considerations. Thus far, the majority of the proposed concurrent languages have defined a basic set of synchronization primitives in the form of functions or structures which a programmer may use without getting lost in the lower level details of interprocess communications. The level of these primitives is fairly common but still may vary a bit in various languages. For example, one language may include semaphores as a primitive while another may only have primitives which may be used to create semaphores. Some of the languages proposed and/or implemented are CSP, Planet, CSP80, RBCSP, ECSP, PLITS, Clouds, Modula-2, Ada, Concurrent Pascal and the low level language OCCAW. Each has its own style or class of primitives. The existing synchronization primitives are broadly categorized into two groups (based on the method of interprocess communication): shared variables and message passing. Shared variables occur when two or more processes exchange information by the means of common variables located in one area of memory on one system. The example in section three shows the type of problem that ~ay occur by using shared variables: lack of mutual exclusion. For detailed discussions see [1,2,9,13,17]. Message passing allows the sharing of information between processes through the act of notifying a process when a particular condition occurs. Messages can be simple as when a process sends a signal message with no content whose purpose is to notify another process that it has reached a certain state. A more complex system of message passing is the dynamic creation of channels over which data is passed between active processes.

4.0 PRIMITIVES

4.1 SHARED VARIABLES :

This section discusses many of the primitives designed to solve the issues of synchronization. To aid in comparison of the different primitive types, a print spooler example is given in pseudo-code for several primitives. A print spooler is a group of processes which control a pool of printer resources. A printer may be requested from the printer pool by a user or task. The printer pool is searched to determine if a printer is available and that printer id is returned to the requesting process. If there are no printers available, then the spooler must wait for a printer. The method of waiting may be dependent upon the synchronization primitive used or other system criteria not discussed in this paper. Once a user or task has finished using the requested printer, it must return the printer to the printer pool. The two print spooler processes represented in pseudo-code are request-printer and release-printer.

Conclusion:

Distributed System is a collection of computers connected via the high speed communication network. In the distributed system, the hardware and software components communicate and coordinate their actions by message passing. Each node in distributed systems can share their resources with other nodes. So, there is need of proper allocation of resources to preserve the state of resources and help coordinate between the several processes. To resolve such conflicts, synchronization is used. Synchronization in distributed systems is achieved via clocks.

The physical clocks are used to adjust the time of nodes.Each node in the system can share its local time with other nodes in the system. The time is set based on UTC (Universal Time Coordination). UTC is used as a reference time clock for the nodes in the system.

The clock synchronization can be achieved by 2 ways: External and Internal Clock Synchronization.