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

2013 2nd International Symposium on Computer,Communication,Control and Automation(3CA 2013)

作者： Ilja Kucevalovs Kaspars Balodis Rūsi?? Freivalds Institute of Mathematics and Computer Science University of Latvia

ISBN: (纸本)9781629939773

We investigate properties of an identification type of recursive functions, called co-learning. The inductive process refutes all possible programs but one, and, by definition, this program is demanded to be correct. This type of identification was introduced in [6]. M. Kummer in the paper [9] showed that this type characterizes computable numberings possessing a certain property thus answering a long standing open problem by Yu. L. Ershov [2]. We consider probabilistic algorithms of co-learning and establish an infinite discrete hierarchy of classes of recursive functions. The parameters of this new hierarchy coincide with the hierarchy by R. Freivalds [4] for probabilistic algorithms of finite identification.

关键词： inductive inference co-learning probabilistic algorithms

来源：评论

学校读者我要写书评

暂无评论

Dynamic probabilistic Reliable Broadcast 28

Dynamic Probabilistic Reliable Broadcast

引用

28th International Conference on Principles of Distributed Systems, OPODIS 2024

作者： Bezerra, João Paulo Anikina, Veronika Kuznetsov, Petr Schiff, Liron Schmid, Stefan LTCI Télécom Paris Institut Polytechnique de Paris France ITMO University St. Petersburg Russia Akamai Technologies CambridgeMA United States Technische Universität Berlin Germany

ISBN: (纸本)9783959773607

Byzantine reliable broadcast is a fundamental primitive in distributed systems that allows a set of processes to agree on a message broadcast by a dedicated process, even when some of them are malicious (Byzantine). It guarantees that no two correct processes deliver different messages, and if a message is delivered by a correct process, every correct process eventually delivers one. Byzantine reliable broadcast protocols are known to scale poorly, as they require Ω(n2) message exchanges, where n is the number of system members. The quadratic cost can be explained by the inherent need for every process to relay a message to every other process. In this paper, we explore ways to overcome this limitation by casting the problem to the probabilistic setting. We propose a solution in which every broadcast message is validated by a small set of witnesses, which allows us to maintain low latency and small communication complexity. In order to tolerate the slow adaptive adversary, we dynamically select the witnesses through a novel stream-local hash function: given a stream of inputs, it generates a stream of output hashed values that adapts to small deviations of the inputs. Our performance analysis shows that the proposed solution exhibits significant scalability gains over state-of-the-art protocols. © João Paulo Bezerra, Veronika Anikina, Petr Kuznetsov, Liron Schiff, and Stefan Schmid.

关键词： accountability cryptocurrencies probabilistic algorithms Reliable broadcast stream-local hashing witness sets

来源：评论

学校读者我要写书评

暂无评论

probabilistic system-level fault diagnostic algorithms for multiprocessors

引用

PARALLEL COMPUTING 1997年第13期22卷 1807-1821页

作者： Bartha, T Selenyi, E Department of Measurement and Instrument Engineering Technical University of Budapest Müegyetem rkp. 9R/113 H-1521 Budapest Hungary

Massively parallel computers (MPCs) introduce new requirements for system-level fault diagnosis, like handling a huge number of processing elements in a heterogeneous system. They also have specific attributes, such as regular topology and low local complexity. Traditional deterministic methods of system-level diagnosis did not consider these issues. This paper presents a new approach, called local information diagnosis that exploits the characteristics of massively parallel systems, The paper defines the diagnostic model, which is based on generalized test invalidation to handle inhomogeneity in multiprocessors. Five effective probabilistic diagnostic algorithms using the proposed method are also given, and their space and time complexity are estimated.

关键词： system-level fault diagnosis probabilistic algorithms generalized test invalidation massively parallel systems regular topology

来源：评论

学校读者我要写书评

暂无评论

PT-LRU: A probabilistic Page Replacement Algorithm for NAND Flash-based Consumer Electronics

引用

IEEE TRANSACTIONS ON CONSUMER ELECTRONICS 2014年第4期60卷 614-622页

作者： Cui, Jinhua Wu, Weiguo Wang, Yinfeng Duan, Zhangfeng Xi An Jiao Tong Univ Sch Elect & Informat Engn Xian 710049 Shaanxi Peoples R China ShenZhen Inst Informat Technol Dept Software Engn Shenzhen 518172 Guangdong Peoples R China

The flash memory is being used to an ever-increasing extent in consumer electronics for the purpose of the dominant secondary storage device. Aiming at the buffer replacement policy for flash-based storage devices in efficiency, a new efficient flash-aware buffer replacement algorithm based on probability is proposed, where three LRU linked lists are used to manage the buffer. The proposed algorithm delays the eviction of hot clean pages by evicting the cold clean pages preferentially. When the cold clean linked list is empty, the pages in the cold dirty linked list will be expelled from the buffer with a higher probability, whereas the probability of evicting the hot clean pages is lower. In that way, hot clean pages cannot reside in the buffer for a long time. Moreover, an interpretation model for describing the proposed algorithm is developed from FSM. Highlights of the experiments include an evaluation with the dynamic write/read ratio traces. Experimental results and detailed comparisons with other similar best-known competitor algorithms on the static write/read ratio traces and the dynamic write/read ratio traces show that not only does the proposed algorithm reduce the write counts, but also it offers a trade-off between the hit ratio and the overall runtime in most cases. The adaptability of the proposed method is also verified by the experiments on various kinds of traces including random, read-most, write-most and Zipf.(1)

关键词： Buffer Management probabilistic algorithms Flash Memory Consumer Electronics

来源：评论

学校读者我要写书评

暂无评论

probabilistic Analysis of Probe Reliability in Differential Gene Expression Studies with Short Oligonucleotide Arrays

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2011年第1期8卷 217-225页

作者： Lahti, Leo Elo, Laura L. Aittokallio, Tero Kaski, Samuel Aalto Univ Sch Sci & Technol Dept Informat & Comp Sci HIIT FI-00076 Aalto Finland Univ Turku Dept Math FI-20014 Turku Finland Univ Turku Turku Ctr Biotechnol FI-20521 Turku Finland

Probe defects are a major source of noise in gene expression studies. While existing approaches detect noisy probes based on external information such as genomic alignments, we introduce and validate a targeted probabilistic method for analyzing probe reliability directly from expression data and independently of the noise source. This provides insights into the various sources of probe-level noise and gives tools to guide probe design.

关键词： Applications biology and genetics parameter learning probabilistic algorithms

来源：评论

学校读者我要写书评

暂无评论

A new probabilistic Extension of Dijkstra's Algorithm to simulate more realistic traffic flow in a smart city

引用

APPLIED MATHEMATICS AND COMPUTATION 2015年 267卷 780-789页

作者： Galan-Garcia, Jose L. Aguilera-Venegas, Gabriel Galan-Garcia, Maria A. Rodriguez-Cielos, Pedro Univ Malaga Dept Appl Math E-29071 Malaga Spain

Dijkstra's algorithm to solve the shortest path problem (SPP) is a very well-known algorithm. When applied to real situations, although the shortest path can be computed with Dijkstra's algorithm, it is not always the one that is chosen. In traffic situations, for example, the driver may not know the exact length of the lanes or the shortest path to follow. Even more compelling is the fact that although the driver knows the shortest route, he/she may prefer choosing a different route. In this paper we present the new algorithm PEDA (probabilistic Extension of Dijkstra's Algorithm) which introduces probabilistic changes in the weight of the edges and also in the decisions when choosing the shortest path. When PEDA is applied to traffic flow, more realistic simulations, in which the shortest path is not always chosen, are obtained. This more accurately simulates the more normal behavior of drivers. As an example of an application, we introduce the ATISMART+ model, an extension of the ATISMART model, where an accelerated-time simulation of car traffic in a smart city was described. In that previous work, all cars in the system used Dijkstra's algorithm to choose improved ATISMART(+) model, for accelerated time simulations of traffic flow in smart cities, uses the new PEDA algorithm. The results obtained show that ATISMART+ produces more realistic simulations considering different drivers' behaviors. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Extension of Dijkstra's Algorithm Accelerated-time simulations Smart cities probabilistic algorithms

来源：评论

学校读者我要写书评

暂无评论

Implementing a probabilistic clock synchronization algorithm

引用

REAL-TIME SYSTEMS 1997年第1期13卷 25-46页

作者： Alari, G Ciuffoletti, A UNIV CATHOLIQUE LOUVAIN DEPT INGN INFORMATB-1348 LOUVAINBELGIUM UNIV PISA DIPARTIMENTO INFORMATI-56125 PISAITALY

In this paper we present a new probabilistic clock synchronization algorithm, its prototype implementation and experimental results. The algorithm follows the client-server programming paradigm and is designed to work in a departmental environment with few servers and a number of clients connected through an arbitrary network topology. At the core of the algorithm is a remote clock reading method that mitigates the negative effects of message delay uncertainty. The implementation proves the effectiveness of this approach and corroborates the theoretical speculations.

关键词： clock synchronization probabilistic algorithms distributed systems distributed algorithms local area networks TCP/IP

来源：评论

学校读者我要写书评

暂无评论

Estimating sensor population via probabilistic sequential polling

引用

IEEE SIGNAL PROCESSING LETTERS 2005年第5期12卷 395-398页

作者： Leshem, A Tong, L Bar Ilan Univ Sch Engn IL-52900 Ramat Gan Israel Cornell Univ Sch Elect & Comp Engn Ithaca NY 14853 USA

A probabilistic sequential polling protocol (PSPP) is presented for the estimation of the sensor population in a large-scale sensor network with a mobile access point. It is shown that PSPP requires O(log(2) N) sensor... 详细信息

关键词： estimation polling probabilistic algorithms sensor network with mobile access (SENMA) sensor networks

来源：评论

学校读者我要写书评

暂无评论

probabilistic methods for centroidal Voronoi tessellations and their parallel implementations

引用

PARALLEL COMPUTING 2002年第10期28卷 1477-1500页

作者： Ju, L Du, Q Gunzburger, M Iowa State Univ Sci & Technol Dept Math Ames IA 50011 USA Penn State Univ Dept Math University Pk PA 16802 USA

Centroidal Voronoi tessellations (CVTs) are Voronoi tessellations of a region such that the generating points of the tessellations are also the centroids of the corresponding Voronoi cells. In this paper, some probabilistic methods for determining CVTs and their parallel implementations on distributed memory systems are presented. By using multi-sampling in a new probabilistic algorithm we introduce, more accurate and efficient approximations of CVTs are obtained without the need to explicit construct Voronoi diagrams. The new algorithm lends itself well to parallelization, i.e., near prefect linear speed up in the number of processors is achieved. The results of computational experiments performed on a CRAY T3E-600 system are provided which illustrate the superior sequential and parallel performance of the new algorithm when compared to existing algorithms. In particular, for the same amount of work, the new algorithms produce significantly more accurate CVTs. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： centroidal Voronoi tessellations probabilistic algorithms parallel implementations rejection method

来源：评论

学校读者我要写书评

暂无评论

On probabilistic snap-stabilization

引用

THEORETICAL COMPUTER SCIENCE 2017年 688卷 49-76页

作者： Altisen, Karine Devismes, Stephane Univ Grenoble Alpes VERIMAG F-38000 Grenoble France CNRS VERIMAG F-38000 Grenoble France

In this paper, we introduce probabilistic snap-stabilization. We relax the definition of deterministic snap-stabilization without compromising its safety guarantees. In an unsafe environment, a probabilistically snap-stabilizing algorithm satisfies its safety property immediately after the last fault;whereas its liveness property is only ensured with probability 1. We show that probabilistic snap- stabilization is more expressive than its deterministic counterpart. Indeed, we propose two probabilistic snap-stabilizing algorithms for a problem having no deterministic snap- or self-stabilizing solution: guaranteed service leader election in arbitrary anonymous networks. This problem consists in computing a correct answer to each process that initiates the question "Am I the leader of the network?," i.e., (1) processes always compute the same answer to that question and (2) exactly one process computes the answer true. Our solutions being probabilistically snap-stabilizing, the answers are only delivered within an almost surely finite time;however any delivered answer is correct, regardless the arbitrary initial configuration and provided the question has been properly started. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Snap-stabilization probabilistic algorithms Leader election

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：