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

distributed COMPUTING 2021年第2期34卷 113-132页

作者： Feuilloley, Laurent Fraigniaud, Pierre Hirvonen, Juho Paz, Ami Perry, Mor Univ Chile Santiago Chile Univ Paris CNRS IRIF Paris France Aalto Univ Espoo Finland Univ Vienna Fac Comp Sci Vienna Austria Weizmann Inst Sci Rehovot Israel

distributed proofs are mechanisms that enable the nodes of a network to collectively and efficiently check the correctness of Boolean predicates on the structure of the network (e.g., having a specific diameter), or on objects distributed over the nodes (e.g., a spanning tree). We consider well known mechanisms consisting of two components: aproverthat assigns acertificateto each node, and a distributed algorithm called averifierthat is in charge of verifying the distributed proof formed by the collection of all certificates. We show that many network predicates have distributed proofs offering a high level of redundancy, explicitly or implicitly. We use this remarkable property of distributed proofs to establish perfect tradeoffs between thesize of the certificatestored at every node, and thenumber of roundsof the verification protocol.

关键词： distributed verification distributed graph algorithms Proof-labeling schemes Space-time tradeoffs Nondeterminism

来源：评论

学校读者我要写书评

暂无评论

Approximate proof-labeling schemes

引用

THEORETICAL COMPUTER SCIENCE 2020年 811卷 112-124页

作者： Censor-Hillel, Keren Paz, Ami Perry, Mor Technion Dept Comp Sci Haifa Israel CNRS IRIF Paris France Univ Paris Diderot Paris France Tel Aviv Univ Dept Elect Engn Tel Aviv Israel

We study a new model of verification of boolean predicates over distributed networks. Given a network configuration, the proof-labeling scheme (PIS) model defines a distributed proof in the form of a label that is given to each node, and all nodes locally verify that the network configuration satisfies the desired boolean predicate by exchanging labels with their neighbors. The proof size of the scheme is defined to be the maximum size of a label. In this work, we extend this model by defining the approximate proof-labeling scheme (APIS) model. In this new model, the predicates for verification are of the form psi <= phi, where psi, phi : F -> N for a family of configurations F. Informally, the predicates considered in this model are a comparison between two values of the configuration. As in the PLS model, nodes exchange labels in order to locally verify the predicate, and all must accept if the network satisfies the predicate. The soundness condition is relaxed with an approximation ration alpha, so that only psi > alpha phi) some node must reject. We focus on two verification problems: upper and lower bounds on the diameter of the graph, and the maximality of a given matching. For these problems, we present the first results that apply to all graph structures. In our new APLS model, we show that the proof size can be much smaller than the proof size of the same predicate in the PLS model. Moreover, we prove that there is a tradeoff between the approximation ratio and the proof size. Finally, we present the first general result for maximum cardinality matching in the PLS model. (C) 2018 Published by Elsevier B.V.

关键词： distributed graph algorithms distributed verification Approximation algorithms Primal-dual algorithms

来源：评论

学校读者我要写书评

暂无评论

Deciding and verifying network properties locally with few output bits

引用

distributed COMPUTING 2020年第2期33卷 169-187页

作者： Arfaoui, Heger Fraigniaud, Pierre Ilcinkas, David Mathieu, Fabien Pelc, Andrzej South Mediterranean Univ Tunis Tunisia CNRS Paris France Univ Paris Diderot Paris France CNRS Talence France Univ Bordeaux Talence France Nokia Bell Labs France Paris France Univ Quebec Outaouais Gatineau PQ Canada

Given a boolean predicate on labeled networks (e.g., the network is acyclic, or the network is properly colored, etc.), deciding in a distributed manner whether a given labeled network satisfies that predicate typically consists, in the standard setting, of every node inspecting its close neighborhood, and outputting a boolean verdict, such that the network satisfies the predicate if and only if all nodes output true. In this paper, we investigate a more general notion of distributed decision in which every node is allowed to output a constant number b >= 1 of bits, which are gathered by a central authority emitting a global boolean verdict based on these outputs, such that the network satisfies the predicate if and only if this global verdict equals true. We analyze the power and limitations of this extended notion of distributed decision.

关键词： distributed decision distributed verification Locality Network

来源：评论

学校读者我要写书评

暂无评论

Large-scale distributed verification Using CADP: Beyond Clusters to Grids

引用

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2013年 296卷 145-161页

作者： Garavel, Hubert Mateescu, Radu Serwe, Wendelin Inria LIG CONVECS team 655 Ave EuropeInovallee Montbonnot F-38334 Saint Ismier France

distributed verification uses the resources of several computers to speed up the verification and, even more importantly, to access large amounts of memory beyond the capabilities of a single computer. In this paper, we describe the distributed verification tools provided by the CADP (Construction and Analysis of distributed Processes) toolbox, especially focusing on its most recent tools for management, inspection, and on-the-fly exploration of distributed state spaces. We also report about large-scale experiments carried out using these tools on Grid'5000 using up to 512 distributed processes.

关键词： asynchronous systems distributed verification labeled transition system model checking on-the-fly verification process calculus

来源：评论

学校读者我要写书评

暂无评论

On distributed Merlin-Arthur Decision Protocols 26th

On Distributed Merlin-Arthur Decision Protocols

引用

26th International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Fraigniaud, Pierre Montealegre, Pedro Oshman, Rotem Rapaport, Ivan Todinca, Ioan CNRS Paris France Univ Paris Paris France Univ Adolfo Ibanez Santiago Chile Tel Aviv Univ Tel Aviv Israel Univ Chile UMI CNRS 2807 DIM CMM Santiago Chile Univ Orleans Orleans France

ISBN: (纸本)9783030249212;9783030249229

In a distributed locally-checkable proof, we are interested in checking the legality of a given network configuration with respect to some Boolean predicate. To do so, the network enlists the help of a prover-a computationally-unbounded oracle that aims at convincing the network that its state is legal, by providing the nodes with certificates that form a distributed proof of legality. The nodes then verify the proof by examining their certificate, their local neighborhood and the certificates of their neighbors. In this paper we examine the power of a randomized form of locally-checkable proof, called distributed Merlin-Arthur protocols, or dMA for short. In a dMA protocol, the prover assigns each node a short certificate, and the nodes then exchange random messages with their neighbors. We show that while there exist problems for which dMA protocols are more efficient than protocols that do not use randomness, for several natural problems, including Leader Election, Diameter, Symmetry, and Counting Distinct Elements, dMA protocols are no more efficient than standard nondeterministic protocols. This is in contrast with Arthur-Merlin (dAM) protocols and Randomized Proof Labeling Schemes (RPLS), which are known to provide improvements in certificate size, at least for some of the aforementioned properties.

关键词： distributed verification Nondeterminism Interactive computation Interactive proof systems

来源：评论

学校读者我要写书评

暂无评论

Randomized proof-labeling schemes

引用

distributed COMPUTING 2019年第3期32卷 217-234页

作者： Fraigniaud, Pierre Patt-Shamir, Boaz Perry, Mor CNRS Inst Rech Informat Fondamentale Paris France Univ Paris Diderot Paris France Tel Aviv Univ Sch Elect Engn Tel Aviv Israel

Proof-labeling schemes, introduced by Korman et al. (Distrib Comput 22(4):215-233, 2010. 10.1007/s00446-010-0095-3), are a mechanism to certify that a network configuration satisfies a given boolean predicate. Such mechanisms find applications in many contexts, e.g., the design of fault-tolerant distributed algorithms. In a proof-labeling scheme, predicate verification consists of neighbors exchanging labels, whose contents depends on the predicate. In this paper, we introduce the notion of randomized proof-labeling schemes where messages are randomized and correctness is probabilistic. We show that randomization reduces verification complexity exponentially while guaranteeing probability of correctness arbitrarily close to one. We also present a novel message-size lower bound technique that applies to deterministic as well as randomized proof-labeling schemes. Using this technique, we establish several tight bounds on the verification complexity of MST, acyclicity, connectivity, and longest cycle size.

关键词： distributed verification Communication complexity Proof-labeling schemes Non-determinism Randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

DAPV: Diagnosing Anomalies in MANETs Routing With Provenance and verification

引用

IEEE ACCESS 2019年 7卷 35302-35316页

作者： Li, Teng Ma, Jianfeng Pei, Qingqi Song, Houbing Shen, Yulong Sun, Cong Xidian Univ Sch Cyber Engn Xian 710071 Shaanxi Peoples R China Xidian Univ Shaanxi Key Lab Blockchain & Secur Computuing Xian 710071 Shaanxi Peoples R China West Virginia Univ Dept Elect & Comp Engn Montgomery WV 25801 USA Xidian Univ Sch Comp Sci Xian 710071 Shaanxi Peoples R China

Routing security plays an important role in the mobile ad hoc networks (MANETs). Despite many attempts to improve its security, the routing mechanism of MANETs remains vulnerable to attacks. Unlike most existing solutions that prevent the specific problems, our approach tends to detect the misbehavior and identify the anomalous nodes in MANETs automatically. The existing approaches offer support for detecting attacks or debugging in different routing phases, but many of them cannot answer the absence of an event. Besides, without considering the privacy of the nodes, these methods depend on the central control program or a third party to supervise the whole network. In this paper, we present a system called DAPV that canfind single or collaborative malicious nodes and the paralyzed nodes which behave abnormally. DAPV can detect both direct and indirect attacks launched during the routing phase. To detect malicious or abnormal nodes, DAPV relies on two main techniques. First, the provenance tracking enables the hosts to deduce the expected log information of the peers with the known log entries. Second, the privacy-preserving verification uses Merkle Hash Tree to verify the logs without revealing any privacy of the nodes. We demonstrate the effectiveness of our approach by applying DAPV to three scenarios: 1) detecting injected malicious intermediated routers which commit active and passive attacks in MANETs;2) resisting the collaborative black-hole attack of the AODV protocol, and;3) detecting paralyzed routers in university campus networks. Our experimental results show that our approach can detect the malicious and paralyzed nodes, and the overhead of DAPV is moderate.

关键词： Wireless network security anomalies detection distributed verification

来源：评论

学校读者我要写书评

暂无评论

Fixed Points of Gaussian Belief Propagation and Relation to Convergence

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2019年第23期67卷 6025-6038页

作者： Li, Bin Su, Qinliang Wu, Yik-Chung Beijing Inst Technol Sch Informat & Elect Beijing Peoples R China Sun Yat Sen Univ Guangdong Key Lab Big Data Anal & Proc Sch Data & Comp Sci Guangzhou 510275 Guangdong Peoples R China Univ Hong Kong Dept Elect & Elect Engn Hong Kong Peoples R China

In general, Gaussian belief propagation (BP) is not guaranteed to converge in loopy graphs. But when Gaussian BP converges to a fixed point of its update equations, the exact means of the marginal distributions can be obtained. However, given a Gaussian graphical model, whether Gaussian BP would have fixed points is unknown. Moreover, the relation between the convergence of Gaussian BP and its fixed points is not clear. To answer these questions, the necessary and sufficient existence condition and an easily verifiable sufficient existence condition of fixed points of Gaussian BP are proposed. Conditioned on the existence of fixed points of Gaussian BP, the convergence conditions of outgoing messages' parameters are analyzed, where outgoing message denotes the message flowing from a variable node to a factor node on a factor graph. It is proved that outgoing messages' precisions (the reciprocal of variance) would converge if there exist fixed points for Gaussian BP. This provides an elegant interpretation of the convergence condition of outgoing messages' precisions. On the other hand, to guarantee the convergence of outgoing messages' means, a sufficient condition for Gaussian models with a single loop and a sufficient condition that can be checked without obtaining the converged outgoing messages' precisions are derived. The relations between the convergence conditions of outgoing messages' parameters and those of incoming messages' parameters are also revealed, making any convergence condition of outgoing messages valid for verifying the convergence of incoming messages. Numerical results are presented to corroborate the newly established theories.

关键词： Gaussian belief propagation fixed point convergence analysis divergence distributed verification

来源：评论

学校读者我要写书评

暂无评论

Certification of Compact Low-Stretch Routing Schemes

引用

COMPUTER JOURNAL 2019年第5期62卷 730-746页

作者： Balliu, Alkida Fraigniaud, Pierre Aalto Univ Dept Comp Sci Konemiehentie 2 Espoo 02150 Finland Univ Paris Diderot CNRS IRIF Batiment Sophie Germain8 Pl Aurelie Nemours F-75013 Paris France

On the one hand, the correctness of routing protocols in networks is an issue of utmost importance for guaranteeing the delivery of messages from any source to any target. On the other hand, a large collection of routing schemes have been proposed during the last two decades, with the objective of transmitting messages along short routes, while keeping the routing tables small. Regrettably, all these schemes share the property that an adversary may modify the content of the routing tables with the objective of, e.g. blocking the delivery of messages between some pairs of nodes, without being detected by any node. In this paper, we present a simple certification mechanism which enables the nodes to locally detect any alteration of their routing tables. In particular, we show how to locally verify the stretch-3 routing scheme by Thorup and Zwick, presented in SPAA in 2001, by adding certificates of the same order of magnitude as the original routing tables. We also propose a new name-independent routing scheme using routing tables of size (O) over tilde (root n) bits at each node in n-node networks. This new routing scheme can be locally verified using certificates of (O) over tilde (root n) bits. Its stretch is 3 if using handshaking, and 5 otherwise.

关键词： distributed network computing distributed decision distributed verification distributed data structures

来源：评论

学校读者我要写书评

暂无评论

distributed verification of Controllability for Weighted Out-tree based Topology

Distributed Verification of Controllability for Weighted Out...

引用

American Control Conference (ACC)

作者： Guo, Di Yan, Gangfeng Lin, Zhiyun Zhejiang Univ Coll Elect Engn Asus Intelligent Syst Lab Hangzhou 310027 Peoples R China

ISBN: (纸本)9781457710964;9781457710957

In this paper, the controllability problem for multi-agent systems is investigated based on leader-follower structure. We focus on an out-tree topology which leads to minimum information exchange among agents. New necessary and sufficient conditions for the controllability of the system are established. Based on out-trees, controllability of several extended topologies are investigated as well.

关键词： Multi-agent systems Controllability distributed verification

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：