Desktop Grid has recently received the strong attraction for executing high throughput applications as CPU, storage and network capacities improve and become cheaper. Desktop Grid is different from Grid in many respects, but there is no general survey or taxonomy for desktop Grid. Therefore, we propose a new comprehensive taxonomy and survey of desktop Grid in order to characterize and categorize desktop Grid.

In P2P systems, the speed of searching for desired lists of sharable files is one of the most important measurement issues in evaluation of overall system performance. Although the searching schemes of existing non-structured P2P systems have been improved to enhance speed considerably, they still never reach to the level of those of the centralized and structured systems. In this paper, we propose a multi-node global directory in P2P systems, where all the lists of sharable resources of the joining peers are aggregated and divided into the chosen nodes while keeping collating sequence as a whole to make one big linked list. Thus in indexed sequential searching, the system provides us with convenience of using the command like 'dir' of MS-DOS, and in general keyword searching, which is naturally impossible for the structured P2P systems, the searching speed is even faster than those of centralized P2P systems since a small list segment is scanned at each node synchronously in parallel

No abstract available.

Broadcasting in wireless mobile computing environments is an effective technique to disseminate information to a massive number of clients equipped with powerful, battery operated devices. To conserve the usage of energy, which is a scarce resource, the information to be broadcast must be organized so that the client can selectively tune in at the desired portion of the broadcast. In this paper, the efficient, energy conserving transaction processing in mobile broadcast environments is examined with widely accepted approaches to indexed data organizations suited for a single item retrieval. The basic idea is to share the index information on multiple data items based on the predeclaration technique. The analytical and simulation studies have been performed to evaluate the effectiveness of our methodology, showing that predeclaration-based transaction processing with selective tuning ability can provide a significant performance improvement of battery life, while retaining a low access time. Tolerance to access failures during transaction processing is also described.

A volunteer node can join and leave a volunteer computing system freely. However, existing volunteer computing systems suffer from interruptions of job execution, delays of execution time, and increases of total execution time, since they do not consider dynamic scheduling properties (i.e. volatilities), such as leave, join, and suspension. Therefore, dynamic execution properties of volunteer node should be considered in scheduling schemes, in order to design a stable and reliable volunteer computing system. This paper proposes a new scheduling scheme based on the dedication rate (DR), which reflects the dynamic properties of a volunteer. The scheduling scheme improves the completeness and reliability of execution, while also decreasing delay and total execution time. In addition, an implementation of the proposed scheduling scheme on top of Korea@Home is described, as well as performance evaluation

Fault tolerance is essential to the development of reliable mobile agent systems in order to guarantee continuous execution of mobile agents. For this purpose, previous work has proposed fault tolerant protocols for mobile agent execution based on stage construction. However, when previous protocols are applied to a multiregion mobile agent computing environment, the overhead of work such as monitoring, election, voting and agreement is increased. We propose a region-based stage construction (RBSC) protocol for fault tolerant execution of mobile agents in a multiregion mobile agent computing environment. The RBSC protocol uses new concepts of quasiparticipant and substage in order to put together some places located in different regions within a stage in the same region. Therefore, the RBSC protocol decreases the overhead of stage works. Consequently, the RBSC protocol decreases the total execution time of mobile agents.

Location management and message delivery protocol is fundamental to the further development of mobile agent systems in a multiregion mobile agent computing environment in order to control mobile agents and guarantee message delivery between them. However, previous works have some problems when they are applied to a multiregion mobile agent computing environment. First, the cost of location management and message delivery is increased relatively. Second, a following problem arises. Finally, cloned mobile agents and parent & child mobile agents don't get dealt with respect to location management and message delivery. We present a HB (home-blackboard) protocol which is a new location management and message delivery protocol for mobile agents in a multiregion mobile agent computing environment. We have implemented the HB protocol. The HB protocol decreases the cost of location management and message delivery and solves the following problem with low communication cost. In addition, the HB protocol deals with the location management and message delivery of cloned and parent & child mobile agents, so that it guarantees message delivery of these mobile agents.

Fault tolerance is essential to the further development of desktop grid computing system in order to guarantee continuous and reliable execution of tasks in spite of failures. In a desktop grid computing environment, volunteers are often susceptible to volunteer autonomy failures such as volatility failure and interference failure in the middle of execution of tasks because a desktop grid computing maximally respects autonomy of volunteers. The failures result in an independent livelock problem (i.e. the delay and blocking of the entire execution of a job). Therefore, the failures should be considered in a scheduling mechanism. In This work, in order to tolerate volunteer autonomy failures, we propose a new fault tolerant scheduling mechanism. First, we specify a volunteer autonomy failures and an independent livelock problem. Then, we propose a volunteer availability which reflects the degree of volunteer autonomy failures. Finally, we propose a fault tolerant scheduling mechanism based on volunteer availability (which is called VAFTSM).

Abstract The Hierarchical Mobile IPv6 (HMIPv6), which is based on the Mobile IPv6 (MIPv6), has been proposed by IETF to reduce registration control signaling. It separates micro‐mobility from macro‐mobility with the help of an intermediate mobility agent, called the mobility anchor point (MAP), and exploits a Mobile Node's (MN's) spatial locality. However, all packets from a Correspondent Node (CN) to an MN are delivered through the MAP. That causes delay in packets delivery and the congestion of packets in the MAP so that it results in deterioration of network capability. To alleviate these problems, we propose a Hierarchical Mobile IPv6 protocol using not only spatial locality but also temporal locality. We introduce a profile for management of these locality information. According to the information in the profile, some packets are directly delivered to an MN, if MN seems to reside for a long time in the current subnet. Also, we introduce a handover scheme with the help of an L2 trigger, so that the proposed scheme takes nearly the same handover delay time as HMIPv6. The other contribution of this paper is to suggest a mathematical modeling and analysis of network traffic costs, MAP processing costs and handover latency for both HMIPv6 and the proposed scheme. Copyright © 2004 John Wiley & Sons, Ltd.

What is important in location-aware services is how to track moving objects efficiently. To this end, an efficient protocol which updates location information in a location server is highly needed. In fact, the performance of a location update strategy highly depends on the assumed mobility pattern. In most existing works, however, the mobility issue has been disregarded and too simplified as linear function of time. We propose a new mobility model, namely state-based mobility model (SMM) to provide more generalized framework for both describing the mobility and updating location information of moving objects. We also introduce the state-based location update protocol (SLUP) based on this mobility model.

Many dynamic location update schemes such as time-based, movement-based, and distance-based; have been studied in the location management of mobile communication. Also there are many studies that improve these schemes adaptively using mobile nodes' call and mobility patterns. These schemes usually use the prediction-based algorithms for mobile nodes' mobility patterns. However those need complicated computation such as heuristic algorithm. Those schemes' management cost are various for mobile nodes' diverse mobility patterns. In this paper we propose a novel approach in which the location management costs are rarely affected by mobile nodes' mobility patterns. The basic idea is to use the velocity of a mobile node, which is represented by the combination of two thresholds: time threshold T and distance threshold D. The update process is triggered by the change of mobile nodes' velocity, that is two thresholds. These values are adjusted by simple algorithm whenever a location update occurs. Also, we use stepwise paging scheme using the mobile nodes' velocity in order to reduce the paging cost. We compare our scheme with the distance-based scheme through numerical analysis. Finally, we show that our proposed scheme is better than the distance-based scheme with an optimal distance threshold value for most mobility patterns.

Wireless data broadcast allows a large number of users to retrieve data simultaneously in mobile databases, resulting in an efficient way of using the scarce wireless bandwidth. However, the efficiency of data access methods is limited by an inherent property that data can only be accessed strictly sequentially by users. To properly cope with the inherent property, this paper presents three predeclaration-based transaction processing methods that yield a significant performance improvement in wireless data broadcast.

Wireless data broadcast allows a large number of users to retrieve data simultaneously in mobile databases, resulting in an efficient way of using the scarce wireless bandwidth. The efficiency of data access methods, however, is limited by an inherent property that data can only be accessed strictly sequentially by users. The paper addresses the issue of ensuring consistency and currency of data items requested in a certain order by wireless read-only transactions. To properly cope with the inherent property of data broadcast, we explore a predeclaration-based query optimization and devise three predeclaration-based transaction processing methods.

In recent years, there has been a lot of research effort in the periodic push model where the server repetitively disseminates information without explicit request. We call the broadcast model supporting backchannel as hybrid broadcast. In this paper, we devise a new transaction processing algorithm called O-PreH, which is based on the notion of pre-reordering. If one or more conflicts for mobile transactions are found from server's periodic invalidation report, conflict orders are determined not to violate the consistency( pre-reordering) and then the remaining operations have to be executed pessimistically.

Considering the properties of mobile computing environments, push-based data dissemination systems have lately attracted considerable interest. However, the skewed access pattern of mobile clients makes the average wait time worse and they may want to request the data object to the server explicitly through the backchannel. We call the broadcast model supporting backchannels adaptive broadcast. We devise new algorithms for adaptive broadcast based on our previous works; that is, we divide data objects which the server maintains into push-data and pull-data. Clients have to explicitly request data objects in pull-data. Maintaining transactional consistency in both pure-push and adaptive broadcast environment is our main concern. We also evaluate the performance behavior through a simulation study.

As the number of mobile nodes registering with a network rapidly increases in Mobile IP, multiple mobility (home or foreign) agents can be allocated to each network in order to improve performance and availability. Previous fault-tolerant protocols to mask failures of the mobility agents have used passive replication techniques. However, they result in high failure-free latency during registration process if the number of mobility agents in the same network increases, and force each mobility agent to manage bindings of all the mobile nodes registering with its network. In this paper, we present a new fault-tolerant protocol using checkpointing and receiver-based pessimistic message logging techniques. The protocol achieves low failure-free latency even if the number of mobility agents in a network increases and improves scalability to a large number of mobile nodes registering with each network compared with the previous protocols. Additionally, the protocol allows each failed mobility agent to recover bindings of the mobile nodes registering with the mobility agent when it is repaired even if all the other mobility agents in the same network concurrently fail.

Causal message logging approach with independent checkpointing having two advantages, low failure-free overhead and limited rollback, is very attractive for providing fault-tolerance for parallel/distributed applications on message passing systems. However, to satisfy the two desirable properties, this approach should force each process to maintain a large amount of message logging information in its volatile storage and piggyback a part of the information on each sending message. In this paper, we present two efficient garbage collection schemes for avoiding these drawbacks. The first scheme enables each process to remove log information related to all messages no longer needed for process recovery by forcing the process to piggyback only an additional -size vector, where is the number of processes, on each sending message without requiring any additional message. The second scheme allows the process to remove a part of the rest of log information in storage buffers if more empty buffer space is required after the first scheme has been executed. The two schemes considerably reduce the number of additional messages and forced checkpoints needed by the garbage collection and output commit overhead compared with previous schemes.

Recently, hierarchical architecture for location databases has been proposed in order to accommodate the growing number of PCSs user. With the 3-level hierarchical database architecture, which is compatible with the current cellular mobile systems, newly developed additional databases, including the regional location database (RLR), are positioned between the HLR and the VLRs. We propose an efficient cache scheme, the Double T-thresholds Location Cache Scheme, could reduce the network and database costs to lookup a portable using the 3-level architecture. The idea behind our proposed scheme is to use two pieces of cache information, VLR and RLR, which are serving the called portables. These two pieces are required in order to exploit not only the locality of a registration area (RA) but also the locality of a regional registration area (RRA), a wide area covered by the RLR. We also use two threshold values in order to determine whether the two pieces are obsolete. The cost analysis presented in this paper shows that the double T-thresholds location cache scheme significantly reduces network and database costs for most patterns of portables.

This paper provides unified protocols of concurrency control and recovery in distributed object-based databases by using two unified conflict notions: preservation and weak preservation. The two conflict relations provide the solutions to (i) the low-level heterogeneity of different recovery mechanisms and/or object models, and (ii) the correct schedules from both concurrency control and recovery points of view. In particular, preservation can be used for accepting serializable and strict (SR-ST) and/or serializable and avoiding cascading aborts (SR-ACA) schedules, whereas weak preservation can be used for accepting serializable and recoverable (SR-RC) schedules. It is also shown that the unified protocols are general enough for object-based databases in addition to the classical read/write databases.

This paper proposes a restoration scheme based on mobility learning and prediction in the presence of the failure of mobility databases in personal communication systems (PCSs). In PCSs, mobility databases must maintain the current location information of users to provide a fast connection for them. However, the malfunction of mobility databases may cause some location information to be lost. As a result, without an explicit restoration procedure, incoming calls to users may be rejected. Therefore, an explicit restoration scheme against the malfunction of mobility databases is needed to guarantee continuous service availability to users. Introducing mobility learning and prediction into the restoration process allows systems to locate users after a failure of mobility databases. In failure-free operations, the movement patterns of users are learned by a neuro-fuzzy inference system (NFIS). After a failure, an inference process of the NFIS is initiated and the users' future location is predicted. This is used to locate lost users after a failure. This proposal differs from previous approaches using a checkpoint because it does not need a backup process nor additional storage space to store checkpoint information. In addition, simulations show that our proposal can reduce the cost needed to restore the location records of lost users after a failure when compared to the checkpointing scheme.

For the purpose of extracting the data effectively, it is necessary to construct a knowledge base system intelligently, making the data connect to each other by relationship. In this paper we propose the selective learning system which has selective perceptible ability and the mechanism for data extraction from their association.

The performance of optimistic concurrency control schemes is sensitive to the transaction abort rate. The abort probability can be reduced by reordering in order to reduce read-write conflicts. However, a potential drawback of reordering schemes is the space overhead in maintaining timestamps, multiple versions or a serialization graph. Furthermore, some transactions in optimistic concurrency control schemes may perform unnecessary operations even after the transactions have accessed write-write conflicting data items, because aborts happen only in the validation phase. In this paper, we propose a new broadcast scheme called BOCC-RS (Broadcast Optimistic Concurrency Control with Re-ordering Scheme) that can reduce the abort probability with low space overhead. In our scheme, the server maintains only one timestamp per data item for reordering. Moreover, our scheme reduces unnecessary operations. This paper presents a simulation study which shows that our scheme outperforms BOCC.

In the client-server database systems, clients can maintain their own cache to reduce the overhead of accessing data objects at server databases.In this case: there should be a protocol which ensures the consistency of cahed data, and it can be divded into two classes: pessimistic protocol and optimistic protocol.In this paper, we propose a new cache management scheme which dyuumically applies an appropriate protocol for each data object based on the degree of contention on each of them.When the contention of data objects is uniformly high or uniformly low, the proposed scheme shows the same performance with conventional algorithms, and when the contention is not uniform, the proposed scheme shows better performance than conventiona alorithms.

In this paper, we provide a uniform approach to global con-' currency control and recovery in multidatabase environment.Instead of considering global serializability and global atomicity as two orthogonal concepts, we simply adopt global serializability as the only correctness criterion and require global serializability to be maintained even in a failure-prone multidatabase environment.We first propose rigid conflict serializability (R-CSR) as a sufficient condition for the global transaction manager to ensure global serializability in an autonomous: heterogeneous, and failure-free multidatabase environment.Following this, we show that the combination of cascadeless R-CSR of global transactions and a wntezt-setlJitiue and lute redo recovery leads to the achievement of global serializability in a failure-prone multidatabase environment.

This paper presents a hybrid checkpointing protocol-an asynchronous checkpointing protocol using a message sending/receiving state change for reducing the overhead of failure-free operation combined with a selective sender-based message logging protocol for reducing the cascade rollback of asynchronous checkpointing protocol. The selective sender-based message logging protocol records only potential orphan messages when taking a checkpoint. And this paper presents a message dependency tree recording the inter-process message sending/receiving information on a volatile storage for reducing the search time of inter-process information during the failure recovery.

Our objective is to provide a theoretical foundation for multidatabase transaction management that deals with global concurrency control and global deadlocks in a uniform manner. We first propose rigid conflict serializability as a sufficient condition for the global transaction management to ensure global serializability in multidatabase environment. Subsequently, it is shown that the enforcement of rigid conflict serializability through a rigid method at the time each global subtransaction begins its execution avoids global deadlocks. The deadlock-free policy in the paper seems to be attractive due to the simple and uniform approach it takes. The basic advantage of the approach is that the global transaction manager can allow any interleavings among normal database operations belonging to global transactions without any mechanism at global level.

In a sender-initiated load balancing algorithm, the overloaded processor continues to send unnecessary request messages for load transfer until underloaded processor is found while the system load is heavy. Therefore, it yields inefficient inter-processor communications, low cpu utilization, and low system throughput. To solve these problems, we propose an improved genetic algorithm method for sender-initiated load balancing in distributed systems, and define a suitable fitness function. In this scheme, the processors that the request messages are transfered to are determined by genetic algorithm. The method also decreases unnecessary request messages. Compared with the conventional sender-initiated algorithms, we show that the proposed algorithm performs better.

This paper proposes preservation as a new conflict relation in an object-based database.By explicitly including reverse-operations which bridge the gap between concurrency control and recovery, preservation can be used independently of execution contexts to which different recovery algorithms and/or object models give rise, and further it forms a basis for formulating semantics-based recovery.This paper also makes a t wo-dimensional( i.e., execution cent exts and operations' specifications) comparison bet ween preservation and other conflict relations.Irr each execution cent ext, our formal comparison reveala that preservationbased concurrency control achieves more concurrency than commutativity-based one.