NDLI: Proceedings of the 2009 workshop on Bio-inspired algorithms for distributed systems (BADS '09)

Please wait, while we are loading the content...

Characterizing fault tolerance in genetic programming

A distributed ant-based algorithm for numerical optimization

Asynchronous simulation of a self-synchronized duty-cycling mechanism for mobile sensor networks

High performance genetic programming on GPU

Proactive information caching for efficient resource discovery in a self-structured grid

Evolutionary p2p network adaptively changing its topologies for reliable searching

Power-efficient epidemic information dissemination in sensor networks

Fastest parallel molecular algorithms for the elliptic curve discrete logarithm problem over GF(2n)

Crystal-growth-inspired algorithms for computational grids

An evaporative approach to handle dynamics in diffusive aggregation schemes

Swarm intelligence based energy saving and load balancing in wireless ad hoc networks

An innovative perspective on mapping in grids

Proceedings of the 2009 workshop on Bio-inspired algorithms for distributed systems (BADS '09)

Content Provider	ACM Digital Library
Editor	Zambonelli, Franco Mastroianni, Carlo Folino, Gianluigi Blum, Christian Krasnogor, Natalio
Copyright Year	2009
Abstract	It is our great pleasure to welcome you to BADS 2009, the Workshop on Bio-Inspired Algorithms for Distributed Systems. The aim of the workshop is to provide a forum to explore the applications of bio-inspired algorithms and protocols in different kinds of distributed computing systems, and discuss the main trends and challenges for the next few years. Computer systems are characterized by an ever growing complexity and a pronounced distributed nature. While the use of centralized or hierarchical architectures and algorithms has been dominant so far, they are now becoming impractical because they have poor scalability and fault-tolerance characteristics. Decentralized architectures and algorithms, for example P2P and Grid systems, are increasingly popular, but to be efficiently managed they need new types of algorithms. Bio-inspired algorithms are proving effective in this context, as they can be used to solve hard parallel and distributed computational problems by imitating the autonomic nature of distributed systems, in this way achieving fault-tolerant and self-adaptive behavior. These algorithms can be inspired by a number of biological systems, including ant colonies, bird flocking, honey bees, bacteria, and many more. In other cases the adopted techniques are "evolutionary", as they exploit genetic rules for the selection and the recombination of candidate solutions. The success of this workshop confirms that distributed computing systems are a very natural application field for bio-inspired algorithms and protocols. The BADS workshop includes one invited paper and 11 research papers selected through an accurate review process, which allowed us to select among 20 manuscripts submitted from Africa, Asia, Brazil, United States and many European Countries. The workshop is organized in four sessions, with the papers grouped according to the application area on which the bio-inspired algorithms are exploited. The four sessions are dedicated, respectively, to Grid computing, distributed systems and P2P, sensor and wireless environments, and parallel architectures. Grid Computing. Four papers are specifically dedicated to Grid computing. The paper by González et al. analyzes the behavior of Parallel Genetic Programming (PGP) applications executing in distributed platforms with high failure rates, with the goal of characterizing the inherent fault tolerance capabilities of the PGP paradigm. Two well-known GP problems, "even parity 5" and "11-multiplexer", are examined via simulation by using trace data collected from real-world Desktop Grid platforms. Experiments show that the PGP paradigm exhibits satisfying fault tolerance properties even in very dynamic environments. The paper by Brocco et al. presents and evaluates an ant-inspired algorithm that aims to reduce the overall network traffic in a Grid. Mobile agents move across the Grid and add or remove logical links exploiting local information, in order to optimize the network topology. The paper also introduces an effective resource discovery algorithm that executes over the obtained topology and uses cache information exchanged among the nodes via a gossiping mechanism. The paper by Brun and Medvidovic shows how the natural process of crystal growth can inspire computational mechanisms that are easily susceptible to large-scale parallelization, fault tolerance, and uniform representation of data and computation, which favors data management and mobility. After summarizing the crystal-inspired solutions to some complex problems, for example the SubsetSum NP-complete problem, the authors describe how these techniques can also be devised for distributed systems and specifically computational Grids. The proposed approach ensures scalability, privacy of data, and tolerance of a wide range of faults and malicious attacks. De Falco et al. propose the use of a multi-objective Differential Evolution (DE) algorithm that finds near-optimal solutions to map the communicating tasks of a computational intensive application on multisite Grid nodes. The authors extend the classical DE paradigm to cope with this problem, also by introducing a novel operator that allows a subset of similar tasks to be allocated on the nodes of a cluster. The algorithm is defined, implemented and evaluated in many simulated scenarios by varying the load and reliability of the nodes, so reproducing a real world environment. Distributed Systems and P2P. Three papers focus on general purpose distributed systems and P2P networks. The paper by Korosec and Silic proposes a distributed ant-colony optimization technique to solve black-box global optimization problems. Prior to the application of the distributed ant algorithm, the problem space is discretized and a search graph of the problem is built. The algorithm exhibits good scalability properties in the scenarios where the black-box execution time dominates the time taken by the ants to search the global optimum. Scalability can be further improved by using a larger number of ants. Ohnishi et al. use an evolutionary-based approach to adaptively change the topology of a dynamic P2P network and improve the reliability of search procedures. The topology of the network is conveniently represented as an individual of the evolutionary algorithm, and crossover and mutation operator are used to change the network topology. The algorithm is evaluated on two different scenarios, with and without replicating the resources: the evolutionary approach proves to be particularly effective without replication. The paper by Bicocchi et al. aims to handle dynamics in diffusive aggregation schemas using a technique based on a classical gossiping technique and on a novel method named "evaporation". The latter is based on the search behavior of ants following pheromone trails, and tends to promote up-to-date values while making old values evaporate. The method avoids the need for periodic restarts present in standard gossiping techniques. Experimental results assess the efficiency of the method especially for large-scale networks. Sensor and Wireless Networks. This session collects three papers that focus on sensor and wireless networks and, more specifically, deal with the important issue of energy saving. The invited paper by Hernández and Blum discusses and analyzes a self-organizing mechanism that exploits the energy harvesting capabilities of a network of mobile sensors. The mechanism is inspired by the self-synchronized sleeping patterns observed in ant colonies. Correspondingly, each sensor switches between the active and the inactive state on the basis of its state parameters, the amount of energy harvested with its solar cells, and the information received by neighbor sensors. The approach is evaluated in conditions that are easily encountered in real world applications, such as de-synchronized sensor clocks, random direction mobility of sensors, and varying weather conditions influencing the amount of solar energy collected by the sensors. Garbinato et al. present a novel approach to disseminating information in a sensor network. This approach combines the decentralized and stateless properties of gossiping protocols, which assure low resource consumption, with the high reliability that is typical of structured protocols. Reliability is obtained by modulating the transmission range of sensors in accordance with a power law statistical distribution. If compared with classical gossiping protocols, the small-world and scale-free nature of the presented approach allows sensors to obtain equivalent delivery ratios with lower energy consumption. De Rango and Tropea present a routing algorithm for mobile ad hoc networks. This algorithm utilizes swarm intelligence techniques, in particular an ant colony optimization algorithm, to discover minimum drain rate paths, so combining traffic load balancing and energy saving. The main novelty of the approach consists in using quantitative metrics for energy saving and traffic load distribution in the pheromone update phase. The algorithm efficiency is proved through comparison, via NS2 simulation, with two currently adopted routing algorithms. Parallel Architectures. The session on algorithms for parallel architectures comprises two papers that exploit innovative techniques: algorithms for GPU-based architectures and DNA computing algorithms. Robilliard et al. analyze the possibilities offered by modern Graphics Processing Units (GPU) for implementing genetic programming. They evaluate and compare the performance of GP obtained by using two parallelization schemas, namely BlockGP and ThreadGP. The paper draws some important lessons for optimizing evolutionary algorithms on GPU-based architectures. In their paper, Iaccarino and Mazza propose a performance improvement of a recent DNA computing algorithm. This method is applied to an intractable problem in the field of cryptography, the "elliptic curve discrete logarithm" problem. In particular, the authors build the model of a parallel multiplier and adder, which outperforms the existing methods in terms of the worst case time complexity. The categorization of the workshop papers in accordance with the corresponding application domains clearly confirms the wide range of practical applications that may benefit from the adoption of bio-inspired algorithms, and the inherent capacity of these algorithms to be exploited in emerging domains such as sensor networks, Grids, P2P networks, and multi-core processors.
ISBN	9781605585840
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-06-19
Access Restriction	Subscribed
Content Type	Text
Resource Type	Conference Proceedings

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in