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

Rendezvous in networks in spite of delay faults

DISTRIBUTED COMPUTING 2016年第3期29卷 187-205页

作者： Chalopin, Jeromie Dieudonne, Yoann Labourel, Arnaud Pelc, Andrzej CNRS LIF Marseille France Aix Marseille Univ Marseille France Univ Picardie Jules Verne Amiens MIS Amiens France Univ Quebec Outaouais Dept Informat Gatineau PQ J8X 3X7 Canada

Two mobile agents, starting from different nodes of an unknown network, have to meet at a node. Agents move in synchronous rounds using a deterministic algorithm. Each agent has a different label, which it can use in the execution of the algorithm, but it does not know the label of the other agent. Agents do not know any bound on the size of the network. In each round an agent decides if it remains idle or if it wants to move to one of the adjacent nodes. Agents are subject to delay faults: if an agent incurs a fault in a given round, it remains in the current node, regardless of its decision. If it planned to move and the fault happened, the agent is aware of it. We consider three scenarios of fault distribution: random ( independently in each round and for each agent with constant probability 0 < p < 1), unbounded adversarial ( the adversary can delay an agent for an arbitrary finite number of consecutive rounds) and bounded adversarial ( the adversary can delay an agent for at most c consecutive rounds, where c is unknown to the agents). The quality measure of a rendezvous algorithm is its cost, which is the total number of edge traversals. For random faults, we show an algorithm with cost polynomial in the size n of the network and polylogarithmic in the larger label L, which achieves rendezvous with very high probability in arbitrary networks. By contrast, for unbounded adversarial faults we show that rendezvous is not possible, even in the class of rings. Under this scenario we give a rendezvous algorithm with cost O(nl), where l is the smaller label, working in arbitrary trees, and we show that Omega(l) is the lower bound on rendezvous cost, even for the two-node tree. For bounded adversarial faults, we give a rendezvous algorithm working for arbitrary networks, with cost polynomial in n, and logarithmic in the bound c and in the larger label L.

关键词： Rendezvous deterministic algorithm Mobile agent Delay fault

来源：评论

学校读者我要写书评

暂无评论

Factoring polynomials over arbitrary finite fields

引用

THEORETICAL COMPUTER SCIENCE 2000年第1-2期234卷 301-308页

作者： Lange, T Winterhof, A Tech Univ Braunschweig Inst Algebra & Zahlentheorie D-38106 Braunschweig Germany

We analyse an extension of Shoup's (Inform. Process. Lett. 33 (1990) 261-267) deterministic algorithm for factoring polynomials over finite prime fields to arbitrary finite fields. In particular, we prove the existence of a deterministic algorithm which completely factors all monic polynomials of degree n over F-q, q odd, except possibly O(n(2) log(2) q/q) polynomials, using O(n(2+epsilon) log(2)q) arithmetical operations in F-q. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： factorisation of polynomials arbitrary finite fields deterministic algorithm average case analysis

来源：评论

学校读者我要写书评

暂无评论

LOCAL FLOW PARTITIONING FOR FASTER EDGE CONNECTIVITY

引用

SIAM JOURNAL ON COMPUTING 2020年第1期49卷 1-36页

作者： Henzinger, Monika Rao, Satish Wang, Di Univ Vienna A-1090 Vienna Austria Univ Calif Berkeley Comp Sci Div Berkeley CA 94720 USA Georgia Inst Technol Atlanta GA 30332 USA

We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic O(m log(2) n log log(2) n) time algorithm. This improves on both the best previously known deterministic running time of O(m log(12) n) (Kawarabayashi and Thorup [J. ACM, 66 (2018), 41) and the best previously known randomized running time of O(m log(3) n) (Karger [J. ACM, 47 (2000), pp. 46-761) for this problem, though Karger's algorithm can be further applied to weighted graphs. Moreover, our result extends to balanced directed graphs, where the balance of a directed graph captures how close the graph is to being Eulerian. Our approach is using the Kawarabayashi and Thorup graph compression technique, which repeatedly finds low conductance cuts. To find these cuts they use a diffusion-based local algorithm. We use instead a flow-based local algorithm and suitably adjust their framework to work with our flow-based subroutine. Both flow-and diffusion-based methods have a long history of being applied to finding low conductance cuts. Diffusion algorithms have several variants that are naturally local, while it is more complicated to make flow methods local. Some prior work has proven nice properties for local flow-based algorithms with respect to improving or cleaning up low conductance cuts. Our flow subroutine, however, is the first that both is local and produces low conductance cuts. Thus, it may be of independent interest.

关键词： min cut graph algorithm deterministic algorithm flow edge connectivity local algorithm

来源：评论

学校读者我要写书评

暂无评论

Weakly Byzantine Gathering with a Strong Team

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2022年第3期E105D卷 541-555页

作者： Hirose, Jion Nakamura, Junya Ooshita, Fukuhito Inoue, Michiko Nara Inst Sci & Technol Ikoma 6300192 Japan Toyohashi Univ Technol Toyohashi Aichi 4418580 Japan

We study the gathering problem requiring a team of mobile agents to gather at a single node in arbitrary networks. The team consists of k agents with unique identifiers (IDs), and f of them are weakly Byzantine agents, which behave arbitrarily except falsifying their identifiers. The agents move in synchronous rounds and cannot leave any information on nodes. If the number of nodes n is given to agents, the existing fastest algorithm tolerates any number of weakly Byzantine agents and achieves gathering with simultaneous termination in O(n(4). vertical bar Lambda(good)vertical bar . X(n)) rounds, where vertical bar Lambda(good)vertical bar is the length of the maximum ID of non-Byzantine agents and X(n) is the number of rounds required to explore any network composed of n nodes. In this paper, we ask the question of whether we can reduce the time complexity if we have a strong team, i.e., a team with a few Byzantine agents, because not so many agents are subject to faults in practice. We give a positive answer to this question by proposing two algorithms in the case where at least 4f(2) + 9f + 4 agents exist. Both the algorithms assume that the upper bound N of n is given to agents. The first algorithm achieves gathering with non-simultaneous termination in O((f + vertical bar Lambda(good)vertical bar) . X(N)) rounds. The second algorithm achieves gathering with simultaneous termination in O((f + vertical bar Lambda(all)vertical bar) . X(N)) rounds, where vertical bar Lambda(all)vertical bar is the length of the maximum ID of all agents. The second algorithm significantly reduces the time complexity compared to the existing one if n is given to agents and vertical bar Lambda(all)vertical bar = O(vertical bar Lambda(good)vertical bar) holds.

关键词： distributed algorithm deterministic algorithm mobile agents gathering Byzantine faults

来源：评论

学校读者我要写书评

暂无评论

Stochastic Distance Transform: Theory, algorithms and Applications

引用

JOURNAL OF MATHEMATICAL IMAGING AND VISION 2020年第5期62卷 751-769页

作者： Ofverstedt, Johan Lindblad, Joakim Sladoje, Natasa Uppsala Univ Dept Informat Technol Lagerhyddsvagen 2Box 337 S-75105 Uppsala Sweden

Distance transforms (DTs) are standard tools in image analysis, with applications in image registration and segmentation. The DT is based on extremal (minimal) distance values and is therefore highly sensitive to noise. We present astochastic distance transform(SDT) based ondiscrete random sets, in which a model of element-wise probability is utilized and the SDT is computed as the first moment of the distance distribution to the random set. We present two methods for computing the SDT and analyze them w.r.t. accuracy and complexity. Further, we propose a method, utilizing kernel density estimation, for estimating probability functions and associated random sets to use with the SDT. We evaluate the accuracy of the SDT and the proposed framework on images of thin line structures and disks corrupted by salt and pepper noise and observe excellent performance. We also insert the SDT into a segmentation framework and apply it to overlapping objects, where it provides substantially improved performance over previous methods. Finally, we evaluate the SDT and observe very good performance, on simulated images from localization microscopy, a state-of-the-art super-resolution microscopy technique which yields highly spatially localized but noisy point-clouds.

关键词： Distance transform Discrete random set Robust distance Image segmentation deterministic algorithm Monte-Carlo method

来源：评论

学校读者我要写书评

暂无评论

Fast computation of robust subspace estimators

引用

COMPUTATIONAL STATISTICS & DATA ANALYSIS 2019年 134卷 171-185页

作者： Cevallos-Valdiviezo, Holger Van Aelst, Stefan ESPOL Polytech Univ Escuela Super Politecn Litoral ESPOL FCNM Campus Gustavo Galindo Km 30-5 Via Perimetral Guayaquil Ecuador Univ Ghent Dept Appl Math Comp Sci & Stat Krijgslaan 281 S9 B-9000 Ghent Belgium Katholieke Univ Leuven Dept Math Celestijnenlaan 200B B-3001 Leuven Belgium

Dimension reduction is often an important step in the analysis of high-dimensional data. PCA is a popular technique to find the best low-dimensional approximation of high dimensional data. However, classical PCA is very sensitive to atypical data. Robust methods to estimate the low-dimensional subspace that best approximates the regular data have been proposed. However, for high-dimensional data these algorithms become computationally expensive. Alternative algorithms for the robust subspace estimators are proposed that are better suited to compute the solution for high-dimensional problems. The main ingredients of the new algorithms are twofold. First, the principal directions of the subspace are estimated directly by iterating the first order solutions corresponding to the estimators. Second, to reduce the computation time even further five robust deterministic values are proposed to initialize the algorithms instead of using random starting values. It is shown that the new algorithms yield robust solutions and the computation time is largely reduced, especially for high-dimensional data. (C) 2019 Elsevier B.V. All rights reserved.

关键词： deterministic algorithm High-dimensional data Least trimmed squares M-scale Principal component analysis

来源：评论

学校读者我要写书评

暂无评论

Price of asynchrony in mobile agents computing

引用

THEORETICAL COMPUTER SCIENCE 2014年第0期524卷 59-67页

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

Asynchrony is one of the main challenges in distributed computing. Some tasks, such as distributed Byzantine consensus, are impossible in the asynchronous setting, while they can be carried out synchronously. For other tasks, such as rendezvous in arbitrary graphs, the best known synchronous algorithm has cost much lower than the best asynchronous one. Various degrees of asynchrony and synchrony and comparisons between them in terms of feasibility of distributed tasks have been particularly intensely studied in the context of mobile agents computing. However, somewhat surprisingly, there are no results showing a provable difference of cost between the synchronous and asynchronous versions of a task executed by mobile agents. The aim of this paper is to fill up this gap. We show for the first time that for some natural task executed by mobile agents in a network, the optimal cost of its deterministic solution in the asynchronous setting has higher order of magnitude than that in the synchronous scenario. The task for which we show this difference is well-studied: that of rendezvous of two agents in an infinite oriented grid. More precisely, we consider two agents with distinct integer labels starting at a distance D in the infinite oriented grid. Each agent knows D and its own label but not the label of the other agent and it does not know the position of the other agent relative to its own. Agents do not have any global system of coordinates. They have to meet in a node or inside an edge of the grid, and the cost of a rendezvous algorithm is the number of edge traversals by both agents until the meeting. We show that in the synchronous scenario rendezvous can be performed at cost O (Dl), where E is the length of the (binary representation of the) smaller label, while cost Omega(D-2 + D(l) is needed for asynchronous completion of rendezvous. Hence, for instances with l = o(D), the optimal cost of asynchronous rendezvous is asymptotically larger than that of synchrono

关键词： Asynchronous Synchronous Mobile agent Network Rendezvous deterministic algorithm Cost

来源：评论

学校读者我要写书评

暂无评论

Lightning: A High-Efficient Neighbor Discovery Protocol for Low Duty Cycle WSNs

引用

IEEE COMMUNICATIONS LETTERS 2016年第5期20卷 966-969页

作者： Wei, Liangxiong Zhou, Beisi Ma, Xichu Chen, Dexin Zhang, Jingyu Peng, Jian Luo, Qian Sun, Limin Li, Dingcheng Chen, Liangyin Sichuan Univ Sch Comp Sci Chengdu 610225 Peoples R China Gen Adm Civil Aviat China Res Inst 2 Chengdu 610042 Peoples R China Chinese Acad Sci Inst Informat Engn Beijing 100864 Peoples R China Mayo Clin Div Biomed Stat & Informat Rochester MN 55901 USA

In wireless sensor networks (WSNs), due to the limited energy of nodes, discovering neighbors needs to be achieved in an energy-efficient way. This means that, at a given energy consumption, we need to reduce the worst-case neighbor discovery latency as far as possible. In this letter, we propose a novel deterministic neighbor discovery method, called Lightning. Lightning employs two kinds of active slots of different active lengths (we call A slot and C slot, respectively). The active time of C slot is much shorter than that of A slot in order to reduce the energy consumption. In addition, to maximize the energy efficiency, Lightning adopts one-way neighbor discovery method. This makes C slot have the smallest active length that is only enough to send one beaconing packet. Through proactively sending one beaconing packet after one-way discovery, Lightning also realizes bi-directional neighbor discovery. The theoretical analysis indicates that, with the same energy consumption, our method reduces the worst-case latency bound up to 37.9% compared with Searchlight-Trim, the best existing discovery algorithm. The simulation verifies the soundness and effectiveness of our design.

关键词： Low Duty Cycle WSNs Neighbor Discovery deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

Thermal analysis of tubular arrangements submitted to external flow using constructal theory

引用

INTERNATIONAL COMMUNICATIONS IN HEAT AND MASS TRANSFER 2020年 111卷 104458-104458页

作者： Pedroti, V. A. de Escobar, C. C. dos Santos, E. D. Souza, J. A. Univ Fed Rio Grande FURL Grad Program Computat Modeling Italia AveKm 8 BR-96201900 Rio Grande RS Brazil

Present work performs a numerical study about the energy removal in a heated tubular array submitted to an external flow. Taking into account that a large variety of tubular arrangements can exists, in this work it is developed a tubular array that does not use any kind of initial predefined arrangement. Using the principles of Constructal Theory (or Law) and a positioning function dependent on the velocity and temperature fields, it is calculated, in a deterministic way, the location where each tube should be positioned. Pressure drop is not taken in to account in this first algorithm implementation as a performance indicator. In order to validate the proposed methodology, the Constructal Array is compared with standard aligned and staggered arrangements suggested in literature. The minimum distance between tubes (p) is considered as a degree of freedom. Four variations are studied: p = 1D, p = 1.25D, p = 1.5D and p = 2D, where D is the tube diameter. It is considered here the simulation of a transient, incompressible and laminar flow of a Newtonian fluid in a two-dimensional domain with forced convection and Prandtl number equal to 0.71. Results are computed when the flow reaches to the steady state condition. It is evaluated three values for Reynolds number: Re-D = 10, 50 and 100. Thermal analysis of the formed patterns has shown that best thermal performance was not obtained with p = 1D, neither with p = 2D, i.e., tube distance has an influence on its formation and, consequently, on the heat transfer exchange. In all performed analyzes, Constructal arrays configuration showed higher energy removal (up to 71%) than the aligned and staggered arrangements, which highlights the capacity of proposed method. Constructal Array for p = 1.5D showed the most homogeneous distribution and proved to be the most effective in 4 of the six studied cases.

关键词： deterministic algorithm Tube heat exchanger Numerical Modeling Constructal Theory

来源：评论

学校读者我要写书评

暂无评论

Scalable wake-up of multi-channel single-hop radio networks

引用

THEORETICAL COMPUTER SCIENCE 2016年 615卷 23-44页

作者： Chlebus, Bogdan S. De Marco, Gianluca Kowalski, Dariusz R. Univ Colorado Dept Comp Sci & Engn Denver CO 80217 USA Univ Salerno Dipartimento Informat I-84084 Salerno Italy Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England

We consider single-hop radio networks with multiple channels as a model of wireless networks. There are n stations connected to b radio channels that do not provide collision detection. A station uses all the channels concurrently and independently. Some k stations may become active spontaneously at arbitrary times. The goal is to wake up the network, which occurs when all the stations hear a successful transmission on some channel. Duration of a waking-up execution is measured starting from the first spontaneous activation. We present a deterministic algorithm that wakes up a network in O(k log(1/b) k log n) time, where k is unknown. We give a deterministic scalable algorithm for the special case when b > d log log n, for some constant d > 1, which wakes up a network in O(k/b log n log(b log n)) time, with k unknown. This algorithm misses time optimality by at most a factor of O(log n(log b + log log n)), because any deterministic algorithm requires Omega(k/b log n/k) time. We give a randomized algorithm that wakes up a network within O(k(1/b) In 1/epsilon) rounds with a probability that is at least 1 - epsilon, for any 0 < epsilon < 1, where k is known. We also consider a model of jamming, in which each channel in any round may be jammed to prevent a successful transmission, which happens with some known parameter probability p, independently across all channels and rounds. For this model, we give two deterministic algorithms for unknown k: one wakes up a network in time O(log(-1) (1/p) log n log(1/b) k), and the other in time O(log(-1) (1/p) k/b log n log(b log n)) when the inequality b > log(128b log n) holds, both with probabilities that are at least 1 - 1/poly(n). (c) 2015 Elsevier B.V. All rights reserved.

关键词： Multiple access channel Radio network Multi-channel Wake-up Synchronization deterministic algorithm Randomized algorithm Distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：