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

THE WEAKEST FAILURE DETECTORS TO SOLVE QUITTABLE CONSENSUS AND NONBLOCKING ATOMIC COMMIT

SIAM JOURNAL ON COMPUTING 2012年第6期41卷 1343-1379页

作者： Guerraoui, Rachid Hadzilacos, Vassos Kuznetsov, Petr Toueg, Sam Ecole Polytech Fed Lausanne Sch Comp & Commun Sci CH-1015 Lausanne Switzerland Univ Toronto Dept Comp Sci Toronto ON M5S 3G4 Canada TU Berlin Telekom Innovat Labs D-10587 Berlin Germany

We define quittable consensus, a natural variation of the consensus problem, where processes have the option to agree on "quit" if failures occur, and we relate this problem to the well-known problem of nonblocking atomic commit. We then determine the weakest failure detectors for these two problems in all environments, regardless of the number of faulty processes.

关键词： asynchronous distributed computing atomic commit problem consensus fault-tolerant algorithms failure detection

来源：评论

学校读者我要写书评

暂无评论

A new parallel solver suited for arbitrary semilinear parabolic partial differential equations based on generalized random trees

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2011年第21期230卷 7891-7909页

作者： Acebron, Juan A. Rodriguez-Rozas, Angel Inst Super Tecn Dept Math Ctr Math & Its Applicat P-1049001 Lisbon Portugal

A probabilistic representation for initial value semilinear parabolic problems based on generalized random trees has been derived. Two different strategies have been proposed, both requiring generating suitable random trees combined with a Pade approximant for approximating accurately a given divergent series. Such series are obtained by summing the partial contribution to the solution coming from trees with arbitrary number of branches. The new representation greatly expands the class of problems amenable to be solved probabilistically, and was used successfully to develop a generalized probabilistic domain decomposition method. Such a method has been shown to be suited for massively parallel computers, enjoying full scalability and fault tolerance. Finally, a few numerical examples are given to illustrate the remarkable performance of the algorithm, comparing the results with those obtained with a classical method. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Monte Carlo methods Domain decomposition Semilinear parabolic problems Parallel computing fault-tolerant algorithms Random trees

来源：评论

学校读者我要写书评

暂无评论

Local dependency dynamic programming in the presence of memory faults

Local dependency dynamic programming in the presence of memo...

引用

28th International Symposium on Theoretical Aspects of Computer Science (SATCS)

作者： Caminiti, Saverio Finocchi, Irene Fusco, Emanuele G. Sapienza Univ Rome Dept Comp Sci Via Salaria 113 I-00198 Rome Italy

ISBN: (纸本)9783939897255

We investigate the design of dynamic programming algorithms in unreliable memories, i.e., in the presence of faults that may arbitrarily corrupt memory locations during the algorithm execution. As a main result, we devise a general resilient framework that can be applied to all local dependency dynamic programming problems, where updates to entries in the auxiliary table are determined by the contents of neighboring cells. Consider, as an example, the computation of the edit distance between two strings of length n and m. We prove that, for any arbitrarily small constant epsilon is an element of (0, 1] and n >= m, this problem can be solved correctly with high probability in O (nm + alpha delta(1+epsilon)) worst-case time and O(nm + n delta) space, when up to delta memory faults can be inserted by an adversary with unbounded computational power and alpha <= delta is the actual number of faults occurring during the computation. We also show that an optimal edit sequence can be constructed in additional time O (n delta + alpha delta(1+epsilon)). It follows that our resilient algorithms match the running time and space usage of the standard non-resilient implementations while tolerating almost linearly-many faults.

关键词： Unreliable memories fault-tolerant algorithms local dependency dynamic programming edit distance

来源：评论

学校读者我要写书评

暂无评论

Dynamic programming in faulty memory hierarchies (cache-obliviously)

Dynamic programming in faulty memory hierarchies (cache-obli...

引用

31st IARCS Annual International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)

作者： Caminiti, Saverio Finocchi, Irene Fusco, Emanuele G. Silvestri, Francesco Univ Roma La Sapienza Dept Comp Sci Rome Italy Univ Padua Dept Informat Engn I-35100 Padua Italy

ISBN: (纸本)9783939897347

Random access memories suffer from transient errors that lead the logical state of some bits to be read differently from how they were last written. Due to technological constraints, caches in the memory hierarchy of modern computer platforms appear to be particularly prone to bit flips. Since algorithms implicitly assume data to be stored in reliable memories, they might easily exhibit unpredictable behaviors even in the presence of a small number of faults. In this paper we investigate the design of dynamic programming algorithms in faulty memory hierarchies. Previous works on resilient algorithms considered a one-level faulty memory model and, with respect to dynamic programming, could address only problems with local dependencies. Our improvement upon these works is two-fold: (1) we significantly extend the class of problems that can be solved resiliently via dynamic programming in the presence of faults, settling challenging non-local problems such as all-pairs shortest paths and matrix multiplication;(2) we investigate the connection between resiliency and cache-efficiency, providing cache-oblivious implementations that incur an (almost) optimal number of cache misses. Our approach yields the first resilient algorithms that can tolerate faults at any level of the memory hierarchy, while maintaining cache-efficiency. All our algorithms are correct with high probability and match the running time and cache misses of their standard non-resilient counterparts while tolerating a large (polynomial) number of faults. Our results also extend to Fast Fourier Transform.

关键词： Unreliable memories fault-tolerant algorithms dynamic programming cache-oblivious algorithms Gaussian elimination paradigm

来源：评论

学校读者我要写书评

暂无评论

Efficient Parallel Solution of Nonlinear Parabolic Partial Differential Equations by a Probabilistic Domain Decomposition

引用

JOURNAL OF SCIENTIFIC COMPUTING 2010年第2期43卷 135-157页

作者： Acebron, Juan A. Rodriguez-Rozas, Angel Spigler, Renato Inst Super Tecn Ctr Math & Applicat Dept Math P-1049001 Lisbon Portugal Univ Roma Tre Dipartimento Matemat I-00146 Rome Italy

Initial- and initial-boundary value problems for nonlinear one-dimensional parabolic partial differential equations are solved numerically by a probabilistic domain decomposition method. This is based on a probabilistic representation of solutions by means of branching stochastic processes. Only few values of the solution inside the space-time domain are generated by a Monte Carlo method, and an interpolation is then made so to approximate suitable interfacial values of the solution inside the domain. In this way, a fully decoupled set of sub-problems is obtained. This method allows for an efficient massively parallel implementation, is scalable and fault tolerant. Numerical examples, including some for the KPP equation and beyond are given to show the performance of the algorithm.

关键词： Monte Carlo methods Domain decomposition Branching stochastic processes Nonlinear parabolic problems Parallel computing fault-tolerant algorithms

来源：评论

学校读者我要写书评

暂无评论

Recovery patterns for iterative methods in a parallel unstable environment

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2007年第1期30卷 102-116页

作者： Langou, J. Chen, Z. Bosilca, G. Dongarra, J. Univ Colorado Hlth Sci Ctr Dept Math Sci Denver CO 80217 USA Jacksonville State Univ MCIS Dept Jacksonville AL 36265 USA Univ Tennessee Dept Comp Sci Knoxville TN 37996 USA

Several recovery techniques for parallel iterative methods are presented. First, the implementation of checkpoints in parallel iterative methods is described and analyzed. Then a simple checkpoint-free fault-tolerant scheme for parallel iterative methods, the lossy approach, is presented. When one processor fails and all its data is lost, the system is recovered by computing a new approximate solution using the data of the nonfailed processors. The iterative method is then restarted with this new vector. The main advantage of the lossy approach over standard checkpoint algorithms is that it does not increase the computational cost of the iterative solver when no failure occurs. Experiments are presented that compare the different techniques. The fault-tolerant FT-MPI library is used. Both iterative linear solvers and eigensolvers are considered.

关键词： fault-tolerant algorithms iterative methods parallel distributed

来源：评论

学校读者我要写书评

暂无评论

Probabilistically induced domain decomposition methods for elliptic boundary-value problems

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2005年第2期210卷 421-438页

作者： Acebrón, JA Busico, MP Lanucara, P Spigler, R Univ Rome Dipartimento Matemat I-00146 Rome Italy CASPUR I-00185 Rome Italy Univ Alcala de Henares Escuela Politecn Dept Automat Alcala De Henares 28871 Spain

Monte Carlo as well as quasi-Monte Carlo methods are used to generate only few interfacial values in two-dimensional domains where boundary-value elliptic problems are formulated. This allows for a domain decomposition of the domain. A continuous approximation of the solution is obtained interpolating on such interfaces, and then used as boundary data to split the original problem into fully decoupled subproblems. The numerical treatment can then be continued, implementing any deterministic algorithm on each subdomain. Both, Monte Carlo (or quasi-Monte Carlo) simulations and the domain decomposition strategy allow for exploiting parallel architectures. Scalability and natural fault tolerance are peculiarities of the present algorithm. Examples concern Helmholtz and Poisson equations, whose probabilistic treatment presents additional complications with respect to the case of homogeneous elliptic problems without any potential term and source. (c) 2005 Elsevier Inc. All rights reserved.

关键词： Monte Carlo methods quasi-Monte Carlo methods domain decomposition parallel computing fault-tolerant algorithms

来源：评论

学校读者我要写书评

暂无评论

Integrated fault-tolerant multicast and anycast routing algorithms

引用

IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES 2000年第4期147卷 266-274页

作者： Jia, W Xu, G Zhao, W City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

Anycast is a new communication service defined in IPv6 (Internet Protocol Version 6 for the next generation). An anycast message is the one that should be delivered to the 'nearest' member in a group of designated recipients. Anycast and multicast mechanisms may be integrated to provide better services. A group of replicated (or mirrored) servers that provides anycast service may also provide multicast services and needs multicast to consistently update, whereas anycast routing may help a multicast request to reach the 'nearest' member in a multicast group. A novel integration routing protocol is presented for both multicast and anycast messages communications in the internet. The protocol is composed of four algorithms: (1) dynamic anycast routing algorithm for efficient transmission of anycast messages over the internet to a group of servers. (2) integrated anycast routing with core-based tree technique based on multicast routing algorithms taking advantage of short delay, high throughput and load sharing. (3) fault-tolerant algorithms for both anycast and multicast routing using backup paths restoring techniques. The performance figures have demonstrated the benefits of anycast routing in reducing end-to-end packet delay, and attaining load balance and fault-tolerance for multicast.

关键词： Information networks protocols Computer communications integrated fault-tolerant multicast routing IPv6 fault-tolerant algorithms Protocols Other computer networks Internet integration routing protocol dynamic anycast routing algorithm anycast routing algorithms multicast communication Internet Protocol Version 6 fault tolerant computing communication service

来源：评论

学校读者我要写书评

暂无评论

A general method for maximizing the error-detecting ability of distributed algorithms

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1997年第2期8卷 164-172页

作者： Schollmeyer, M McMillin, B UNIV MISSOURI DEPT COMP SCIROLLAMO 65409

The bound on component failures and their spatial distribution govern the fault tolerance of any candidate error-detecting algorithm. For distributed memory multiprocessors, the specific algorithm and the topology of the processor interconnection network define these bounds. This paper introduces the maximal fault index, derived from the system topology and local communication patterns, to demonstrate how a maximal number of simultaneous component failures can be tolerated for a particular interconnection network and error-detecting algorithm. The index is used to design a mapping of processes to processor groups such that the error-detecting ability of the algorithm is preserved for certain multiple simultaneous processor failures.

关键词： error detection multicomputers fault-tolerant algorithms mapping fault tolerance architecture

来源：评论

学校读者我要写书评

暂无评论

AN EFFICIENT fault-tolerant DECENTRALIZED COMMIT PROTOCOL

引用

PARALLEL COMPUTING 1994年第1期20卷 101-114页

作者： YUAN, SM Department of Computer & Information Science National Chiao Tung University Hsinchu 30050 Taiwan

A new efficient decentralized commit protocol is proposed for distributed database systems. This protocol can be applied to systems of all sizes and is [log(2) N] - 2 resilient to site failures, where N is the number of sites in the system. In addition, the number of messages sent among the N sites is (N log(2)(2)N) which is only a factor of log(2) over the message complexity lower bound O(N In N) of decentralized commit protocols.

关键词： COMMIT PROTOCOLS DECENTRALIZED algorithms fault-tolerant algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：