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

PROBABILISTIC CLOCK SYNCHRONIZATION IN DISTRIBUTED SYSTEMS

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1994年第5期5卷 474-487页

作者： ARVIND, K Digital Equipment Corporation Littleton MA USA

This paper presents and analyzes a new probabilistic clock synchronization algorithm that can guarantee a much smaller bound on the clock skew than most existing algorithms. The algorithm is probabilistic in the sense that the bound on the clock skew that it guarantees has a probability of invalidity associated with it. However, the probability of invalidity may be made extremely small by transmitting a sufficient number of synchronization messages. It is shown that an upper bound on the probability of invalidity decreases exponentially with the number of synchronization messages transmitted. A closed-form expression that relates the probability of invalidity to the clock skew and the number of synchronization messages is also derived.

关键词： CLOCK SYNCHRONIZATION deterministic algorithm DISTRIBUTED SYSTEMS MASTER-SLAVE SCHEME PROBABILISTIC algorithm PROBABILITY OF INVALIDITY TIME TRANSMISSION PROTOCOL

来源：评论

学校读者我要写书评

暂无评论

Anonymous Meeting in Networks

引用

algorithmICA 2016年第2期74卷 908-946页

作者： Dieudonne, Yoann Pelc, Andrzej Univ Picardie Jules Verne Amiens MIS Amiens France Univ Quebec Outaouais Dept Informat Gatineau PQ J8X 3X7 Canada

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, possibly at different times, have to meet at the same node. Agents are anonymous (identical), execute the same deterministic algorithm and move in synchronous rounds along links of the network. An initial configuration of agents is called gatherable if there exists a deterministic algorithm (even dedicated to this particular configuration) that achieves meeting of all agents in one node. Which configurations are gatherable and how to gather all of them deterministically by the same algorithm? We give a complete solution of this gathering problem in arbitrary networks. We characterize all gatherable configurations and give two universal deterministic gathering algorithms, i.e., algorithms that gather all gatherable configurations. The first algorithm works under the assumption that a common upper bound on the size of the network is known to all agents. In this case our algorithm guarantees gathering with detection, i.e., the existence of a round for any gatherable configuration, such that all agents are at the same node and all declare that gathering is accomplished. If no upper bound on the size of the network is known, we show that a universal algorithm for gathering with detection does not exist. Hence, for this harder scenario, we construct a second universal gathering algorithm, which guarantees that, for any gatherable configuration, all agents eventually get to one node and stop, although they cannot tell if gathering is over. The time of the first algorithm is polynomial in the upper bound on the size of the network, and the time of the second algorithm is polynomial in the (unknown) size itself. Our results have an important consequence for the leader election problem for anonymous agents in arbitrary graphs. Leader election is a fundamental symmetry breaking problem in distributed computing. Its goal is to assign, in some common round, value 1 (lead

关键词： Gathering deterministic algorithm Anonymous mobile agent

来源：评论

学校读者我要写书评

暂无评论

On the complexity of computing quadrature formulas for marginal distributions of SDEs

引用

JOURNAL OF COMPLEXITY 2015年第1期31卷 110-145页

作者： Mueller-Gronbach, Thomas Ritter, Klaus Yaroslavtseva, Larisa Univ Passau Fak Informat & Math D-94032 Passau Germany Tech Univ Kaiserslautern Fachbereich Math D-67653 Kaiserslautern Germany

We study the problem of approximating the distribution of the solution of a d-dimensional system of stochastic differential equations (SDEs) at a single time point by a probability measure with finite support, i.e., by a quadrature formula with positive weights summing up to one. We consider deterministic algorithms that may use finitely many evaluations of the drift coefficient and the diffusion coefficient and we analyze their worst case behavior with respect to classes of SDEs, which are specified in terms of smoothness constraints for the coefficients of the equation. The worst case error of an algorithm is defined in terms of a metric on the space of probability measures on the state space of the solution, which is induced by a class of test functions f: R-d -> R. For the definition of the worst case cost of an algorithm we either consider the size of the support of the approximating probability measure or the number of evaluations of the coefficients of the equation or the total computational cost within the real number model without pricing precomputation. We show that the order of convergence of the corresponding minimal errors is rid, min(s(1), s(2))/d and min(r, s(1), s(2))/d, respectively, up to an arbitrarily small power, where the parameters r, s(1) and s(2) denote the smoothness of the test functions, the drift coefficients and the diffusion coefficients, respectively. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Quadrature of SDEs Quantization of SDEs Worst case analysis Lower bounds Optimal algorithm deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

Byzantine gathering in networks

引用

DISTRIBUTED COMPUTING 2016年第6期29卷 435-457页

作者： Bouchard, Sebastien Dieudonne, Yoann Ducourthial, Bertrand UPMC Sorbonne Univ INRIA LIP6 Regal Paris France Univ Picardie Jules Verne MIS Amiens France CNRS Heudiasyc Compiegne France Univ Technol Compiegne Compiegne France

This paper investigates an open problem introduced in Dieudonn, et al. (ACM Trans algorithms 11(1):1, 2014). Two or more mobile agents start from nodes of a network and have to accomplish the task of gathering which consists in getting all together at the same node at the same time. An adversary chooses the initial nodes of the agents and assigns a different positive integer (called label) to each of them. Initially, each agent knows its label but does not know the labels of the other agents or their positions relative to its own. Agents move in synchronous rounds and can communicate with each other only when located at the same node. Up to f of the agents are Byzantine. A Byzantine agent can choose an arbitrary port when it moves, can convey arbitrary information to other agents and can change its label in every round, in particular by forging the label of another agent or by creating a completely new one. What is the minimum number of good agents that guarantees deterministic gathering of all of them, with termination? We provide exact answers to this open problem by considering the case when the agents initially know the size of the network and the case when they do not. In the former case, we prove while in the latter, we prove . More precisely, for networks of known size, we design a deterministic algorithm gathering all good agents in any network provided that the number of good agents is at least . For networks of unknown size, we also design a deterministic algorithm ensuring the gathering of all good agents in any network but provided that the number of good agents is at least . Both of our algorithms are optimal in terms of required number of good agents, as each of them perfectly matches the respective lower bound on shown in Dieudonn, et al. (2014), which is of when the size of the network is known and of when it is unknown. Perhaps surprisingly, our results highlight an interesting feature when put in perspective with known results concerning a relaxed

关键词： Rendezvous deterministic algorithm Mobile agent Byzantine fault

来源：评论

学校读者我要写书评

暂无评论

High-performance binary and non-binary Low-density parity-check codes based on affine permutation matrices

引用

IET COMMUNICATIONS 2015年第17期9卷 2114-2123页

作者： Gholami, Mohammad Alinia, Masoumeh Inst Res Fundamental Sci IPM Sch Math Tehran Iran Shahrekord Univ Dept Math Shahrekord 115 Iran

Low-density parity-check (LDPC) codes from affine permutation matrices, called APM-LDPC codes, are a class of LDPC codes whose parity-check matrices consist of zero matrices or APMs of the same orders. APM-LDPC codes are not quasi-cyclic (QC), in general. In this study, necessary and sufficient conditions are provided for an APM-LDPC code to have cycles of length 2l, l 2, and a deterministic algorithm is given to generate APM-LDPC codes with a given girth. Unlike Type-I conventional QC-LDPC codes, the constructed (J, L) APM-LDPC codes with the J x L all-one base matrix can achieve minimum distance greater than (J + 1)! and girth larger than 12. Moreover, the lengths of the constructed APM-LDPC codes, in some cases, are smaller than the best known lengths reported for QC-LDPC codes with the same base matrices. Another significant advantage of the constructed APM-LDPC codes is that they have remarkably fewer cycle multiplicities compared with QC-LDPC codes with the same base matrices and the same lengths. Simulation results show that the binary and non-binary constructed APM-LDPC codes with lower girth outperform QC-LDPC codes with larger girth.

关键词： binary codes parity check codes matrix algebra deterministic algorithms cyclic codes high-performance binary low density parity check code high-performance nonbinary low density parity check code affine permutation matrix APM-LDPC base code deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

A multi-start central force optimization for global optimization

引用

APPLIED SOFT COMPUTING 2015年 27卷 92-98页

作者： Liu, Yong Tian, Peng Shanghai Jiao Tong Univ Antai Coll Econ & Management Shanghai 200052 Peoples R China Yancheng Inst Technol Dept Fundamental Sci Yancheng 224051 Jiangsu Peoples R China

Central force optimization (CFO) is an efficient and powerful population-based intelligence algorithm for optimization problems. CFO is deterministic in nature, unlike the most widely used metaheuristics. CFO, however, is not completely free from the problems of premature convergence. One way to overcome local optimality is to utilize the multi-start strategy. By combining the respective advantages of CFO and the multi-start strategy, a multi-start central force optimization (MCFO) algorithm is proposed in this paper. The performance of the MCFO approach is evaluated on a comprehensive set of benchmark functions. The experimental results demonstrate that MCFO not only saves the computational cost, but also performs better than some state-of-the-art CFO algorithms. MCFO is also compared with representative evolutionary algorithms. The results show that MCFO is highly competitive, achieving promising performance. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Central force optimization deterministic algorithm Multi-start strategy Global optimization

来源：评论

学校读者我要写书评

暂无评论

Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields

引用

algorithmICA 2018年第2期80卷 560-575页

作者： Ivanyos, Gabor Karpinski, Marek Santha, Miklos Saxena, Nitin Shparlinski, Igor E. Hungarian Acad Sci Inst Comp Sci & Control H-1111 Budapest Hungary Univ Bonn Dept Comp Sci D-53113 Bonn Germany Univ Paris Diderot CNRS F-75013 Paris France Natl Univ Singapore CQT Singapore 117543 Singapore Indian Inst Technol Dept Comp Sci & Engn Kanpur 208016 Uttar Pradesh India Univ New South Wales Dept Pure Math Sydney NSW 2052 Australia

We consider the problem of recovering (that is, interpolating) and identity testing of a "hidden" monic polynomial f, given an oracle access to for , where is finite field of q elements (extension fields access is not permitted). The naive interpolation algorithm needs queries and thus requires . We design algorithms that are asymptotically better in certain cases;requiring only queries to the oracle. In the randomized (and quantum) setting, we give a substantially better interpolation algorithm, that requires only queries. Such results have been known before only for the special case of a linear f, called the hidden shifted power problem. We use techniques from algebra, such as effective versions of Hilbert's Nullstellensatz, and analytic number theory, such as results on the distribution of rational functions in subgroups and character sum estimates.

关键词： Hidden polynomial power Black-box interpolation Nullstellensatz Rational function deterministic algorithm Randomised algorithm Quantum algorithm

来源：评论

学校读者我要写书评

暂无评论

A divide-and-conquer approach to the minimum k-way cut problem

引用

algorithmICA 2002年第2期32卷 262-276页

作者： Kamidoi, Y Wakabayashi, S Yoshida, N Hiroshima City Univ Fac Informat Sci Asaminami Ku Hiroshima 7313194 Japan Hiroshima Univ Grad Sch Engn Higashihiroshima 7398597 Japan

This paper presents algorithms for computing a minimum 3-way cut and a minimum 4-way cut of an undirected weighted graph G. Let G = (V, E) bean undirected graph with n vertices, m edges, and positive edge weights. Goldschmidt and Hochbaum presented an algorithm for the minimum k-way cut problem with fixed k, that requires O (n(4)) and O (n(6)) maximum flow computations, respectively, to compute a minimum 3-way cut and a minimum 4-way cut of G. In this paper we first show some properties on minimum 3-way cuts and minimum 4-way cuts, which indicate a recursive structure of the minimum k-way cut problem when k = 3 and 4. Then, based on those properties, we give divide-and-conquer algorithms for computing a minimum 3-way cut and a minimum 4-way cut of G, which require O(n(3)) and O(n(4)) maximum flow computations, respectively.

关键词： deterministic algorithm minimum k-way cut maximum flow computation undirected weighted graph recursive structure

来源：评论

学校读者我要写书评

暂无评论

Product range spaces, sensitive sampling, and derandomization

引用

SIAM JOURNAL ON COMPUTING 1999年第5期28卷 1552-1575页

作者： Brönnimann, H Chazelle, B Matousek, J INRIA Sophia Antipolis F-06902 Sophia Antipolis France Princeton Univ Dept Comp Sci Princeton NJ 08544 USA Charles Univ Dept Appl Math CR-11800 Prague Czech Republic

We introduce the concept of a sensitive epsilon-approximation and use it to derive a more efficient algorithm for computing epsilon-nets. We define and investigate product range spaces, for which we establish sampling theorems analogous to the standard finite VC-dimensional case. This generalizes and simplifies results from previous works. Using these tools, we give a new deterministic algorithm for computing the convex hull of n points in R-d. The algorithm is obtained by derandomization of a randomized incremental algorithm, and its running time of O(n log n + n(right perpendicular d/2 left perpendicular)) is optimal for any fixed dimension d greater than or equal to 2.

关键词： convex hull deterministic algorithm optimal

来源：评论

学校读者我要写书评

暂无评论

Identity testing and interpolation from high powers of polynomials of large degree over finite fields

引用

JOURNAL OF COMPLEXITY 2018年第Dec.期49卷 74-84页

作者： Karpinski, Marek Merai, Laszlo Shparlinski, Igor E. Univ Bonn Dept Comp Sci D-53113 Bonn Germany Johannes Kepler Univ Linz Austrian Acad Sci Johann Radon Inst Computat & Appl Math Altenberger Str 69 A-4040 Linz Austria Johannes Kepler Univ Linz Inst Financial Math & Appl Number Theory Altenberger Str 69 A-4040 Linz Austria Univ New South Wales Dept Pure Math Sydney NSW 2052 Australia

We consider the problem of identity testing and recovering (that is, interpolating) of a "hidden" monic polynomial f, given an oracle access to f(x)(e) for x is an element of F-q, where F-q is the finite field of q elements and queries with x from an extension field are not permitted. The naive interpolation algorithm needs de + 1 queries, where d = degf and thus requires de < q. For a prime q = p, we design algorithms that are asymptotically better in certain cases, especially when d is large. These algorithms are based on some new results in the spirit of additive combinatorics. In particular, we give an upper bound on the number of values of a rational function of large degree, evaluated on a short sequence of consecutive integers, that belong to a small subgroup of F-p*. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Hidden polynomial High powers of polynomials Black-box interpolation deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：