Volume 24, 2005, No. 4

A Machine Assignment Mechanism for Compile-Time List-Scheduling Heuristics

Tarek HAGRAS, Jan JANEČEK   Abstract Finding an optimal solution for a scheduling problem is NP-complete. Therefore, it is necessary to use heuristics to find a good schedule rather than evaluating all possible schedules. List scheduling is generally accepted as an attractive approach, since it combines low complexity with good results. List scheduling consists of two phases: a task prioritization phase where a certain priority is computed and assigned to each task, and a machine assignment phase where each task (in order of its priority) is assigned a machine that minimizes a suitable cost function. This paper presents a machine assignment mechanism that can be used with any list-scheduling algorithm. The mechanism is called Reverse Duplicator Mechanism and outperforms the current mechanisms.

 

Ethically-Social Approach to Computer Security Problem

Krzysztof CETNAROWICZ, Gabriel ROJEK   Abstract This article came to existence on the ground of interest in what makes possible inter-human contacts and co-operation without excessive risk for any person. An individual is protected in society from dishonesty by ethical system as well as social mechanisms, which are not infallible, although so effective in working that transferring them onto the ground of computer systems is worth testing. Equipping computer resources with mechanisms observed in individuals within human societies will enable these resources to control the safety. Our goal is to obtain mechanisms which will enable security without definition what is desirable or undesirable in a computer system. This should enable to detect viruses or attack techniques that are not already known. Mechanisms are presented which may enable to recognize and dismiss resources undesirable or harmful in the computer system on the basis of behavior observation. The proposed mechanisms were tested and tests results are presented and discussed.

 

Object Replication Algorithms for World Wide Web

Amjad MAHMOOD   Abstract Object replication is a well-known technique to improve the accessibility of the Web sites. It generally offers reduced client latencies and increases a site's availability. However, applying replication techniques is not trivial and a large number of heuristics have been proposed to decide the number of replicas of an object and their placement in a distributed web server system. This paper presents three object placement and replication algorithms. The first two heuristics are centralized in the sense that a central site determines the number of replicas and their placement. Due to the dynamic nature of the Internet traffic and the rapid change in the access pattern of the World-Wide Web, we also propose a distributed algorithm where each site relies on some locally collected information to decide what objects should be replicated at that site. The performance of the proposed algorithms is evaluated through a simulation study. Also, the performance of the proposed algorithms has been compared with that of three other well-known algorithms and the results are presented. The simulation results demonstrate the effectiveness and superiority of the proposed algorithms.

 

Distributive Join Strategy Based on Tuple Inversion

Wang-Chan WONG, Lubomir F. BIC   Abstract In this paper, we propose a new direction for distributive join operations. We assume that there will be a scalable distributed computer system in which many computers (processors) are connected through a communication network that can be in a LAN or as part of the Internet with sufficient bandwidth. A relational database is then distributed across this network of processors. However, in our approach, the distribution of the database is very fine-grained and is based on the Distributed Hash Table (DHT) concept. A tuple of a table is assigned to a specific processor by using a fair hash function applied to its key value. For each joinable attribute, an inverted file list is further generated and distributed again based on the DHT. This pre-distribution is done when the tuple enters the system and therefore does not require any distribution of data tuples on the fly when the join is executed. When a join operation request is broadcast, each processor performs a local join and the results are sent back to a query processor which, in turn, merges the join results and returns them to the user. Note that the distribution of the DHT of the inverted file lists can be either pre-processed or distributed on the fly. If the lists are pre-processed and distributed, they have to be maintained. We evaluate our approach by comparing it empirically to two other approaches: the naive join method and the fully distributed join method. The results show a significantly higher performance of our method for a wide range of possible parameters.

 

Genetic Algorithm for Solving Uncapacitated Multiple Allocation Hub Location Problem

Jozef KRATICA, Zorica STANIMIROVIĆ, Dušan TOŠIĆ, Vladimir FILIPOVIĆ   Abstract Hub location problems are widely used for network designing. Many variations of these problems can be found in the literature. In this paper we deal with the uncapacitated multiple allocation hub location problem (UMAHLP). We propose a genetic algorithm (GA) for solving UMAHLP that uses binary encoding and genetic operators adapted to the problem. Overall performance of GA implementation is improved by caching technique. We present the results of our computational experience on standard ORLIB instances with up to 200 nodes. The results show that GA approach quickly reaches all optimal solutions that are known so far and also gives results on some large-scale instances that were unsolved before.

 

Mobile Agent System Framework Suitable for Scalable Networks

Francisco Maciá-PÉREZ, Juan Manuel García-CHAMIZO, Antonio Soriano-PAYÁ, Daniel Ruiz-FERNÁNDEZ   Abstract In this article we present a formal framework based on the action and reaction model that allows us to cover the dynamics of multi-agent systems (MAS) made up of mobile software agents suitable for scalable networks. This model is based on the operation of the human nervous centres. At the present time, we are applying it in works related with the control of biological systems and also in those related to the network management. In the case of systems based on mobile agents, the main problem is the different vision the agents have of the world and the impossibility of being aware of and synchronizing all the influences brought by the different agents acting on it. We have compared our proposal with the conventional MAS by solving an extension of the predator-prey problem. The results show the advantages of mobility as the size of the problem grows in a distributed system.

 

Volume 24, 2005, No. 4