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

Semi-local Model of computations on Graphs to Break the local Symmetry

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE 2006年第2期154卷 113-120页

作者： Wroblewski, Dobieslaw Polish Acad Sci Inst Comp Sci Warsaw Poland

We consider finite connected undirected graphs without self-loops as a model of computer networks. The nodes of the graph represent computers or processors, while the edges of the graph correspond to the links between them. We present a model of distributed computations, called semi-local. This extension of the classical local model breaks the local symmetry. As a result, many useful tasks become deterministically solvable in every network assuming a very small initial knowledge about its graph representation. One of these tasks is a creation of a token in an arbitrary anonymous ring-an example of election of a leader. A semi-local solution to this problem is presented.

关键词： Transformations and refinements verification and analysis local computations graph relabelling systems election anonymous graphs rings token ring networks

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing enumeration algorithm

引用

INFORMATION PROCESSING LETTERS 2002年第6期82卷 299-305页

作者： Godard, E Univ Bordeaux 1 LaBRI UMR 5800 F-33405 Talence France

This paper describes a self-stabilizing version of an algorithm presented by A. Mazurkiewicz [Inform. Process. Lett. 61 (1997) 233-239] for enumerating nodes by local rules on an anonymous network. The result improves the reliability aspects of the original algorithm and underlines the importance of a non-ambiguous topology for a network. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： distributed computing self-stabilizing systems local computations anonymous networks

来源：评论

学校读者我要写书评

暂无评论

Power diagrams and interaction processes for unions of discs

引用

ADVANCES IN APPLIED PROBABILITY 2008年第2期40卷 321-347页

作者： Moller, Jesper Helisova, Katerina Aalborg Univ Dept Math Sci DK-9220 Aalborg Denmark Charles Univ Prague Dept Probabil & Math Stat Prague 18675 8 Czech Republic

We study a flexible class of finite-disc process models with interaction between the discs. We let U denote the random set given by the union of discs, and use for the disc process an exponential family density with the canonical sufficient statistic depending only on geometric properties of U such as the area, perimeter, Euler-Poincare characteristic, and the number of holes. This includes the quermass-interaction process and the continuum random-cluster model as special cases. Viewing our model as a connected component Markov point process, and thereby establishing local and spatial Markov properties, becomes useful for handling the problem of edge effects when only U is observed within a bounded observation window. The power tessellation and its dual graph become major tools when establishing inclusion-exclusion formulae, formulae for computing geometric characteristics of U, and stability properties of the underlying disc process density. Algorithms for constructing the power tessellation of U and for simulating the disc process are discussed, and the software is made public available.

关键词： area-interaction process Boolean model disc process exponential family germ-grain model local computations local stability Markov properties inclusion-exclusion formulae interaction point process power tessellation simulation quermass-interaction process random closed set Ruelle stability

来源：评论

学校读者我要写书评

暂无评论

Interaction nets for linear logic

引用

THEORETICAL COMPUTER SCIENCE 2000年第1-2期247卷 83-140页

作者： Mackie, I CNRS UMR 7650 F-91128 Palaiseau France Ecole Polytech Lab Informat LIX F-91128 Palaiseau France

This paper presents a system of interaction nets, a graphical paradigm of computation based on net rewriting, for linear logic. The two main features of the encoding are that the system of interaction is a finite one (meaning that there are a finite number of agents and interaction rules), and most importantly, for the multiplicative exponential fragment we obtain for the first time a strong result that nets in normal form correspond to cut-free proofs - thus we can trivially convert a net back into a proof without a complicated read-back algorithm. For the additives, we perform weak cut-elimination (without the additive commutative cut-elimination step), which is the most natural strategy for these connectives since it avoids unnecessary duplication of proofs. For proofs containing additives, our result is that nets in normal form correspond to cut-free proofs module additive commutative cuts. This implementation of linear logic is the most faithful and the most efficient of ail the extant interaction net encodings of linear logic. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： linear logic cut-elimination interaction nets local computations

来源：评论

学校读者我要写书评

暂无评论

Fully distributed economic dispatch of distributed generators in active distribution networks considering losses

引用

IET GENERATION TRANSMISSION & DISTRIBUTION 2017年第3期11卷 627-636页

作者： Kouveliotis-Lysikatos, Iasonas Hatziargyriou, Nikos Natl Tech Univ Athens Dept Elect Engn Heroon Polytechniou 9 Athens Greece

The increased complexity of the modern distribution system caused by the installation of a large number of distributed energy resources, dictates the necessity for novel, decentralised schemes for the grid operation. In this study, a fully distributed method for the economic dispatch (ED) problem is proposed that takes into account distribution losses. The solution is reached using only local computations and exchange of messages between adjacent nodes without the need of a central coordinating entity. The algorithm presents plug-and-play capabilities and is self-triggered. More specifically, the ED is formulated as a resource allocation problem and a fully distributed algorithm is employed to acquire the solution that is based on the replicator equation model. It takes into account the technical constraints of the generators and it is extended in order to integrate the distributed calculation of active power losses using distributed estimation of the loss penalty factors. Guarantees for the convergence and optimality of the proposed algorithm are provided along with numerical results that demonstrate the effectiveness and efficiency of the algorithm.

关键词： Power system management, operation and economics distributed estimation adjacent nodes loss penalty factors distributed power generation message exchange distributed economic dispatch distributed generators power generation dispatch active distribution networks resource allocation problem Distribution networks active power loss Distributed power generation replicator equation power distribution economics distribution loss plug-and-play capability local computations resource allocation distributed energy resources

来源：评论

学校读者我要写书评

暂无评论

Distributed enumeration

引用

INFORMATION PROCESSING LETTERS 1997年第5期61卷 233-239页

作者： Mazurkiewicz, A Institute of Computer Science of PAS Ordona 21 01-237 Warsaw Poland

Finite, undirected graphs without self-loops are considered in the paper. The goal is to find a protocol for local computation which, starting with a uniform labelling of graph nodes, eventually terminates with a labelling being an enumeration of nodes. It is known from (Litovsky et al., 1993) that for some (''ambiguous'') graphs of the considered family such a protocol does not exist;in the present paper a protocol is constructed which is the best in the sense that, for a given graph, it either enumerates nodes of the graph, or supplies a proof of ambiguity of the graph. It is proved that for any graph there exists a computation terminating with any a priori given enumeration of its nodes. It is also proved that after successful termination individual nodes ''know'' this fact. The proposed protocol can be used for election a leader out of nodes of graphs;in this way it generalizes existing algorithms. The protocol is called distributed, since remote nodes of the processed graph can communicate only by sending messages. (C) 1997 Elsevier Science B.V.

关键词： algorithms distributed systems graphs local computations

来源：评论

学校读者我要写书评

暂无评论

UNCERTAIN EVIDENCE AND ARTIFICIAL ANALYSIS

引用

JOURNAL OF STATISTICAL PLANNING AND INFERENCE 1988年第3期20卷 355-368页

作者： DEMPSTER, AP KONG, A HARVARD UNIV DEPT STATCAMBRIDGEMA 02138

A belief function measure of uncertainty, associated with a network based knowledge structure, effectively defines an artificial analyst (e.g., an expert system) capable of making uncertain judgements. In practice, a belief function is typically constructed by combining independent components developed on local areas of the network from inputs such as accepted causal theories, probabilistic judgements by experts, or empirical sample data. Representation of the network in a special form called a ‘tree of cliques’ leads to a locally controlled algorithm that propagates locally defined beliefs through the tree, and fuses the resulting beliefs at the nodes, in such a way as to simultaneously compute marginal beliefs over all nodes of the tree. The paper develops a simple hypothetical example from the field of reliability to illustrate these ideas.

关键词： 60J05 62N99 90B25 Belief functions local computations networks local dependency expert systems tree of cliques

来源：评论

学校读者我要写书评

暂无评论

Distributed Maintenance of a Spanning Tree of k-Connected Graphs 24

Distributed Maintenance of a Spanning Tree of k-Connected Gr...

引用

IEEE 24th Pacific Rim International Symposium on Dependable Computing (PRDC)

作者： Hamid, Brahim Rouland, Quentin Jaskolkat, Jason IRIT Univ Toulouse 118 Route Narbonne F-31062 Toulouse 9 France Carleton Univ Syst & Comp Engn 1125 Colonel By Dr Ottawa ON K1S 5B6 Canada

ISBN: (纸本)9781728149615

This work is devoted to the problem of spanning trees maintenance in the presence of crash failures in a distributed environment using only local knowledge. Using a pre-constructed spanning tree of a k-connected graph, we present a protocol to maintain a spanning tree in the presence of k - 1 consecutive failures. The contribution of this paper is threefold. First, the problem is formalized as an occurrence of Menger's theorem in a distributed setting. The second result shows an implementation of the protocol which is composed of a set of modules encoded using a graph relabeling systems model. The last contribution is the implementation of this protocol in the asynchronous message passing model. For a given graph G = (V, E), where M is the number of its edges, N is the number of its nodes, and Delta is its degree;After each failure occurrence, our algorithms need the following requirements: The first one uses O(Delta x N) steps and O(Delta) bits per node. The second one uses ON + M) messages and O(N) time and O(Delta) bits per node. In addition, we investigate the possible specification and verification of the presented algorithm using Alloy as a tooled formal language.

关键词： Distributed computing failure detectors fault-tolerance graph relabeling systems local computations maintenance spanning tree vertex connectivity

来源：评论

学校读者我要写书评

暂无评论

locally computable enumerations 11th

引用

11th International Symposium on Fundamentals of Computation Theory (FCT 97)

作者： Mazurkiewicz, A Polish Acad Sci Space Res Ctr PL-01237 Warsaw Poland

ISBN: (纸本)3540633863

This paper is an extended and modified version of [10]. A protocol with local rules is presented for enumerating anonymous nodes of finite graphs. It is proved that such algorithms do not exists for the class of ambiguous graphs, defined in the paper;the proposed algorithm works successfully for remaining non-ambiguous graphs. It is also proved that protocol is fair, which means that no enumeration of nodes is discriminated by the protocol and that all individual nodes "know" the fact of successful termination of the protocol activity, provided the number of nodes of a graph is known to the protocol. The described protocol is a generalization of that presented in [9] by the author.

关键词： algorithms distributed systems graphs local computations

来源：评论

学校读者我要写书评

暂无评论

Simulation of random set models for unions of discs and the use of power tessellations

Simulation of random set models for unions of discs and the ...

引用

6th International Symposium on Voronoi Diagrams

作者： Moller, Jesper Helisova, Katerina Aalborg Univ Dept Math Sci Aalborg Denmark Czech Tech Univ Dept Math Prague Czech Republic

ISBN: (纸本)9781424447695

The power tessellation (or power diagram or Laguerre diagram) turns out to be particularly useful in connection to a flexible class of random set models specified by an underlying process of interacting discs. We discuss how to simulate these models and calculate various geometric characteristics of power tessellations, where new relations for the characteristics are established. The proposed model is fitted to a heather dataset.

关键词： birth-death algorithm Boolean model codes geometric characteristics heather dataset inclusion-exclusion formulae interacting discs local computations power diagram statistical analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：