Distributed Algorithms

Distributed Algorithm are algorithms designed to run large but limited set of processors that run similar programs. It runs on a distributed system that does not assume the previous existence of a central coordinator. A distributed system is a group of processors that do not share memory or a clock. Each process has its own memory and the processors use communication networks to communicate. Distributed algorithms are used in various practical systems, ranging from large computer networks to multiprocessor shared-memory systems. They also have a rich theory, which forms the subject matter for this course.

The development of distributed algorithms are different in nature from the development of centralized algorithms. Distributed system differs from centralized system in three essential respects Lack of knowledge of global state, Lack of a global time-frame and Non-determinism. Read more details pertaining to distributed algorithm below.

Distributed Algorithm: Distributed System vs Parallel System

Distributed system refers to the all computer applications where several computers or processors are interconnected in some way. It incorporates multiprocessor computers in which each processor has its own control unit, wide-area computer communication networks, local-area networks and systems of cooperating processes. Following are some points of comparison between Distributed System and Parallel System:

• In Distributed System, the systems are loosely coupled whereas in Parallel System, the systems are tightly coupled.
• In Distributed System, the primary issues are fault-tolerance, synchronization, scalability, etc. and in Parallel System, the main issues are increased and speed-up data handling capability.
• The events are partially ordered in both distributed system and parallel system,
• The difference between distributed system and parallel system is not always very clear.

Also Read: CATIA

Distributed Algorithm Applications

There are numerous applications of Distributed Algorithm in distributed system. In distributed system, nodes represent processes and the links represent communication channels.  Distributed Algorithm has their applications in

• Social networks
• Skype
• Bit Torrent
• Computational grids
• Sensor networks
• Internet banking
• Distance education
• Google earth

Also Read: Databases

Distributed Algorithm: Standard Problems

Although, Distributed Algorithm has its use in various applications but there are some standard problems too. Following are some common issues:

• Mutual Exclusion: It is a property of currency control introduced to proscribe race conditions. In this, one thread of execution never enters a critical section while a concurrent thread of execution is already accessing critical section.
• Leader election: It is a procedure of assigning a single process as the organizer of some task distributed among several computers (nodes). Once the leader election algorithm run, each node throughout the network acknowledges a particular, unique node as the task leader
• Replica management: It encompasses sharing information to ensure consistency between software or hardware components, to improve fault-tolerance, reliability and accessibility.
• Time synchronization: It refers to the time recovery, which achieves frequency synchronization, as opposed to full phase synchronization. It is used in telecommunication and automatic baud rate detection.
• Consensus: This algorithm closely work around some properties like Termination, Integrity, Validity and Agreement. Paxos algorithm and Raft algorithm are common algorithms used for solving consensus issues.
• Reliable broadcast: It is a communication primitive in distributed systems, which may have sequential, causal or total ordering. Integrity, Validity and Agreement are some properties of Reliable broadcast.

Also Read: NoSQL Databases

Distributed Algorithm vs Graph Algorithm

Distributed Algorithm has been compared with the Graph Algorithm because many problems in Distributed Algorithm are framed as Graph problem. Following are some points to give a clear view:

• Shortest path algorithm is used for Routing table computation.
• Spanning tree is used by Efficient broadcasting algorithm.
• Vertex coloring is used for the reuse of frequencies in wireless networks.
• The topology of a distributed system is a graph.
• The maximum flow between a pair of nodes in a graph is determined by Maxflow algorithm.

What do Distributed Algorithm Researchers do?

The researchers working in the field of Distributed Algorithm are responsible for the following activities:

• Describe different kinds of distributed computing environments, including network-based environments and shared-memory.
• Analyze the correctness, performance, and fault-tolerance of the algorithms.
• Identify problems to be resolved in those environments.
• Design new algorithms for the problems.
• Investigate problems that arise in practical distributed systems, comprising problems of data management, communication, synchronization, resource management, and distributed agreement