35226732
Linear-time algorithms for computing the reliability of bipartite and (#<=2) star distributed computing systems
Abstract Let S =( V , F ) denote a distributed computing system with star topology, where V is the set of nodes of S and F is the set of files distributed in V . The problem of computing the reliability of S has been shown to be #P-complete. Therefore, all known exact algorithms for this problem have exponential time complexity. This study presents two linear-time algorithms to compute the reliability of two restricted subclasses of S . The first algorithm runs in O(| F |) when the file distribution is limited to being bipartite and non-separable. The second algorithm runs in O(| V |), when each file is allocated to at most two distinct nodes and each node contains at most two distinct records. If the failure and working probabilities of every node are identical, then the computation can be accelerated to O(log(| V |)) time by means of the Fibonacci number and the Lucas number. Scope and purpose The star topology has become increasingly popular in distributed computing systems as it offers higher reliability, lower installation cost, and more flexibility than other topologies. The computation of the reliability of star distributed computing systems is shown to be #P-complete. Therefore, computing the reliability of such a system is intractable. This article presents two fast linear-time algorithms to compute the reliability of two restricted subclasses of star distributed computing systems.
45057698
The distributed program reliability analysis on star topologies
Abstract A distributed computing system consists of processing elements, communication links, memory units, data files, and programs. These resources are interconnected via a communication network and controlled by a distributed operating system. The distributed program reliability in a distributed computing system is the probability that a program which runs on multiple processing elements and needs to retrieve data files from other processing elements will be executed successfully. This reliability varies according to (1) the topology of the distributed computing system, (2) the reliability of the communication edges, (3) the data files and programs distribution among processing elements, and (4) the data files required to execute a program. In this paper, we show that computing the distributed program reliability on the star distributed computing systems is NP-hard. We also develop an efficiently solvable case to compute distributed program reliability when some additional file distribution is restricted on the star topology. Scope and purpose Recent advances in VLSI circuitry have a tremendous impact on the price-performance revolution in microelectronics. This development has led to an increased use of workstations connected in the form of a powerful distributed computing system. Potential benefits offered by such distributed computing systems include better cost performance, enhanced fault tolerance, increased system throughput, and efficient sharing of resources. Distributed program reliability is an important measure that should be examined for designing a high fault-tolerance distributed computing system. This reliability varies according to (1) the topology of the distributed computing system, (2) the reliability of the communication edges, (3) the data files and programs distribution among processing elements, and (4) the data files required to execute a program. This article is concerned with the analysis of distributed program reliability on star distributed computing systems.
9086045
The distributed program reliability analysis on star topologies
We show that computing distributed program reliability on the star distributed computing system is NP-hard. We develop a polynomially solvable case to compute distributed program reliability when some additional file distribution is restricted on the star topology. We also propose a polynomial time algorithm for computing distributed program reliability with an approximate solution when the star topology is not satisfied with the additional file distribution.
205481590
Fast and simple algorithms to count the number of vertex covers in an interval graph
This study provides the following fast and simple algorithms for an interval graph: (1) an algorithm for counting the number of vertex covers, and (2) an algorithm for counting the number of minimal vertex covers.
50312
The distributed program reliability analysis on ring-type topologies
Abstract Distributed computing system (DCS) has become very popular for its high fault-tolerance, potential for parallel processing, and better reliability performance. One of the important issues in the design of the DCS is the reliability performance. Distributed program reliability (DPR) is addressed to obtain this reliability measure. In this paper, we propose a polynomial-time algorithm for computing the DPR of ring topology and show that solving the DPR problem on a ring of trees topology is NP-hard. Scope and purpose The widespread use of distributed computing system is due to the price–performance revolution in microelectronics, the development of cost-effective and efficient communication subsets, the development of resource sharing software, and the increased user demands for communication, economical sharing of resources, and productivity. This article is concerned with the analysis of distributed program reliability on a ring-distributed computing system. The distributed program reliability is a useful measure for reliability evaluation of distributed computing system. The distributed program reliability analyses also give a good index for designing a high-reliability-performance-distributed computing system.
5909240
The Computational Complexity of the Reliability Problem on Distributed Systems
Abstract The reliability of a distributed program in a distributed computing system is the probability that a program which runs on multiple processing elements and needs to communicate with other processing elements for remote data files will be executed successfully. This reliability varies according to 1. (1) the topology of the distributed computing system 2. (2) the reliability of the communication links 3. (3) the data files and program distribution among processing elements and 4. (4) the data files required to execute a program. This paper shows that solving this reliability problem is NP-hard even when the distributed computing system is restricted to a series-parallel, a 2-tree, a tree, or a star structure.
5692452
k-server optimal task scheduling problem with convex cost function
We consider a class of k-server optimal task scheduling problems partitioning and scheduling N tasks with various real-time constrains and work loads on k servers with convex task processing cost function so as to minimize the total task processing cost while still guaranteeing satisfaction of all time constraints. This class has broad expressing power for practical scheduling problems in several areas such as real-time multimedia wireless transmission , CPU energy conservation, and warehouse order processing management, et. al. Our formulation is quite general such that most previous works can be readily reduced to a special case of the presented k-server optimal task scheduling problem. We show that, when k = 1, optimal solution can be obtained in computational complexity of O(N) and the corresponding optimal scheduling problem is equivalent to finding the shortest 2D Euclidean distance between two vertices inside a well-defined 2D polygon. However, when k 2, the optimal scheduling problem can be demonstrated to be NP-hard by reducing it to a well-known NP-complete bin-packing problem. Therefore, we conclude no polynomial time algorithm exists for a general k-server optimal task scheduling problem. We then construct approximation algorithms to solve the presented k-server problem in a practical way and illustrate its performance by simulation results and analysis.
7639620
Stable and responsive six-degree-of-freedom haptic manipulation using implicit integration
In this paper we present a novel approach for simulating the rigid body dynamics of a haptically manipulated object using implicit integration. Our formulation requires the linearization of contact and manipulation forces, and it provides higher stability and responsiveness than previous methods. The linearization of contact forces, coupled with fast, perceptually based collision detection algorithms, enables us to perform highly stable and responsive 6-degree-of-freedom haptic rendering of complex polygonal models.
6288895
A Survey on Hair Modeling: Styling, Simulation, and Rendering
Realistic hair modeling is a fundamental part of creating virtual humans in computer graphics. This paper surveys the state of the art in the major topics of hair modeling: hairstyling, hair simulation, and hair rendering. Because of the difficult, often unsolved problems that arise in alt these areas, a broad diversity of approaches is used, each with strengths that make it appropriate for particular applications. We discuss each of these major topics in turn, presenting the unique challenges facing each area and describing solutions that have been presented over the years to handle these complex issues. Finally, we outline some of the remaining computational challenges in hair modeling
2903221
Algorithms for clique-independent sets on subclasses of circular-arc graphs
A circular-arc graph is the intersection graph of arcs on a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum cardinality of a clique-independent set for a general graph. In the present paper, we propose polynomial time algorithms for finding the maximum cardinality and weight of a clique-independent set of a 3K2-free CA graph. Also, we apply the algorithms to the special case of an HCA graph. The complexity of the proposed algorithm for the cardinality problem in HCA graphs is O(n). This represents an improvement over the existing algorithm by Guruswami and Pandu Rangan, whose complexity is O(n2). These algorithms suppose that an HCA model of the graph is given.
33339608
Almost Optimal Solutions for Bin Coloring Problems
In this paper we study two interesting bin coloring problems: Minimum Bin Coloring Problem (MinBC) and Online Maximum Bin Coloring Problem (OMaxBC), motivated from several applications in networking. For the MinBC problem, we first show that it is NP-complete, and then present two near linear time approximation algorithms to achieve almost optimal solutions, i.e., no more than OPT+2 and OPT+1 respectively, where OPT is the optimal solution. For the OMaxBC problem, we first introduce a deterministic 2-competitive greedy algorithm, and then give lower bounds for any deterministic and randomized (against adaptive offline adversary) online algorithms. The lower bounds show that our deterministic algorithm achieves the best possible competitive ratio.