24549782
Adaptive Fault Tolerant Hospital Resource Scheduling
In a distributed hospital system, different hospitals should collaborate among themselves for sharing their resources to provide better and faster service to the patients. We address the distributed hospital resource scheduling problem and apply the Generalized Partial Global Planning (GPGP) approach used for multiagent systems for the same. An adaptive coordination mechanism based on the contract net protocol is proposed to support inter-hospital collaboration. We have performed simulation studies and the experimental results show that our coordination mechanism performs better than commonly used schemes. Fault handling mechanisms are presented so that the system continues to provide service even in the presence of faults. The proposed approach is applicable in contexts other than the distributed hospital system as well.
65058359
Group Based Routing in Disconnected Ad Hoc Networks
In this paper, we propose a routing protocol for disconnected ad hoc networks where most nodes tend to move about in groups. To the best of our knowledge, no routing protocol for disconnected ad hoc networks has been designed earlier keeping in mind possible group patterns formed by the movement of nodes. Our protocol works by identifying groups using an efficient distributed group membership protocol, and then routing at the group level, rather than at the node level. The protocol is designed so that existing concepts of routing in disconnected ad hoc networks can be extended to work at the group level. Initial simulations across a broad spectrum of parameters suggest that our protocol performs better in terms of delivery ratio and latency over traditional approaches like AODV [1], and also over disconnected routing approaches like the 2-Hop routing protocol [2].
3086074
An Exercise in Fault-Containment: Self-Stabilizing Leader Election
Self-stabilizing algorithms are designed to guarantee convergence to some desired stable state from arbitrary initial states arising out of an arbitrarily large number of faults. However, in a well-designed system, the simultaneous occurrence of a large number of faults is rare. It is therefore desirable to design algorithms that are not only self-stabilizing, but also have the ability to recover very fast from a bounded number of faults. As an illustration, we present a simple self-stabilizing leader election protocol that recovers in O(1) time from a state with a single transient fault on oriented rings. Only the faulty node and its two neighbors change their state during convergence to a stable state. Thus, the effect of a single fault is tightly contained around the fault. The technique for transforming a self-stabilizing algorithm into its fault-contained version is simple and general, and can be applied to other problems as well that satisfy certain properties.
19017935
Fault-containing network protocols
Self-stabilization is a simple and elegant approach towards designing fault-tolerant network protocols. While self-stabilization provides automatic recovery from arbitrary transient faults, self-stabilizing systems do not incorporate any optimization for more efficient recovery from limited transient faults, even though such limited faults are more likely to occur in practice than arbitrary faults. Fault-containing self-stabilizing protocols are proposed to efficiently contain the effects of more frequent, limited transient faults while retaining the desirable property of self-stabilization. In this paper, we propose a methodology for designing fault-containing selfstabilizing network protocols. The methodology views the properties of self-stabilization and fault-containment in separation. Since self-stabilizing protocols already exist for many important network problems, the design starts with an existing self-stabilizing protocol, and adds to it the fault-containment property. The feasibilitv of this technique is illustrated bv the design of a fault-containing self-stabilizing protocol for the breadthfirst-search (BFS) spanning tree problem. The applicability of the technique used in deriving the BFS protocol to other problems is also discussed.
9811083
Performance enhancement of a contract net protocol based system through instance-based learning
The contract net protocol (CNP) is a widely used coordination mechanism in multiagent systems. It has a lot of communication overhead due to the broadcast of the task announcements. The performance of the CNP degrades drastically when the number of communicating agents and the number of tasks announced increases. Hence, it has problems of scalability. In order to overcome this limitation, an instance-based learning (IBL) mechanism is designed that uses previously stored instances in order to select a target agent. This avoids the expensive bidding process. The scheme is implemented in a simulated distributed hospital system where the CNP is used for resource sharing across hospitals. Experimental results demonstrate that with the incorporation of the IBL, the system performance improves significantly. The system is better scalable with respect to the number of tasks.
32945610
A Framework for Automatic Identification of the Best Checkpoint and Recovery Protocol
Fault tolerance is important for a distributed system to increase its reliability and throughput. Checkpoint and recovery protocols have been proposed as fault tolerance for non-critical applications. The performance of checkpoint and recovery protocols plays an important role in the overall performance of a distributed system. The performance of these protocols depends on system characteristics as well as an application characteristics. In this paper, we propose a novel technique to automatically identify the checkpoint and recovery protocol which is likely to perform the best for a given system and an application the system is currently running. We present experimental results to show that the scheme can efficiently determine a suitable checkpoint and recovery protocol for many applications.
326701
A modeling and execution environment for distributed scientific workflows
We illustrate how a domain scientist can perform a complex scientific task by interleaving data access, querying, and manipulation, as well as analytical steps and computations in complex, problem specific ways. We show how our system is used by a geneticist for solving the problem of discovering the so-called "co-regulated" genes by interlinking data and computation from several Web sites, local computations, as well as local and remote databases. The main distinctive features of our system (compared, e.g., to the ZOO environment (Ioannidis et al., 1996)) include: (i) executable workflows run as Web services; (ii) abstract workflows employ concept names and semantic types that are higher-level (and thus more "scientist friendly") than executable workflows; and (iii) our system supports automatic translation of the latter into the former.
8665183
Dynamic detection and removal of inactive clauses in SAT with application in image computation
In this paper, we present a new technique for the efficient dynamic detection and removal of inactive clauses, i.e. clauses that do not affect the solutions of interest of a Boolean satisfiability (SAT) problem. The algorithm is based on the extraction of gate connectivity information during generation of the Boolean formula from the circuit, and its use in the inner loop of a branch-and-bound SAT algorithm. The motivation for this optimization is to exploit the circuit structure information, which can be used to find unobservable gates at circuit outputs under dynamic conditions. It has the potential to speed up all applications of SAT in which the SAT formula is derived from a logic circuit. In particular, we find that it has considerable impact on an image computation algorithm based on SAT. We present practical results for benchmark circuits which show that the use of this optimization consistently improves the performance for reachability analysis, in some cases enabling the prototype tool to reach more states than otherwise possible.
5331854
On the Scalable Computation of Large Sets of Integrals
We consider efficient strategies for the parallel and distributed computation of large sets of multivariate integrals. These arise in many applications such as computational chemistry, high energy physics and finite element problems. We use a hierarchical architecture which is highly scalable and allows parallelization not only at the domain level but also at the integral level. We present experimental results on a family of parametrized integrals and show that our approach leads to an efficient scalable load balanced algorithm. The methods are easily applicable to other areas where a large number of problems need to be solved efficiently on a parallel and distributed system.
607185
Localization using evolution strategies in sensornets
With the emergence of wireless sensor networks and pervasive computing, innovative location-aware technologies and services are being investigated. Several iterative approaches employing distributed computations over sensors have been proposed in the literature for locating all the sensor nodes in the network. Due to their iterative nature these techniques are inefficient in terms of power, a very precious resource in sensor networks. This paper presents a novel power efficient approach aimed at identifying the locations of all the nodes in a sensor network given the location of a small subset of nodes. The technique, using evolution strategies, is independent of the ranging method used to estimate distances between nodes and involves sink nodes in the computation. The proposed approach provides substantial energy savings over existing techniques while providing comparable accuracy, and requires the presence of at least one neighbor for each sensor node compared to at least 3 neighbors for most of the existing techniques
10298588
Using Statically Computed Invariants Inside the Predicate Abstraction and Refinement Loop
Predicate abstraction is a powerful technique for extracting finite-state models from often complex source code. This paper reports on the usage of statically computed invariants inside the predicate abstraction and refinement loop. The main idea is to selectively strengthen (conjoin) the concrete transition relation at a given program location by efficiently computed invariants that hold at that program location. We experimentally demonstrate the usefulness of transition relation strengthening in the predicate abstraction and refinement loop. We use invariants of the form ±x ±y ≤c where c is a constant and x,y are program variables. These invariants can be discovered efficiently at each program location using the octagon abstract domain. We observe that the abstract models produced by predicate abstraction of strengthened transition relation are more precise leading to fewer spurious counterexamples, thus, decreasing the total number of abstraction refinement iterations. Furthermore, the length of relevant fragments of spurious traces needing refinement shortens. This leads to an addition of fewer predicates for refinement. We found a consistent reduction in the total number of predicates, maximum number of predicates tracked at a given program location, and the overall verification time.