Components for load distributing algorithm


Transfer Policy:
This policy determines whether the node is in a suitable state to share the load. Most of the transfer policies are threshold based policies, If a load at a node exceeds a threshold value T, then the node is overloaded and act as a sender. If the load at the node falls below a threshold T, then the load is under loaded and acts as a receiver.
Selection Policy:
This policy selects a task for transfer. Simplest approach is to select the newly originated task at the node which has made this node as the sender for task transfer, it will also be a cheap operation as it will be a non preemptive task transfer. The basic criterion which is to be satisfied during selection of a task is that the overhead incurred in task transfer must be less than the reduction in response time of the task and long-lived task satisfies this condition.  Another factor which is to be considered during selection of tasks is that the task must have fewer location dependent system calls since such calls are to be executed on the same machine where the task has been originated.
Location Policy:
This policy selects the node where the selected task is to be transferred. Simplest approach to find such node is PollingIn polling, one node calls another node to determine whether it is in a state of load sharing. Nodes can be called serially or parallaly. A node can be selected for polling randomly or on nearest neighbor basis. An alternative to polling is to distribute a query to all nodes to find the available nodes.
Information Policy:
This policy is responsible for determining when the system state is to be corrected, from where it is to be corrected and what information is to be corrected.
It is of three types:
Demand Driven:
In this policy, the node starts correcting the state of other nodes when it becomes a sender or receiver. This policy is basically a dynamic policy. This policy can be sender initiated, receiver initiated or symmetrically initiated. In sender initiated, a sender looks for receiver to give their load, In receiver initiated, receiver searches for sender, take their load, and symmetrically initiated is the combination of both where the collection of the system state is started whenever there is need of extra processing power.
In this policy, the nodes exchange their system information periodically and on the basis of this information, task transfer is made. This policy does not adapt its activities according to system state change for example if the system is already overloaded then exchanging the system state information periodically will further worsen the situation.
State Change Driven Policy:
In this policy, a node disseminates its state information to other nodes whenever its state changes by certain degree. This policy differs from demand driven policy as in this case, the nodes disseminate their state information rather than collecting the state information of other nodes. Under centralized approach, a node disseminates its information t centralized collection point whereas in case of decentralized approach, a node disseminate to peers.
There are two views of stability:
The queuing theoretic Perspective:
Whenever the arrival rate of the task is more than the arrival service rate of the system, then CPU queue length rose without count and the system becomes unstable. An Algorithm is effective under a given set of conditions if it results in improvement of the system relative to a system which does not use this algorithm. An effective algorithm is always  stable, on the other hand, stable algorithms may not be effective.
The Algorithmic Perspective:
If an algorithm performs fruitless actions, indefinitely with the finite probability then the algorithm is unstable. Consider the case of the Processor Thrashing, In this, if the task transfer to the receiver exceeds its queue length, the point of overload then the task will be further transferred to another node and this process will go.

DISTRIBUTED SYSTEM covered following topics in these notes.

Post a Comment

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.