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

The correctness proof of Ben-Or's randomized consensus algorithm

DISTRIBUTED COMPUTING 2012年第5期25卷 371-381页

作者： Aguilera, Marcos K. Toueg, Sam Microsoft Res Silicon Valley Mountain View CA 94043 USA Univ Toronto Toronto ON M5S 3G4 Canada

In a ground-breaking paper that appeared in 1983, Ben-Or presented the first randomized algorithm to solve consensus in an asynchronous message-passing system where processes can fail by crashing. Although more efficient randomized algorithms were subsequently proposed, Ben-Or's algorithm is still the simplest and most elegant one. For this reason, it is often taught in distributed computing courses and it appears in several textbooks. Even though Ben-Or's algorithm is widely known and it is very simple, surprisingly a proof of correctness of the algorithm has not yet appeared: previously published proofs make some simplifying assumptions-specifically, they either assume that f < n/3 (n is the total number of processes and f is maximum number of processes that may crash) or that the adversary is weak, that is, it cannot see the process states or the content of the messages. In this paper, we present a correctness proof for Ben-Or's randomized consensus algorithm for the case that f < n/2 process crashes and the adversary is strong (i.e., it can see the process states and message contents, and schedule the process steps and message receipts accordingly). To the best of our knowledge, this is the first full proof of this classical algorithm. We also demonstrate a counterintuitive problem that may occur if one uses the well-known abstraction of a "global coin" to modularize and speed up randomized consensus algorithms, such as Ben-Or's algorithm. Specifically, we show that contrary to common belief, the use of a global coin can sometimes be deleterious rather than beneficial: instead of speeding up Ben-Or's algorithm, the use of a global coin in this algorithm may actually prevent termination.

关键词： process state randomized algorithms algorithms correctness of algorithm Proof of correctness Crash Speeding Coin RANDOMISING

来源：评论

学校读者我要写书评

暂无评论

Proof of correctness of a direct construction of DFA from regular expression

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1997年第3-4期64卷 191-210页

作者： Babu, SR Sanyal, A Venkatesh, G Dept. of Comp. Sci. and Engineering Indian Institute of Technology Bombay 400076 India

We present a proof of correctness of an algorithm for directly constructing a deterministic finite automaton (DFA) from a regular expression. We do this in a functional framework by introducing a structure called dot annotated regular expression (dare). A dare acts as an implicit representation of a state in a DFA. State transitions in a DFA correspond to dot movements in a dare. We investigate and identify certain algebraic properties of dare's which are then used to prove the correctness of the algorithm. The proof is algebraic and presented in the same framework as that of the algorithm itself.

关键词： correctness of algorithm recognition problem regular expressions finite automata

来源：评论

学校读者我要写书评

暂无评论

Selection and determination of beam weights based on genetic algorithms for conformal radiotherapy treatment planning

引用

PHYSICS IN MEDICINE AND BIOLOGY 2000年第9期45卷 2547-2558页

作者： Wu, XG Zhu, YP Dai, JR Wang, ZL St Jude Childrens Res Hosp Dept Radiat Oncol Memphis TN 38105 USA SE Univ Dept Biomed Engn Nanjing 210096 Peoples R China

A genetic algorithm has been used to optimize the selection of beam weights for external beam three-dimensional conformal radiotherapy treatment planning. A fitness function is defined, which includes a difference function to achieve a least-square fit to doses at preselected points in a planning target volume, and a penalty item to constrain the maximum allowable doses delivered to critical organs. Adjustment between the dose uniformity within the target volume and the dose constraint to the critical structures can be achieved by varying the beam weight variables in the fitness function. A floating-point encoding schema and several operators, like uniform crossover, arithmetical crossover, geometrical crossover, Gaussian mutation and uniform mutation, have been used to evolve the population. Three different cases were used to verify the correctness of the algorithm and quality assessment based on dose-volume histograms and three-dimensional dose distributions were given. The results indicate that the genetic algorithm presented here has considerable potential.

关键词： Radiotherapy Planning Computer-Assisted Radiotherapy Conformal 放射治疗计划计算机辅助放射疗法适形 computer-assisted treatment planning Beams and girders Radiotherapy planning Radiotherapy Conformal Radiotherapy RADIATION DOSE DISTRIBUTIONS correctness of algorithm Planning Target Volume conformal Genetic algorithm (GA)

来源：评论

学校读者我要写书评

暂无评论

Identification of the Global Text Skew Based on the Convex Hulls

Identification of the Global Text Skew Based on the Convex H...

引用

36th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO)

作者： Brodic, Darko Milivojevic, Dragan R. Tasic, Visa Milivojevic, Zoran N. Univ Belgrade Tech Fac Bor Bor Serbia Inst Min & Met Bor Serbia Tech Coll Nis Nish Serbia

ISBN: (纸本)9789532330762

Old printed documents represent the important part of our heritage. For theirs preservation, the digitalization is indispensable. The paper proposes the algorithm for the identification of the global text skew. It is based on the connected components made by the filled convex hulls around each text element. Furthermore, connected components are enlarged by morphological dilatation. Currently, the biggest connected component is extracted. The global orientation of the document is identified by its orientation. Efficiency and correctness of the algorithm is examined by testing on datasets. Obtained results proved the algorithms correctness.

关键词： convex hull connected component texts husks Hulls Skew accuracy class correctness of algorithm Convexity algorithms Dataset

来源：评论

学校读者我要写书评

暂无评论

Finding the automorphism group of a circulant association scheme in polynomial time

引用

Journal of Mathematical Sciences 2006年第3期136卷 3972-3979页

作者： Ponomarenko, I.N. St. Petersburg Department Steklov Mathematical Institute St. Petersburg Russian Federation

A polynomial-time algorithm for finding the automorphism group of a circulant association scheme is constructed. The correctness of the algorithm is based on a new result generalizing the Burnside-Schur theorem (on permutation groups having a regular cyclic subgroup) in the class of automorphism groups of association schemes. Bibliography: 14 titles. ©2006 Springer Science+Business Media, Inc.

关键词： Automorphism accuracy class Permutation group algorithms Polynomial correctness of algorithm Association

来源：评论

学校读者我要写书评

暂无评论

A subexponential parameterized algorithm for Subset TSP on planar graphs 14

A subexponential parameterized algorithm for Subset TSP on p...

引用

Annual ACM-SIAM Symposium on Discrete algorithms

作者： Philip N. Klein Daniel Marx Brown University Providence Rhode Island Hungarian Academy of Sciences (MTA SZTAKI) Budapest Hungary

ISBN: (纸本)9781611973389

Given a graph G and a subset S of vertices, the Subset TSP problem asks for a shortest closed walk in G visiting all vertices of S. The problem can be solved in time 2~k·n~(O(1)) using the classical dynamic programming algorithms of Bellman and of Held and Karp, where k = |S| and n =|V (G)|. Our main result is showing that the problem can be solved in time (2~O(k~(1/2) log k) +W) · n~(O(1)) if G is a planar graph with weights that are integers no greater than W. While similar speedups have been observed for various paramterized problems on planar graphs, our result cannot be simply obtained as a consequence of bounding the tree-width of G or invoking bidimensionality theory. Our algorithm consists of two steps: (1) find a locally optimal solution, and (2) use it to guide a dynamic program. The proof of correctness of the algorithm depends on a treewidth bound on a graph obtained by combining an optimal solution with a locally optimal solution.

关键词： optimal solution planning drawings algorithms Subset Proof of correctness correctness of algorithm Planar Sulfur vertex head parameterization

来源：评论

学校读者我要写书评

暂无评论

An approximate calculation for error spectrum

An approximate calculation for error spectrum

引用

International Conference on Estimation, Detection and Information Fusion (ICEDIF)

作者： Weishi Peng Yangwang Fang Shaohua Chen School of Aeronautics and Astronautics Engineering Air Force Engineering University Xi'an Shaanxi China

ISBN: (纸本)9781479964192

As a comprehensive measure, the error spectrum will be widely used for estimation performance evaluation. However, it's hard to calculate without the error distribution. An approximate algorithm is proposed in this study to solve this problem. Then, how the approximate calculation can be used is illustrated by numerical examples. Finally, the correctness of the algorithm is validated by the simulation results.

关键词： approximate algorithm error spectrum estimation performance evaluation the law of large numbers Approximate computation error distribution Spectra correctness of algorithm

来源：评论

学校读者我要写书评

暂无评论

TRIANGULAR-PRISM-BASED algorithm ON URBAN FLOOD INUNDATION SIMULATION BY EMPLOYING DICHOTOMY NUMERICAL SOLUTION

TRIANGULAR-PRISM-BASED ALGORITHM ON URBAN FLOOD INUNDATION S...

引用

IEEE International Geoscience and Remote Sensing Symposium

作者： Zhifeng Li Lixin Wu Zhenxin Zhang Zhihua Xu Zhi Wang Key Laboratory of Environment Change and Natural Disaster Beijing Normal University College of Geoscience and Surveying Engineering China University of Mining and Technology Academy of Disaster Reduction and Emergency Management Beijing Normal University

ISBN: (纸本)9781479911127

Triangular Irregular Network (TIN), especially Constrained Delaunay Triangular Irregular Network (CD-TIN), has been proven to be more accurate for the modeling of complex urban terrain, compared with raster represented digital elevation model (DEM). DEM with high precision is of importance to simulate urban flood inundation. In the paper, the triangular-prism sets are introduced to calculate the inundation water surface within each basin. It is worth mentioning that the explored dichotomy numerical solution is efficient on the simulation of the inundation depth. The case of ramp-shape urban terrain validates the correctness of the algorithm. And the application of the "7.21" storm in main campus of Beijing Normal University (BNU) verifies the usability and practicality of the algorithm. The cases demonstrate the feasibility of the proposed algorithm for simulation of urban flood inundation associated with urban surface runoff and drainage system capacity information.

关键词： Triangular-prism Dichotomy numerical solution Urban flood Inundation simulation CD-TIN Urban Flooding Flood simulating algorithms NUMERICAL SOLUTION scramble network correctness of algorithm Raster processing

来源：评论

学校读者我要写书评

暂无评论

Research of GNSS real-time pseudorange differential positioning technology

Research of GNSS real-time pseudorange differential position...

引用

International Conference on Cyberspace Technology (CCT 2013)

作者： Nie Jianhui Qi Jianzhong Song Peng College of Information Engineering North China University of Technology Beijing China

ISBN: (纸本)9781632660015

In the thesis, two pieces of tn-mode navigation receiver board are respectively used as base station and mobile station, communicate through RS232 serial port, which can form a difference positioning system. By analyzing principle of pseudorange differential positioning and the methods of RTCM encoding and decoding, to make them implementation respectively in DSP of the base station and mobile receivers. The experimental results show that accuracy can be doubled by pseudorange differential positioning. It fully verifies correctness of the algorithm and provides a basis for further study.

关键词： RTCM SC-104 positioning accuracy pseudorange difference positioning accuracy differential positioning BASE STATION correctness of algorithm mobile station Digital signal processing Desmoplakin Gene Global Navigation Satellite System accuracy class DECODING

来源：评论

学校读者我要写书评

暂无评论

Research on multilevel security access control policy processing method

Research on multilevel security access control policy proces...

引用

ICINS 2014 - 2014 International Conference on Information and Network Security

作者： Junshe Wang Shengjuan Liu Hongbin Zhang Jiang Chang School of Information Science & Engineering Hebei University of Science and Technology Shijiazhuang 050018 China

ISBN: (纸本)9781510804289

Access control is one of the most important means to protect the resources of multilevel security systems. So to make sure the authorization of multilevel security access control can be legally enforced, the access control policies must be correct and complete. Based on the implicit hierarchical relations between subjects and objects in multilevel security access control systems, this paper gives a method to build a unified directed acyclic graph(DAG) model (including both subjects and objects), using the partial orders based on sets. This method is easier to realize and is more utility for designing the access control model. Also based on partially ordered set, this paper proposes the algorithms for detecting policy conflicts and incomplete policies, which is embedding in the process of building DAG model. In the end, this paper verifies the correctness of the algorithm by experiment.

关键词： Multilevel security access control conflict detection directed acyclic graph access control conflict detection Directed Acyclic Graph multilayers Policies control strategy correctness of algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：