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

Random Structures & algorithms 1990年第4期1卷 447-460页

作者： Feige, Uriel Peleg, David Raghavan, Prabhakar Upfal, Eli The Weizmann Institute of Science Rehovot 76100 Israel IBM T.J. Watson Research Center Yorktown Heights New York 10598 United States IBM Almaden Research Center San Jose California United States Department of Applied Mathematics Weizmann Institute of Science Rehovot Israel

In this paper we study the rate at which a rumor spreads through an undirected graph. This study has two important applications in distributed computation: in simple, robust and efficient broadcast protocols, and in t... 详细信息

关键词： distributed computation random graphs randomized algorithms rumor propagation

来源：评论

学校读者我要写书评

暂无评论

OPTIMAL AND SUBLOGARITHMIC TIME randomized PARALLEL SORTING algorithms

引用

SIAM JOURNAL ON COMPUTING 1989年第3期18卷 594-607页

作者： RAJASEKARAN, S REIF, JH Harvard Univ MA United States

This paper assumes a parallel RAM (random access machine) model which allows both concurrent reads and concurrent writes of a global memory.

关键词： 68Q25 randomized algorithms parallel sorting parallel random access machines random permutations radix sort prefix sum optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

THE BIT COMPLEXITY OF randomized LEADER ELECTION ON A RING

引用

SIAM JOURNAL ON COMPUTING 1989年第1期18卷 12-29页

作者： ABRAHAMSON, K ADLER, A GELBART, R HIGHAM, L KIRKPATRICK, D UNIV BRITISH COLUMBIA DEPT MATHVANCOUVER V6T 1W5BCCANADA

The inherent bit complexity of leader election on asynchronous unidirectional rings of processors is examined under various assumptions about global knowledge of the ring. If processors have unique identities with a maximum of m bits, then the expected number of communication bits sufficient to elect a leader with probability 1, on a ring of (unknown) size n is

O (n m)

来源：评论

学校读者我要写书评

暂无评论

The Two-Processor Scheduling Problem is in Random NC

引用

SIAM Journal on Computing 1989年第6期18卷 1140-1148页

作者： Umesh V. Vazirani Vijay V. Vazirani

An efficient parallel algorithm $({\text{RNC}}^2 )$ for the two-processor scheduling problem is presented. An interesting feature of this algorithm is that it finds a highest-level-first schedule; such a schedule defines a lexicographically first solution to this problem in a natural way. A key ingredient of the algorithm is a generalization of a theorem of Tutte which establishes a one-to-one correspondence between the bases of the Tutte matrix of a graph and the sets of matched nodes in maximum matchings in the graph.

关键词： 15A03 15A15 68Q25 68R05 68R10 scheduling matching parallel algorithms randomized algorithms basis of a matrix

来源：评论

学校读者我要写书评

暂无评论

A randomized PARALLEL BRANCH-AND-BOUND ALGORITHM

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 1988年第3期17卷 277-301页

作者： JANAKIRAM, VK GEHRINGER, EF AGRAWAL, DP MEHROTRA, R N CAROLINA STATE UNIV DEPT ELECT & COMP ENGNCOMP SYST LABRALEIGHNC 27695 ARTHUR ANDERSEN & CO CHICAGOIL 60603

randomized algorithms are algorithms that employ randomness in their solution method. We show that the performance of randomized algorithms is less affected by factors that prevent most parallel deterministic algorithms from attaining their theoretical speedup bounds. A major reason is that the mapping of randomized algorithms onto multiprocessors involves very little scheduling or communication overhead. Furthermore, reliability is enhanced because the failure of a single processor leads only to degradation, not failure, of the algorithm. We present results of an extensive simulation done on a multiprocessor simulator, running a randomized branch-and-bound algorithm. The particular case we consider is the knapsack problem, due to its ease of formulation. We observe the largest speedups in precisely those problems that take large amounts of time to solve.

关键词： Branch-and-bound randomized algorithms parallel algorithms speedup

来源：评论

学校读者我要写书评

暂无评论

A NOTE ON EXTENDING KNUTH TREE ESTIMATOR TO DIRECTED ACYCLIC GRAPHS

引用

INFORMATION PROCESSING LETTERS 1987年第3期24卷 203-206页

作者： PITT, L Aiken Computation Laboratory Harvard University Cambridge MA 02138 U.S.A.

D. E. Knuth showed that the cost of searching a tree may be estimated by a simple random walk in the tree. It is shown how Knuth's algorithm may be extended to estimate the cost of searching a rooted, directed acyclic graph (a DAG). The algorithm also gives an estimate of the size of a DAG. While the technique only applies to acyclic directed graphs, any search strategy must detect cycles to avoid nontermination. Thus, even in this situation, the space being searched is effectively a rooted DAG.

关键词： Backtrack search directed graph randomized algorithms estimation

来源：评论

学校读者我要写书评

暂无评论

CONVERGENCE AND FINITE-TIME BEHAVIOR OF SIMULATED ANNEALING

引用

ADVANCES IN APPLIED PROBABILITY 1986年第3期18卷 747-771页

作者： MITRA, D ROMEO, F SANGIOVANNIVINCENTELLI, A UNIV CALIF BERKELEY DEPT ELECT ENGN & COMP SCIBERKELEYCA 94720

Simulated annealing is a randomized algorithm which has been proposed for finding globally optimum least-cost configurations in large NP-complete problems with cost functions which may have many local minima. A theoretical analysis of simulated annealing based on its precise model, a time-inhomogeneous Markov chain, is presented. An annealing schedule is given for which the Markov chain is strongly ergodic and the algorithm converges to a global optimum. The finite-time behavior of simulated annealing is also analyzed and a bound obtained on the departure of the probability distribution of the state at finite time from the optimum. This bound gives an estimate of the rate of convergence and insights into the conditions on the annealing schedule which gives optimum performance.

关键词： GLOBAL OPTIMIZATION randomized algorithms TIME-INHOMOGENEOUS MARKOV CHAINS

来源：评论

学校读者我要写书评

暂无评论

A SIMPLE AND EFFICIENT randomized BYZANTINE AGREEMENT ALGORITHM

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1985年第6期11卷 531-539页

作者： CHOR, B COAN, BA Laboratory for Computer Science Massachusetts Institute of Technology

A new randomized Byzantine agreement algorithm is introduced. This algorithm functions in a synchronous system of n processors, at most t of which can fail. The algorithm reaches agreement in given expected rounds and given expected message bits independent of the distribution of processor failures. This performance is improved to a constant expected number of rounds and message bits if the distribution of processor failures is assumed to be uniform. In either case, the algorithm improves on the known lower limit on rounds for deterministic algorithms. Other benefits of the algorithm include: 1. It requires no cryptographic methods. 2. The amount of local computation is small. 3. The expected number of random bits used per processor is only one. It is argued that, in many practical applications of Byzantine agreement, the randomized algorithm presented here achieves superior performance.

关键词： randomized algorithms Byzantine Agreement Fault Tolerance

来源：评论

学校读者我要写书评

暂无评论

UNBOUNDED SPEED VARIABILITY IN DISTRIBUTED COMMUNICATIONS-SYSTEMS

引用

SIAM JOURNAL ON COMPUTING 1985年第1期14卷 75-92页

作者： REIF, JH SPIRAKIS, PG NYU COURANT INST MATH SCINEW YORKNY 10012

This paper concerns the fundamental problem of synchronizing communication between distributed processes whose speeds (steps per time unit) vary dynamically. Communication must be established in matching pairs, which are mutually willing to communicate. We show how to implement a distributed local scheduler to find these pairs. The only means of synchronization are boolean “flag” variables, each of which can be written by only one process and read by at most one other process.

关键词： distributed networks communicating sequential processes handshake communication synchronization real-time response probabilistic choice randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

REAL-TIME SYNCHRONIZATION OF INTERPROCESS COMMUNICATIONS

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 1984年第2期6卷 215-238页

作者： REIF, JH SPIRAKIS, PG Aiken Computation Laboratory Harvard University Cambridge MA Department of Computer Science Courant Institute of Mathematical Sciences New York University 251 Mercer Street New York NY

This paper considers a fixed (possibly infinite) set of distributed asynchronous processes, which at various times are willing to communicate with each other. Each process has various ports, each of which is used for communication with a distinct neighbor process. Each process can have at most one port open at any time, and its other ports must be closed. Two processes handshake over a time interval A if their respective ports are open for mutual communication during this interval. Note that the handshake relation is a matching. Successful communication requires a handshake of at least one step of each process;during the one-step overlap a message can be transmitted between processes. The problem is to synchronize processes (via a distributed scheduler) so that they can successfully handshake at their will, given that the means of synchronization is some low-level construct that does not guarantee the handshake property if used in an unsophisticated way. Probabilistic distributed algorithms for synchronizing processes so that they can handshake at will are described. A process is considered to be tame over a time interval A if its speed varies within certain arbitrarily fixed nonzero bounds. Our synchronization algorithms are shown to have real-time response: If a pair of processers are mutually willing to communicate within a time interval A of length at least a given constant and the pair are tame on A, then they establish communication within A with high likelihood (for the worst case behavior of the system), and the expected time for establishment of communication is also constant. Our model and algorithms are applied to solve a large class of real-time resource allocation problems, as well as real-time implementation of the synchronization primitives of Hoare's multiprocessing language CSP. © 1984, ACM. All rights reserved.

关键词： asynchronous systems communicating sequential processes expected time handshake protocols Interprocess communication probabilistic choice randomized algorithms response time symmetry synchronization

来源：评论

学校读者我要写书评

暂无评论

全选清除本页清除全部题录导出标记到“检索档案”

共142页 << < 133 134 135 136 137 138 139 140 141 142 > >>

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

电话和邮箱必须正确填写，我们会与您联系确认。

联系人：

所在院系：

联系邮箱：

联系电话：

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：