Distributed Computing aims at achieving higher execution speed than the one obtainable with uniprocessor system by exploiting the collaboration of multiple computing nodes interconnected in some fashion. The idea has been to partition a uniprocessor computing load into multiple units of execution and assigning them to the various processing nodes. The best possible speed up will obviously be obtained if the various partitions of the given computational task can run independently in parallel. However, since the various partitions of the task collaborate to achieve a common objective, the requirement of communication/interaction among these units of the given task can hardly be avoided.　Hence, the idea of distributed computing can be characterized by the following:

a) Partitioning and allocation of units of a task to various processing nodes of the system so as to achieve speed up.

b) The processing nodes of the system must be sharing the computational load of the system so as to be able to provide proper execution characteristics. All the processing nodes must be made busy as much as possible by receiving and executing multiple tasks.

This research considers the efforts made in both of the above said directions to identify an appropriate way of distributing the computational load across the processing nodes to achieve higher system throughput characteristics in terms of number of tasks executed per unit time.

l Multiple Task Allocation and Load Balancing in a Distributed Computing System (DCS)

A Distributed Computing System (DCS) is a network of workstations, personal computers and/or other computing systems. Such a system may be heterogeneous in the sense that the computing nodes may have different speeds and memory capacities. A DCS accepts tasks from users and executes different modules of these tasks on various nodes of the system. Various modules of a task have a precedence relation depicted by its task graph and their communicational requirements are given by the Inter Module Communication (IMC) matrix. A good number of task allocation algorithms have been proposed in the literature. These algorithms allocate a given task with their modules on to the DCS nodes and aim to minimize the turn around time of the given task. Such algorithms do not consider (both) the number of modules that can be accepted by the individual computing nodes and the memory capacity of the nodes. Factually, in DCS the nodes may share some specified load within their memory capacity constraints. Further the above mentioned algorithms consider only one given task. In this research we are considering the number of modules that can be accepted by individual nodes along with their memory capacities and arrival of multiple disjoint tasks to the DCS from time to time. We propose an algorithm that will allocate one or more tasks in the DCS when the allocator is invoked. This algorithm allocates the modules of the tasks, one at a time that will result in increased throughput of the system as well. Finally, there may be a situation that the given task is not allocated at all due to the high memory requirements of one or more modules of the task.

As it is a NP-Hard problem, still, algorithms proposed in the literatures with many heuristics are good to provide near optimal or sub optimal solutions. So research is still going on to find the best optimal solution for the purpose. The present research lies on developing efficient parallel/distributed algorithms for the purpose.

l Evolutionary algorithm based load balancing Task Allocation

To solve the above cited problem we consider using evolutionary algorithm such as GA, ant colony optimization, simulated annealing etc. in our research. A method based on genetic algorithm is already developed by us which is memory efficient and give an optimal solution of the problem. The given simulation results also show significant achievement in this regard. However, the algorithm we have proposed is sequential in nature and experimental studies and the experimental studies has been conducted on a single PC, thus the present research lies on developing parallel and distributed algorithm for the same purpose using GA for a real test bed of DCS and comparing its efficiency with other existing algorithm for the same such as greedy heuristic based MIN-MIN, MIN-MAX and A* based algorithms.