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

American Control Conference

作者： Di Guo Gangfeng Yan Zhiyun Lin Asus Intelligent Systems Lab College of Electrical Engineering Zhejiang University 38 Zheda Road Hangzhou 310027 P. R. China

ISBN: (纸本)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 controllability topology information exchange Multi-agent systems Sufficient conditions Tree Topology verification

来源：评论

学校读者我要写书评

暂无评论

Local verification of global proofs 32

Local verification of global proofs

引用

32nd International Symposium on distributed Computing, DISC 2018

作者： Feuilloley, Laurent Hirvonen, Juho University Paris Diderot France University of Freiburg Germany

ISBN: (纸本)9783959770927

In this work we study the cost of local and global proofs on distributed verification. In this setting the nodes of a distributed system are provided with a nondeterministic proof for the correctness of the state of the system, and the nodes need to verify this proof by looking at only their local neighborhood in the system. Previous works have studied the model where each node is given its own, possibly unique, part of the proof as input. The cost of a proof is the maximum size of an individual label. We compare this model to a model where each node has access to the same global proof, and the cost is the size of this global proof. It is easy to see that a global proof can always include all of the local proofs, and every local proof can be a copy of the global proof. We show that there exists properties that exhibit these relative proof sizes, and also properties that are somewhere in between. In addition, we introduce a new lower bound technique and use it to prove a tight lower bound on the complexity of reversing distributed decision and establish a link between communication complexity and distributed proof complexity. © Laurent Feuilloley and Juho Hirvonen.

关键词： distributed verification Local proofs Non-determinism Proof-labeling schemes

来源：评论

学校读者我要写书评

暂无评论

Efficient and Privacy-Preserving Metering Protocols for Smart Grid Systems

引用

IEEE TRANSACTIONS ON SMART GRID 2016年第3期7卷 1732-1742页

作者： Jo, Hyo Jin Kim, In Seok Lee, Dong Hoon Korea Univ Ctr Informat Secur Seoul 136701 South Korea

Smart grids have attracted increasing interest in the field of industrial research. These systems allow electricity consumers to communicate with electrical systems using bidirectional communications. However, these bidirectional channels may introduce privacy threats to consumers. Considerable research has been conducted with the aim of resolving these threats. Unfortunately, a practical smart grid design with adequate efficiency and security functionalities has not yet been produced. In this paper, we propose lightweight privacy preserving metering protocols by designing a distributed authentication method to further increase the speed of the message authentication process. We confirmed the efficiency and security of our method by performing a detailed analysis.

关键词： distributed verification privacy smart grid

来源：评论

学校读者我要写书评

暂无评论

Tight Bounds For distributed MST verification

Tight Bounds For Distributed MST Verification

引用

28th International Symposium on Theoretical Aspects of Computer Science (SATCS)

作者： Kor, Liah Korman, Amos Peleg, David Weizmann Inst Sci Dept Comp Sci & Appl Math IL-76100 Rehovot Israel Univ Paris 07 CNRS Paris France Univ Paris 07 LIAFA Paris France

ISBN: (纸本)9783939897255

This paper establishes tight bounds for the Minimum-weight Spanning Tree (MST) verification problem in the distributed setting. Specifically, we provide an MST verification algorithm that achieves simultaneously O(|E|) messages and O(root n+D) time, where |E| is the number of edges in the given graph G and D is G's diameter. On the negative side, we show that any MST verification algorithm must send Omega(|E|) messages and incur (root n + D) time in worst case. Our upper bound result appears to indicate that the verification of an MST may be easier than its construction, since for MST construction, both lower bounds of Omega(| E|) messages and Omega(root n+ D) time hold, but at the moment there is no known distributed algorithm that constructs an MST and achieves simultaneously O (|E|) messages and O(root n+D) time. Specifically, the best known time-optimal algorithm (using O (root n + D) time) requires O(| E| + n(3/2)) messages, and the best known message-optimal algorithm (using O(|E|) messages) requires O(n) time. On the other hand, our lower bound results indicate that the verification of an MST is not significantly easier than its construction.

关键词： distributed algorithms distributed verification labeling schemes minimum-weight spanning tree

来源：评论

学校读者我要写书评

暂无评论

Randomized Local Network Computing 15

Randomized Local Network Computing

引用

27th ACM symposium on Parallelism in Algorithms and Architectures (SPAA)

作者： Feuilloley, Laurent Fraigniaud, Pierre Aalto Univ Dept Comp Sci Espoo Finland CNRS Dept Comp Sci Paris France Univ Paris Diderot Paris France

ISBN: (纸本)9781450335881

In this paper, we carry on investigating the line of research questioning the power of randomization for the design of distributed algorithms. In their seminal paper, Naor and Stockmeyer [STOC 1993] established that, in the context of network computing, in which all nodes execute the same algorithm in parallel, any construction task that can be solved locally by a randomized Monte-Carlo algorithm can also be solved locally by a deterministic algorithm. This result however holds in a specific context. In particular, it holds only for distributed tasks whose solutions can be locally checked by a deterministic algorithm. In this paper, we extend the result of Naor and Stockmeyer to a wider class of tasks. Specifically, we prove that the same derandomization result holds for every task whose solutions can be locally checked using a 2-sided error randomized Monte-Carlo algorithm. This extension finds applications to, e.g., the design of lower bounds for construction tasks which tolerate that some nodes compute incorrect values. In a nutshell, we show that randomization does not help for solving such resilient tasks.

关键词： distributed decision distributed verification distributed computing local computing

来源：评论

学校读者我要写书评

暂无评论

Tight Bounds for distributed Minimum-Weight Spanning Tree verification

引用

THEORY OF COMPUTING SYSTEMS 2013年第2期53卷 318-340页

作者： Kor, Liah Korman, Amos Peleg, David Weizmann Inst Sci Dept Comp Sci & Appl Math IL-76100 Rehovot Israel CNRS Paris France Univ Paris 07 Paris France

This paper introduces the notion of distributed verification without preprocessing. It focuses on the Minimum-weight Spanning Tree (MST) verification problem and establishes tight upper and lower bounds for the time and message complexities of this problem. Specifically, we provide an MST verification algorithm that achieves simultaneously messages and time, where m is the number of edges in the given graph G, n is the number of nodes, and D is G's diameter. On the other hand, we show that any MST verification algorithm must send messages and incur time in worst case. Our upper bound result appears to indicate that the verification of an MST may be easier than its construction, since for MST construction, both lower bounds of messages and time hold, but at the moment there is no known distributed algorithm that constructs an MST and achieves simultaneously messages and time. Specifically, the best known time-optimal algorithm (using time) requires O(m+n (3/2)) messages, and the best known message-optimal algorithm (using messages) requires O(n) time. On the other hand, our lower bound results indicate that the verification of an MST is not significantly easier than its construction.

关键词： distributed algorithms distributed verification Labeling schemes Minimum-weight spanning tree

来源：评论

学校读者我要写书评

暂无评论

Dynamic state space partitioning for external memory state space exploration

引用

SCIENCE OF COMPUTER PROGRAMMING 2013年第7期78卷 778-795页

作者： Evangelista, Sami Kristensen, Lars Michael Univ Paris 13 CNRS UMR 7030 LIPN F-93430 Villetaneuse France Bergen Univ Coll Dept Comp Engn Bergen Norway

We describe a dynamic partitioning scheme useable by explicit state space exploration techniques that divide the state space into partitions, such as many external memory and distributed model checking algorithms. The goal of the scheme is to reduce the number of transitions that link states belonging to different partitions, and thereby limit the amount of disk access and network communication. We report on several experiments made with our verification platform ASAP that implements the dynamic partitioning scheme proposed in this paper. The experiments demonstrate the importance of exploiting locality to reduce cross transitions and 10 operations, and using informed heuristics when choosing components to be used as a basis for partition refinement. The experiments furthermore show that the proposed approach improves on earlier techniques and significantly outperforms these when provided with access to the same amount of bounded RAM. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Model checking Explicit state space exploration External memory verification distributed verification State space partitioning State explosion problem

来源：评论

学校读者我要写书评

暂无评论

Locality and Checkability in Wait-Free Computing

引用

25th International Symposium on distributed Computing (DISC 2011)

作者： Fraigniaud, Pierre Rajsbaum, Sergio Travers, Corentin CNRS F-75700 Paris France Univ Nacl Autonoma Mexico Inst Math Mexico City DF Mexico Univ Bordeaux CNRS LaBRI Bordeaux France

ISBN: (纸本)9783642240997

This paper studies notions of locality that are inherent to the specification of a distributed task and independent of the computing environment, in a shared memory wait-free system. A locality property called projection-closed is identified, that completely characterizes tasks that are wait-free checkable. A task T = (I, O, Delta) is checkable if there exists a wait-free distributed algorithm that, given s is an element of I and t is an element of O, determines whether t is an element of Delta(s), i.e., if t is a valid output for s according to the specification of T. Moreover, determining whether a projection-closed task is wait-free solvable remains undecidable, and hence this is a rich class of tasks. A stronger notion of locality considers tasks where the outputs look identically to the inputs at every vertex (input value of a, process). A task T = (I, O, Delta) is said to be locality-preserving if O is a covering complex of I. This topological property yields obstacles for wait-free solvability different in nature from the classical agreement impossibility results. On the other hand, locality-preserving tasks are projection-closed and therefore always wait-free checkable. A classification of locality-preserving tasks in term of their relative computational power is provided. A correspondence between locality-preserving tasks and subgroups of the edgepath group of an input complex shows the existence of hierarchies of locality-preserving tasks, each one containing at the top the universal task (induced by the universal covering complex), and at the bottom the trivial identity task.

关键词： distributed verification local computing wait-free decision task

来源：评论

学校读者我要写书评

暂无评论

Fast and Compact Self Stabilizing verification, Computation, and Fault Detection of an MST 11

Fast and Compact Self Stabilizing Verification, Computation,...

引用

30th Annual ACM SIGACT-SIGOPS Symposium on Principles of distributed Computing (PODC)

作者： Korman, Amos Kutten, Shay Masuzawa, Toshimitsu CNRS Paris France

ISBN: (纸本)9781450307192

This paper demonstrates the usefulness of distributed local verification of proofs, as a tool for the design of algorithms. In particular, it introduces a somewhat generalized notion of distributed local proofs, and utilizes it for improving the memory size complexity, while obtaining time efficiency too. As a result, we show that optimizing the memory size carries at most a small cost in terms of time, in the context of Minimum Spanning Tree (MST). That is, we present algorithms that are both time and space efficient for constructing an MST, for verifying it, and for detecting the location of the faults. This involves several steps that may be considered contributions in themselves. First, we generalize the notion of local proofs, trading off the locality (or, really, the time complexity) for memory efficiency. This adds a dimension to the study of distributed local proofs, that has been gaining attention recently. Second, as opposed to previous studies that presented only the labels verification part of a proof labeling schemes, we present here also a space and time efficient distributed self stabilizing marker algorithm to generates those labels. This presents proof labeling schemes as an algorithmic tool. Finally, we show how to enhance a known transformer that makes input/output algorithms self stabilizing. It now takes as input an efficient construction algorithm and an efficient self stabilizing proof labeling scheme, and produces an efficient self stabilizing algorithm. When used for MST;the transformer produces a memory optimal (i.e., O(log n) bits per node) self stabilizing algorithm, whose time complexity, namely, O(n), is significantly better even than that of previous algorithms that where not space optimal. (The time complexity of previous MST algorithms that used Omega(log(2) n) memory bits per node was O(n(2)), and the time for optimal space algorithms was O(n vertical bar E vertical bar).) Our MST algorithm also has the important property that, if f

关键词： distributed algorithm self stabilization MST distributed verification local proof checking fault detection locality

来源：评论

学校读者我要写书评

暂无评论

distributed verification with LoLA

引用

FUNDAMENTA INFORMATICAE 2003年第2-3期54卷 253-262页

作者： Schmidt, K Humboldt Univ Inst Informat D-10099 Berlin Germany

We report work in progress on a distributed version of explicit state space generation in the Petri net verification tool LoLA. We propose a data structure where all available memory of all involved workstations can be fully exploited, and load balancing actions are possible at any time while the verification is running. It is even possible to extend the set of involved workstations while a verification is running.

关键词： Petri net state space distributed verification

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：