检索结果-内蒙古大学图书馆

Task allocation for maximizing reliability of a distributed system using hybrid particle swarm optimization

JOURNAL OF systems AND SOFTWARE 2007年第5期80卷 724-735页

作者： Yin, Peng-Yeng Yu, Shiuh-Sheng Wang, Pei-Pei Wang, Yi-Te Natl Chi Nan Univ Dept Informat Management Puli 545 Nantou Taiwan

In a distributed computing system, a number of program modules may need to be allocated to different processors such that the reliability of executing successfully these modules is maximized and the constraints with limited resources are satisfied. The problem of finding an optimal task allocation with maximum system reliability has been shown to be NP-hard;thus, existing approaches to finding exact solutions are limited to the use in problems of small size. This paper presents a hybrid particle swarm optimization (HPSO) algorithm for finding the near-optimal task allocation within reasonable time. The experimental results show that the HPSO is robust against different problem size, task interaction density, and network topology. The proposed method is also more effective and efficient than a genetic algorithm for the test-cases studied. The convergence and the worst-case characteristics of the HPSO are addressed using both theoretical and empirical analysis. (c) 2006 Elsevier Inc. All rights reserved.

关键词： task allocation problem distributed computing systems distributed system reliability hybrid strategy particle swarm optimization genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Linear-time algorithms for computing the reliability of bipartite and (# ≤ 2) star distributed computing systems

引用

COMPUTERS & OPERATIONS RESEARCH 2003年第11期30卷 1697-1712页

作者： Lin, MS Natl Taipei Univ Technol Dept Elect Engn Taipei 106 Taiwan

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.

关键词： reliability distributed computing systems #P-complete linear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal k-bounded placement of resources in distributed computing systems

引用

IEICE TRANSACTIONS ON INFORMATION AND systems 2000年第7期E83D卷 1480-1487页

作者： Kim, JH Lee, CH Chungnam Natl Univ Dept Comp Engn Parallel Proc Lab Yusong Gu Taejon 305764 South Korea

We consider the problem of placing resources in a distributed computing system so that certain performance requirements may be met while minimizing the number of resource copies needed. Resources include special I/O processors, expensive peripheral devices, or such software modules as compilers, library routines, and data files. Due to the delay in accessing each of these resources, system performance degrades as the distance between each processor and its nearest resource copy increases. Thus, every processor must be within a given distance k greater than or equal to 1 of st least one resource copy, which is called the k-bounded placement problem. The structure of a distributed computing system is rep resented by a graph. The Ic-bounded placement problem is first transformed into the problem of finding smallest k-dominating sets in a graph. Searching for smallest k-dominating sets is formulated as a state-space search problem. We derive heuristic information to speed up the search, which is then used to solve the problem with the well-known A* algorithm. An illustrative example and some experimental results are presented to demonstrate the effectiveness of the heuristic search.

关键词： A* algorithm interprocessor communication distributed computing systems k-bounded resource placement k-dominating sets state-space search

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for reliability analysis of distributed computing systems

引用

INFORMATION SCIENCES 1999年第1-2期117卷 89-106页

作者： Lin, MS Chang, MS Chen, DJ Tamsui Oxford Univ Coll Dept Informat Management Taipei 25103 Taiwan Natl Chiao Tung Univ Dept Comp Sci & Informat Engn Hsinchu 30050 Taiwan

A distributed computing system is modeled as a collection of resources (e.g. processing elements, data tiles and programs) interconnected via an arbitrary communication network and controlled by a distributed operating system, The distributed program reliability in a distributed computing system is the probability of successful execution of a program running on multiple processing elements and needs to retrieve data files from other processing elements. 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 addition, computing the reliability of distributed computing systems is #P-complete even when the distributed computing system is restricted to a series-parallel, a 2-tree, a tree, or a star structure. This paper presents efficient algorithms for computing the reliability of a distributed program running on other restricted classes of networks. (C) 1999 Elsevier Science Inc. All rights reserved.

关键词： distributed computing systems distributed program reliability computational complexity algorithms

来源：评论

学校读者我要写书评

暂无评论

A task migration algorithm for heterogeneous distributed computing systems

引用

JOURNAL OF systems AND SOFTWARE 1998年第3期41卷 175-188页

作者： Tiemeyer, MP Wong, JSK Iowa State Univ Dept Comp Sci Ames IA 50011 USA

Most load balancing schemes are based on the assumption that all processors in a distributed computing system (DCS) have similar processing power and workload. However, as technology continues to advance, networks have become more likely to contain processors of different capabilities and configurations. The proposed load balancing method is based on the coterie, a tool first used in mutual exclusion and vote assignment. This paper describes how the unique properties of coteries allow the underlying protocol to be tailored to the capabilities of the individual nodes in a connected network. In general, each processor communicates with only a subset of the other processors in the network, keeping message traffic relatively low. The coterie allows these subsets to be constructed according to a more thoughtful method - one that is designed to better meet the needs of networks of varying characteristics. It is also shown that the proposed method will always perform task migration whenever possible i.e., if at least one lightly loaded processor and at least one heavily loaded processor exist in the network, task migration will occur. Further, an extension of our algorithm to provide fault tolerance is given: when a processor fails, the network can continue to function with a modified system configuration. (C) 1998 Elsevier Science Inc. All rights reserved.

关键词： coterie load balancing fault tolerance distributed computing systems heterogeneous systems

来源：评论

学校读者我要写书评

暂无评论

Architecture of a VOD system with proxy servers

引用

IEICE TRANSACTIONS ON COMMUNICATIONS 2000年第4期E83B卷 850-857页

作者： Ahn, KA Choi, H Kim, WO Chungnam Natl Univ Dept Comp Engn Distributed Syst Lab Yusong Gu Taejon 305764 South Korea

We present an architecture of a VOD system employing proxy servers. The proposed VOD system provides efficient and reliable VOD services and solves the problems caused by traditional VOD systems of centralized, hierarchical or distributed architecture. The proxy servers are placed between video servers and user systems. The proxy server is a small size video server that has not only caching function but also intelligence such as VCR-like video stream control or navigation of other proxy/video servers to search for a selected video program. Using a VOD system of the proposed architecture, the VOD services can be provided to more users because it reduces the workload of video servers and network traffic, me provide the performance model of the system. Service availability is also analyzed. The proposed architecture shows better performance and availability than the traditional VOD architectures.

关键词： video-on-demand distributed computing systems proxy-distributed architecture cache replacement service availability traffic analysis

来源：评论

学校读者我要写书评

暂无评论

A dual-ascent procedure for the file allocation and join site selection problem on a telecommunications network

引用

NETWORKS 1999年第2期33卷 109-124页

作者： Murthy, I Seo, PK Louisiana State Univ Dept Informat Syst & Decis Sci Baton Rouge LA 70803 USA Myung Jee Univ Seoul South Korea

In this paper, a model and a solution procedure is developed for the File Allocation and Join Site Selection Problem with 2-way Join [FAJSP-2], defined on a telecommunications network. This problem attempts to integrate the file allocation and query optimization aspects of a distributed computing system. By allowing for queries that require processing up to two file types, this problem is designed to determine simultaneously the number and location of file types and the location of join operations. This problem is modeled as a mixed-integer linear program, for which a fast dual-ascent approximation procedure is developed. Extensive computational results are presented which demonstrate that our dual-ascent procedure is able to solve even large-scale problems to near optimality quickly. (C) 1999 John Wiley & Sons, Inc.

关键词： telecommunications network distributed computing systems integer programming dual ascent

来源：评论

学校读者我要写书评

暂无评论

Efficient rollback recovery technique in distributed computing systems

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed systems 1996年第6期7卷 565-577页

作者： Chiu, GM Young, CR Department of Electrical Engineering and Technology National Taiwan Institute of Technology Taipei Taiwan

In this paper we propose a new approach for implementing rollback-recovery in a distributed computing system. A concept of logical ring is introduced for the maintenance of information required for consistent recovery from a system crash. Message processing order of a process is kept by all other processes on its logical ring. Transmission of data messages are accompanied by the circulation of the associated order messages on the ring. The sizes of the order messages are small. In addition, redundant transmission of order information is avoided, thereby reducing the communication overhead incurred during failure-free operation. Furthermore, updating of the order information and garbage collection task are simplified in the proposed mechanism. Our approach does not require information about message processing order be written to stable storage;in fact, the time-consuming operations of saving information in stable storage are confined to the checkpointing activities. When failures occur, a surviving process need roll back only if some preceding order information is totally lost, which is relatively unlikely considering the ever growing speed of communication networks. It is shown that a system can recover correctly as long as there exists at least one surviving process.

关键词： checkpoint crash recovery distributed computing systems fault tolerance logical ring rollback

来源：评论

学校读者我要写书评

暂无评论

A genetic task allocation algorithm for distributed computing systems incorporating problem specific knowledge

引用

INTERNATIONAL JOURNAL OF HIGH SPEED computing 1996年第4期8卷 363-370页

作者： Tripathi, AK Vidyarthi, DP Mantri, AN BANARAS HINDU UNIV FAC SCIDEPT COMP SCIVARANASI 221005UTTAR PRADESHINDIA

distributed computing systems (DCS) promise a convenient platform for parallel processing and consequently can be expected to provide highly improved throughput and turnaround characteristics for all types of computing jobs. Task allocation in DCS remains to be an important and relevant problem attracting the attention of researchers in the discipline. Genetic Algorithms (GA) have successfully been used to solve various optimization problems. A GA based task allocation model for multiprocessors has been proposed by Hou, Ansari & Ren [3]. We present a Genetic Task Allocation Algorithm for DCS, wherein we have considered the underlying interconnection network of the processors, communication requirements among modules of the tasks apart from the precedence relation of the task graph that has been considered in [3] also. We have also considered multiprogramming at every processing nodes with related characteristic values. We have, intentionally, made use of the finding [4] that the incorporation of the problem specific knowledge in construction of GAs improves the initial population structures. The model and algorithm proposed by us is sufficiently simple and adequately usable for the purpose of simulation experiments and its possible incorporation in future operating systems of DCS.

关键词： distributed computing systems multiprogramming task Inter-Module Communication (IMC) genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Dynamic task allocation models for large distributed computing systems

引用

IEEE TRANSACTIONS ON PARALLEL AND distributed systems 1995年第12期6卷 1301-1315页

作者： Chang, HWD Oldham, WJB TEXAS TECH UNIV DEPT COMP SCILUBBOCKTX 79409

Dynamic task allocation for distributed computing systems (DCS) is an important goal to be achieved for engineering applications, The purpose of dynamic task allocation is to increase the system throughput in a dynamic environment, which can be done by balancing the utilization of computing resources and minimizing communication between processors during run time, In this paper, we propose two dynamic task allocation models which are: 1) the clustering simulated annealing model (CSAM) and 2) the mean field annealing model (MFAM). Both of these models combine characteristics of statistical and deterministic approaches, These models provide the rapid convergence characteristic of the deterministic approaches while preserving the solution quality afforded by simulated annealing, Simulation results of the CSAM acid MFAM provide a stable and balanced system with 50% and 10% of the convergence time needed by simulated annealing, respectively. The results of this research are important in that it presents the feasibility of applying statistically based task allocation models on large DCSs in a dynamic environment, Solutions of these models depend on the annealing process instead of the structures of the input data, providing the possibility of obtaining better solutions by using more efficient computing hardware.

关键词： distributed computing systems dynamic task allocation interprocessor communication load balancing optimization

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：