This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
Common characteristics of distributed systems include dynamicity, unreliability, and large-scale. Biological organisms cope with the demands of their environments using solutions quite unlike the traditional human-engineered approaches to prob- lem solving. Biological systems tend to be adaptive, reactive, and distributed. Techniques based on biological paradigms can provide efficient solutions to a wide variety of problems in parallel processing and distributed systems as most bio-based techniques are inherently parallel. The paper focuses on tackling complex problems using computational methods modeled after design principles encountered in na- ture. It is on how one can exploit the properties of emergence and adaptability of live systems to build distributed systems that are autonomous, resilient and adap- tive to their environments. The main motivation for this work is that nature has greatly enriched computing, successfully solving highly complex problems.
Index Terms - Distributed Computing, Parallel Processing, Biology, Nature.
Common approaches to distributed system design assume that the system is built of reliable com- ponents, or that the system scale is modest. These assumptions are not applicable for environments such as large-scale, wide-area computer networks or mobile ad-hoc networks. Approaches based on central control over the system as a whole are not feasible either for the same reasons. A central control introduces a single point-of-failure which should be avoided whenever possible. This paper explores approaches that avoid these drawbacks.
The study of biological processes and organisms is a possible means of arriving at solutions to these problems. This is because, it is well known that living organisms can effectively organize large numbers of unreliable and dynamically-changing components (cells, molecules, individuals, etc.) into structures that implement a wide range of functions. In addition, most biological structures (such as organisms) have a number of nice properties such as robustness to failures of individual components, adaptability to changing conditions, and the lack of reliance on explicit central co- ordination. Therefore, inviting ideas from nature can be seen as a promising research theme in various fields of computer science. Besides, biological inspiration is beginning to make its way into the mainstream of distributed computing after having been a niche topic for a long time [Lod04].
The motivation for this work is that large-scale and dynamic distributed systems have strong similarities to some of the biological environments as mentioned earlier. This makes it possible to extract solutions from biological systems and to apply them in distributed systems.
The biological evolution of organisms serves as a perfect study because of the rich source of design patterns that work; if a certain species has survived until today, then the solutions that it applies to solve all problems related to survival from the functioning of a single cell to the cooperation among the members of a population must be well tested and reliable.
Immunocomputing is a developing research field [imm01a] which aims at creating a new kind of computational paradigm based on some principles of information processing by proteins and im- mune networks in the living nature. This paradigm is used to solve specific complex problems and
protection from computer viruses, intruder attacks, noise and random errors. The animal nervous system has been already intensively used in computer science as a biological prototype for mathe- matical algorithms of artificial neural networks (ANN). Software, based on ANN, has been created and found its hardware implementation in neural computers [Hay98]. However, the extraordinary information processing capabilities of the natural immune system has been appreciated only re- cently. For example, the immune learning and memory achieve a more efficient protection against a specific pathogen. If immune system detects an antigen it had not encountered before, it under- goes a primary response, during which it "learns" to recognize that specific antigen more effectively, i.e. it produces a large number of lymphocytes with high affinity for that antigen, through a process called affinity maturation. These so called memory cells remain in circulation and provide faster detection and elimination of the pathogen at the next encounter.
The natural immune system has features that are desirable from a computer science standpoint. The system is intensively parallel and is truly distributed in its function. Individual components are disposable and unreliable, yet the system as a whole is robust. Previously encountered infections are detected and eliminated quickly, while novel intrusions are detected on a slower time scale, using a variety of adaptive mechanisms. The system is autonomous, controlling its own behavior both at the detector and effector levels. Individual organism's immune systems detect infections in slightly different ways, so pathogens that are able to evade the defenses of one organism cannot necessarily evade those of every other organism in population [AGI+ 01].
In section 4, we present a new model of logical clock synchronization in distributed systems.
1.2 Swarm Intelligence
Swarm Intelligence (SI) is the property of a system whereby the collective behaviour of (unsophis- ticated) agents interacting locally with their environment cause coherent functional global patterns to emerge. SI provides a basis with which it is possible to explore collective (or distributed) problem solving without centralized control or the provision of a global model.
Real ants find shortest paths using as only information the pheromone trail deposited by other ants. Ant colony optimization (ACO) algorithms which take inspiration from ants' behavior in finding shortest paths have recently been successfully applied to combinatorial optimization [CD98]. In ant colony optimization a set of artificial ants collectively solve a combinatorial problem by a cooperative effort. This effort is mediated by stigmergetic communication, that is, a form of indirect communication of information on the problem structure ants collect while building solutions.
In section 5, we explain the Ant system and its applications.
2 Achieving Efficient Load Balancing
Load balancing is one of the most general problems encountered in computer science. Examples of load balancing in practice are balancing system load among parallel processes [DBH+ 04], balancing processes among distributed systems [FK99, Ora01] , balancing storage among distributed storage devices, and many more. An equivalent of load balancing in physics can be taken as "diffusion" of gases, where in the concentration is balanced from many non uniform states to uniform states. This is accomplished in a decentralized manner, much like the way we intend to incorporate in distributed systems.
Load balancing is very common in many biological systems. In most cases, some kind of signal (urine, bird songs) is used to maintain distance between individuals or groups [PJG+97]. Yeast cells use chemical repellents to prevent growth of yeast colonies into one anothers space. Hence, in general, load balancing in biological systems is more active than the correspondingly passive, physical mechanism of diffusion.
This biological equivalent load balancing scheme is a common phenomenon called "Chemotaxis". Chemotaxis means control of movement (taxis) through diffusion of chemical signals. It is an efficient way of control of aggregate behavior of many small entities. It is used in biology both for bringing about homogeneous distributions (negative or repulsive chemotaxis), and for inducing
highly non-homogeneous aggregates (positive chemotaxis) [BF97]. It is essential for guiding cells in biological development, wound healing and many more ways in biological systems. The emphasis is made on implementing a form of repulsive chemotaxis on distributed systems to achieve time- efficient load balancing.
Plain diffusion is the physical equivalence of load balancing where there are no signals present in the system. The load and the signal are the same for plain diffusion, meaning that the load as such is the entity sensed by the system. Chemotaxis instead uses signals (in this case chemicals) to achieve efficient load balancing. The signals move faster than the load are sensed before by the system, thus achieving load balancing before the actual event of load overhead occurs. The chemotaxis design pattern was formulated as a composite pattern consisting of two components. The first component employs the plain diffusion design pattern to propagate signal system-wide. The second component utilizes the propagating signal to achieve a global data movement objective more efficiently. Improved efficiency is possible when signal carries information about the presence of data at remote locations; this information enables better local movement decisions to be made by the nodes that implement the second component. Chemotaxis assumes that the two components operate at different time scales, i.e., that signal propagates faster than the speed at which data can be moved.
In the context of distributed systems, signal is defined as a load indicator that requires only a few bytes and therefore can propagate quickly. The load to be evenly distributed among nodes is assumed to consist of large amounts of data and therefore moves slowly in comparison to the signal. We now compare the plain diffusion load balancing scheme (followed in most present day systems) and the chemotaxis load balancing scheme.
2.1 Plain Diffusion
Plain diffusion is a simple concept. Basically, nodes that have more load than capacity send a fraction of their excess load to their neighbors. In the simplest case, a node i with load Ï†i and capacity Ci will send a small fraction c of its excess load (Ï†i âˆ’Ci ) to each of its neighbors independent of node, of neighbor, and of time. Each transfer of load to a neighbor node j can be captured by the following equation:
âˆ†Ï†iâ†’j = c(Ï†i âˆ’ Ci).
With plain diffusion, load is moved in all directions without taking into account load already present in different regions of the network. Thus there is the risk of moving too much load to overloaded regions and too little to under-loaded regions. The result is an inefficient load balancing mechanism.
It is well known from biology that certain cells are able to move autonomously. Such motile cells make decisions about when to move and in what direction to move based on the presence of certain chemicals in the immediate environment. The process of cell motility in response to concentration gradients of chemicals is called chemotaxis. Some chemicals (e.g., nutrients) may cause a cell to move in the direction of increasing concentration of the sensed chemical, other chemicals (e.g., poison) act as repellents and cause a negative chemotactic response.
Chemotactic load balancing is based on the idea of repulsive chemotaxis, i.e. movement in response to a repulsive chemical. The basic principle used is that each node continuously emits a signal proportional to its excess load. The signal emitted at node i at each time is:
âˆ†Siemit = c2 (Ï†i âˆ’ Ci).
which can be encoded as a few bytes. Hence restrictions on load movement speed do not apply to signal. At each time, signal accumulated at a node is diffused to its neighbors. The following equation expresses the simple diffusion of signal from a node i to its neighbor j:
âˆ†Siâ†’j = c4 Si.
Now, the slowly diffusing load can be guided by gradients of signal as follows:
âˆ†Ï†iâ†’j = c3(Si âˆ’ Sj ).
Note the signal-aided diffusion mechanism consists of two components, a load diffusion compo- nent and a signal diffusion component. Also the two components are independent in the sense that they operate on different time scales. Algorithms based on this concept can be efficiently used for load balancing.
Replication is inherent in biological systems. Efficient and successful replication-based processes are commonplace in nature. Examples include viral replication, DNA replication or growth processes, epidemic spreading, or proliferation processes in the immune system . As stated earlier, these efficient and successful natural processes of replication present a valid stage to look at the existing problems in the field of distributed computing. For example, a distributed system can be correlated well to an epidemic scenario as follows:
A node - Potential host of a virus. Neighbour - Physical proximity, sexual contact, social
relationships, etc. Message - An infective agent (e.g., virus). Typically it is transmitted unchanged. It can also mutate in the host and be transmitted in its mutated form.
The common problems related to replication in distributed computing can be enumerated as follows:
1. The problem of propagating information just received to all other nodes. For example, database update.
2. The problem of bringing the system to a state in which all nodes are assigned the maximal value.
3. The problem of finding a node whose document matches a given query (e.g., keywords in a document).
Solutions to these problems are based on replication. For the problem 1, the nodes receive messages from their neighbors, and they forward (that is, replicate) some of the messages they received by following some application specific rules. A common solution to this is that the nodes simply copy all new pieces of information they receive to all neighbors. This strategy is commonly referred to as flooding. However, more efficient variants exist where the nodes apply a cleverer rule for forwarding, taking into account elapsed time, the number of times they received the same information, etc.
For the problem 2, messages can be considered as the candidates for the maximum value, and nodes keep, and forward the maximal value they have received, locally. For the problem 3, i.e., in the case of search, the pattern is applied to search queries which are replicated. If a match is not found, then it is forwarded. Again, there is enough scope for optimizing the strategy according to which the query can be replicated. Optimizations based on information about the topology or characteristics of the data being stored at the nodes are possible.
3.1 Example of Replication: Searching
As already mentioned, in case of the distributed search problem, the replication pattern is used to spread queries, by the nodes making clones of the queries they receive according to a predefined strategy. However, the production of cloned queries presents some overhead.
Replication can be implemented using a number of different strategies. For example, as de- scribed earlier, flooding (unbridled replication) techniques have generally been used to implement
search in unstructured networks. Although flooding ensures robustness and gives very fast results, it results in a huge number of query messages which ultimately overwhelms the entire system. This is a well known problem with the first generation Gnutella networks. Alternatively, slower- but-efficient method is to perform the search operation using k-random walkers (no replication) [LCC+02]. A proliferation algorithm (controlled replication), is discussed in [BCD+ 06]. When constrained to produce a number of messages comparable to the k-random walker algorithm, it is significantly faster in finding the desired items. Proliferation is a specific replication strategy inspired by the immune system. The algorithm has been inspired by the simple mechanism of the humoral immune system, where B cells, upon stimulation by a foreign agent (antigen) undergo proliferation generating antibodies [JTWS01]. Correlating this to a distributed systems context, we find that this mechanism represents an instance of the replication pattern. Proliferation helps in increasing the number of antibodies that can then efficiently track down the antigens (foreign bodies). A query message is conceived as an antibody which is generated by the node initiating a search, whereas antigens are the searched items hosted by other nodes of the overlay network. As in the natural immune system, the messages undergo proliferation based on the affinity mea- sure between the message and the contents of the node visited, which results in an efficient search mechanism.
4 Immunocomputing: Logical Clock Synchronization
Immunocomputing(IC) model of synchronization of events in distributed asynchronous systems has been developed [imm01b]. The model uses principles of homology and recognition between formal proteins(FPs). As a result, the model doesn't need to introduce any notion of "time", which is usual for algorithms that provide the synchronization of events or the necessary order of delivering messages, and that are called synchronization protocols.
The model includes the representation of network events by FPs called "messengers". One of the central problems of multicast is distributed synchronizing or deciding how to provide message delivery order. Solutions to this problem have already been addressed [Lam78]. However, it is noteworthy that similar problems are solved on the level of biomolecules where billions of heteroge- neous cells have to synchronize their functionalities by exchanging proteins as "multicast messages". Though the concept of a scalar or vector clocks cannot be defined at this level, rather general and effective mechanisms of synchronizing can be found [Per89]. Models of multicast protocols based on formal proteins have already been developed. Computing proceeds by a sequence of broadcasts, in which a process sends a message to some arbitrary subset of processes, including itself. Although the model doesn't use any kind of time, it is able to synchronize message delivering. Two well- known time based protocols as special cases of the model were considered: Scalar Time Stamps and Vector Time Stamps [imm01b].
5 Routing with Swarm Intelligence
5.1 The Ant System
The Ant System (AS) is an all-purpose trial-and-error algorithm, which can resolve different augmentation problems [DMC96]. It has the following features:
â€¢ It is adaptable and can be used to solve comparable variants of a single problem
â€¢ It is potent and generic
â€¢ It is a collection-based trial-and-error technique.
This algorithm is an instance of a distributed search mechanism. Search exercises are spread over ant-like agents, i.e. items with naive capacities. These agents emulate the behavior of real ants in a figurative way.
Figure 1: Shortest Path Emergence
It is evident that the technique used for the exchange of information between individuals about paths, and the one adopted to implement routing decisions, is contained of the apprehension of pheromone trails as shown in Fig.1. Pheromone is laid in different quantities on the ground, by a moving ant, thus denoting the path by a trail of the substance. An individual ant, when intersected by such a trail, perceives the substance and chooses to pursue it with increased expectation. Consequently, the trail is further bolstered with additional pheromone. The combined action of multiple ants pursuing to detect a path that emanates resembles an autocatalytic process. More the ants in the trail, more attractive are the trail for newer ants. The process forms a positive feedback loop, where the likelihood with which an ant resorts to a path will multiply with the number of ants that resorted to the same path earlier.
The Ant System is a search technique that resembles a distributed autocatalytic mechanism.
The concept that drives the ant system search technique is that of a collection of agents each advised by an autocatalytic process controlled by a craving force. If an agent were to search alone, the autocatalytic process and the craving force would impel to forge the agent encounter a sub- optimal result with increased speed. The craving force can lend valuable suggestions to the autocatalytic process during agent interaction and allow quick convergence to excellent, often optimal, solutions without involving in local optima. Such carriage emerges because information learnt by the agents amidst the search process is applied to enhance (using pheromones) the problem representation. By and large, the area of the space relevant to the search process is decreased.
The advantages of using an Ant System are as follows:
1. Positive feedback is utilized as an exploration and optimization tool. The concept is that, if at a given point an agent (ant) has to decide amongst various options, and the one actually selected appears to be better, then moving further that choice will appear more enticing than it was earlier.
2. Synergy can originate and be applied in distributed systems. In AS, the potency of the exploration accomplished by a given number of mutually helpful ants is more than that of the search discharged by the same number of ants, each one behaving on its own in isolation.
6.1 Load Balancing in Networks
Load balancing is a key characteristic in networks, transport layer in particular. The absolute target of TCP layer is to disclose congestion and obtain an increased amount of equality among the flows
Figure 2: Example network topology for achieving flow fairness through load balancing.
negotiating a path, i.e. achieve load balancing among flows. Consider the scenario shown in Fig.2. The nodes A and B want to communicate with nodes E and F respectively. The congestion occurred on account of the snag at nodes C and D influences the equality of flows. Let the flow from A to E be called as flow 1 and the flow from B to F as flow 2.
This instant's biological schema can be described as follows. Flow 1 communicates a signal to all flows in the snag. We are in the signal aspect of the load balancing scheme. Nodes C and D are utilized for signaling. These nodes implant a tiny score of data in the flow that channels information about other flows. Now, both sender and receiver are aware of the other flows in that particular snag and accordingly adjust their flow (by channelizing through another path or by decreasing flow rate), hence obtaining load balancing within the nodes. This technique calls for cross layer communication between TCP and network layers and reflects the concept of chemotactic load balancing.
Extensive simulations in NS2 have revealed an enhanced TCP performance for the approach benefitted from the piggybacking received from the routers on its path.
This concept has triggered the invent of multiple protocols. Our protocol UCP [KVK08] and VCP [XSSK05] imbibe only 2 bits to cipher the signal, while XCP protocol [KHRlIT02] calls for 128 bits and a discrete header field.
6.2 Natural Selection
We propose a new model to work for a service oriented distributed system architecture. Assuming there are n+k servers that offer a distributed service, and k different ways of achieving that service. Each of the k methods is based on a particular pre-defined heuristic approach. We basically intend to tackle the problem of selection of appropriate heuristic for a given configuration of the system. The configuration of a system in this service architecture is what we define as queries from the clients. We assume that the system is highly scalable and the requests modify the system using a positive feed back, i.e. the system dynamically adapts to the clients requests to achieve the best service overall.
Drawing ideas from Darwin's natural evolution theory, we propose the following in the lines of natural selection, aptly described as Survival of the Fittest. We assume an initial configuration where all the k heuristics are evenly distributed among the n nodes in the system. Two adjacent nodes can communicate and exchange information such as bandwidth utilization, throughput etc. After a specific time, if a node A finds that its adjacent node B's performance is worse compared to itself under the current configuration, it "commands" the node B to follow its own heuristic algorithm. If the node B finds that its performance degrades after switching to the new heuristic, it reverts back to the original one, thus ensuring that service is offered in a better way.
The technique of analyzing the interaction of organisms and hence extracting strong reciprocity with distributed computing due to the natively parallel systems of the congenital world can be considered as an inception of motivation and as a handy resource pool to fetch results in distributed computing. Some of those models are Chemotaxis, Stigmergy, Evolution strategies, and immune-computing. Native parallelism, equivocal nature, adjustment, and the use of constructive criticism are some of the key features of such methods.
We bring to foray an insight into the relatively novice method of looking back at the nature to find answers to complex problems that are difficult to resolve using conventional techniques.