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

作者：蔡诗妤国立交通大学

学位级别：硕士

本篇论文考虑的是设计解决极小控制集（MDS）问题的更具有效率的自我稳定演算法（self-stabilizing algorithms）。设n为分散式系统里的节点数目。若一个自我稳定演算法在给定的分散式系统执行至多t次动作后，即可到达合理状态（legitim... 详细信息

本篇论文考虑的是设计解决极小控制集（MDS）问题的更具有效率的自我稳定演算法（self-stabilizing algorithms）。设n为分散式系统里的节点数目。若一个自我稳定演算法在给定的分散式系统执行至多t次动作后，即可到达合理状态（legitimate configuration），则称此自我稳定演算法为t-动作演算法（t-move algorithm）。在2007年，Turau提出了一个分散式排程下的解决MDS问题的9n-动作演算法。随后，在2008年，Goddard等人提出一个分散式排程下的解决MDS问题的5n-动作演算法。设计一个执行动作少于5n次的分散式排程下的解决MDS问题的演算法，确实是一个挑战。本篇论文的目的就在于设计出这样的演算法。具体来说，我们提出了一个分散式排程下的解决MDS问题的4n-动作演算法；此外，采用我们演算法，需要4n-1个动作才可以到达合理状态的例子也被提出。

关键词：自我稳定演算法容错分散式计算图形演算法控制

来源：评论

学校读者我要写书评

暂无评论

分散式系统之自我稳定极小控制集演算法与凯氏图之正负号星控制数

分散式系统之自我稳定极小控制集演算法与凯氏图之正负号星控制数

引用

作者：邱钰杰国立交通大学

学位级别：博士

图论的控制集问题的研究始于1960年代。一个分散式系统(例如：一个随意网路)可以用一个无向简单图G=(V,E)来表示，其中V表示点集，而E表示点跟点之间的联结关系。图G的点集V的子集合D被称为是控制集，若此子集D具有性质：V中的任一元素... 详细信息

图论的控制集问题的研究始于1960年代。一个分散式系统(例如：一个随意网路)可以用一个无向简单图G=(V,E)来表示，其中V表示点集，而E表示点跟点之间的联结关系。图G的点集V的子集合D被称为是控制集，若此子集D具有性质：V中的任一元素v属于D或与D中的元素相邻。如果一个控制集不真包含另一控制集，则称其为极小控制集(简记为MDS)。极小控制集在无线网路中的应用之一是使所需的资源中心保持为较少数目。自我稳定是一个可用于设计分散式系统容忍暂时性错误的一个概念，并且是在1974年由Dijkstra提出。一个分散式系统是自我稳定的，如果它满足：不论初始组态为何，系统总是能保证在有限时间内达到一个合法的(正确的)组态。此处所称的系统组态是由系统中所有节点的状态所组成。一个自我稳定演算法由一些规则所组成，每个规则都有其触发条件及其对应动作，该动作能通过更新节点的变数来改变节点的状态。每执行一个规则称为是一步。本论文所提出的演算法的效能皆是以执行总步数来计算。自我稳定演算法有许多不同的执行模式，且执行模式是以排程器的概念来呈现。排程器分为公平的及不公平的两种。众所皆知，不公平的分散式排程器比其他类型的排程器更贴近实际使用状况。令n表示给定的分散式系统的节点数。在2007年，Turau对于MDS问题，提出了不公平的分散式排程器下的第一个线性时间的自我稳定演算法，此演算法在最多9n步之后稳定。在2008年，Goddard等人改进了上述演算法并做到最多5n步。我们将在本论文中提出一个采用不公平分散式排程器下最多4n步的自我稳定MDS演算法。理想中，MDS演算法是希望能做到MDS-静止的，亦即，若分散式系统的初始组态已经是一个MDS，则演算法将不执行任何动作。值得注意的是，在正常模式中，一个节点只能取得其一步内邻居的资讯，我们称这些资讯为1步资讯。不幸的是，在本论文中，我们将证明：1步资讯不足以建立一个MDS-静止的演算法。在本论文中，我们将讨论此一问题，并针对自我稳定MDS演算法提出一个新的性能评量，称为稳定性。我们推广这部份的结果至其他自我稳定演算法，并将自我稳定演算法分类为四个层次。特别的是，我们将证明：在2步资讯模式下，可建构出自我稳定MDS-静止的演算法，且其稳定时间之上界为2n步。在2005年，Xu提出了图的带正负号星控制集的概念，在2007年，Wang给出了完全图的带正负号控制数，详细定义请参见本论文的第五章。在2010年，Atapour等人定义了带正负号星控制划分数，并利用完全图具有可完全1-因子分解或可完全汉米尔顿圈分解的性质，计算出完全图的带正负号星控制划分数。在2012年，我与印度学者Chelvam等人合作，定义了有向图的带正负号星控制数，给出了全部有向凯式图的带正负号星控制数，与无向凯式图的带正负号星控制数的部份结果，并推广这些结果至可完全{2,1}-因子分解的正则图。

关键词：自我稳定演算法分散式计算图论演算法有正负号星控制数凯氏图

来源：评论

学校读者我要写书评

暂无评论

以賽局理論設計MANET最大獨立集合自我穩定協定

International Journal of Science and Engineering

引用

International Journal of Science and Engineering 2015年第1期5卷 1-10页

作者：黃靖軺嚴力行葉博榮

图论中的最大独立集合(maximal independent set)问题是从一个无向图G中的节点集合V挑选部分的节点集合S，需满足在S当中不存在任何两节点相邻且S不为其它任一独立集合的子集合。本篇论文透过赛局理论(game theory)寻求较佳的最大独立... 详细信息

图论中的最大独立集合(maximal independent set)问题是从一个无向图G中的节点集合V挑选部分的节点集合S，需满足在S当中不存在任何两节点相邻且S不为其它任一独立集合的子集合。本篇论文透过赛局理论(game theory)寻求较佳的最大独立集合问题解。我们接着将赛局设计转换为在分散式系统中运作的自我稳定演算法。自我稳定(self-stabilization)的性质可以保证不论系统初始状态为何，必定会在有限的时间内到达稳定的合法状态，即最大独立集合。为了使我们提出的方法能在MANET中有效的实作，需另外再对演算法进行修改以克服环境上的差异。模拟实验结果显示我们提出的演算法有较好的效能表现，比先前的方法有较多的最大独立集合节点数以及较短的收敛时间。

关键词：最大獨立集合賽局理論自我穩定演算法

来源：评论

学校读者我要写书评

暂无评论

当k等于1或2时针对最小k-支配集问题的自我稳定演算法

当k等于1或2时针对最小k-支配集问题的自我稳定演算法

引用

作者：陈志远元智大学

学位级别：博士

自我稳定(self-stabilization)是不遮掩错误的那类容错分散式演算法的一种适当的理论框架。自我稳定的性质使得演算法有能力从错误的情况下自动的恢复。针对瞬时错误(transient fault) 的处理，自我稳定系统比传统的容错系统能力更强。... 详细信息

自我稳定(self-stabilization)是不遮掩错误的那类容错分散式演算法的一种适当的理论框架。自我稳定的性质使得演算法有能力从错误的情况下自动的恢复。针对瞬时错误(transient fault) 的处理，自我稳定系统比传统的容错系统能力更强。所谓瞬时错误是指，只会干扰系统状态而不会干扰程式码的错误。自我稳定的观念首度由Dijkstra在1974年的论文中提出。根据Dijkstra原来的概念，一个分散式演算法若满足以下的条件，则我们称它为自我稳定。此条件为‘无论系统的初始状态为何，无论演算法如何的执行，系统都必定会被带到合理状态(legitimate configuration)，且之后，若系统不再遭遇到任何的瞬时错误，便不会离开合理状态’。在Dijkstra的论文中所采用的计算模式现在被通称为central demon计算模式。大部分关于自我稳定演算法的论文都采用此种计算模式。之后，Burns在1987年提出了更一般化的distributed demon计算模式。在central demon计算模式下，系统的每一个原子步骤(atomic step)中，恰有一个具特权的处理器(privileged processor)被central demon挑选来做动作(move)。然而在distributed demon计算模式下，系统的每一个原子步骤中，任意数目的具特权的处理器皆有可能被distributed demon同时选来做动作。 Dolev等人在他们1993年着名的论文中提出了Dolev计算模式。此计算模式和Dijkstra的central demon计算模式最主要的差别是它假设读/写分开的原子步骤(read/write atomicity)。在这样的假设下，每个系统动作（或原子步骤）是由一些内部计算和一个单一读的动作或一个单一写的动作所组成。而且每一个处理器按照自己的步调来执行自己所配备的程式，且程式的执行是依照程式指令的顺序依序来执行。在分散式系统中的k-支配集(k-dominating set)是指一个由一些处理器所组成的集合，且在此集合外面的每一个处理器至少必须有k个邻居在此集合里面。在应用上，k-支配集可以作为系统内理想的放置资源的地点。而最小k-支配集(minimal k-dominating set)可以让放置资源的地点的数目尽可能地少。因为最大独立集(maximal independent set)可以被视为最小1-支配集，所以从某些观点，找最小2-支配集问题是找最大独立集问题的延伸。在此论文中，我们首先证明Kamei和Kakugawa所提出的最小k-支配集演算法，在k=2的情况，在任何一个采用central demon计算模式的一般网路中运作，必会是自我稳定且能解决最小2-支配集问题。我们同时也计算出此演算法在最差状况的稳定时间(stabilization time)为线性。其次，我们提出了另一个演算法。此演算法在任何一个采用distributed demon计算模式的一般网路中运作，皆为自我稳定且可以解决最小2-支配集问题。最后，我们修改了Goddard等人所提出的在同步计算模式(synchronous model)下为自我稳定的最大独立集演算法。我们证明这个修改的版本，在任何一个采用Dolev计算模式的一般网路中运作，必为自我稳定且能解决最小支配集问题。

关键词：自我稳定演算法最小k-支配集 central demon计算模式 distributed demon计算模式 Dolev计算模式容错系统瞬时错误

来源：评论

学校读者我要写书评

暂无评论

完全圖上最大權重配對問題知自我穩定演算法的設計及分析

引用

师大学报：数理与科技类 2000年第1&2期45卷 21-36页

作者：陳瑞宜林順喜

在1974 年，Dijkstra提出了自我稳定的概念。一个分散式系统不论其初始状态为何，最後都会收敛至正确的系统状态称之为自我稳定系统。近年来，自我稳定演算法不用初始化的特性受到许多研究者的重视。Hsu和Huang针对分散式网路中「最大... 详细信息

在1974 年，Dijkstra提出了自我稳定的概念。一个分散式系统不论其初始状态为何，最後都会收敛至正确的系统状态称之为自我稳定系统。近年来，自我稳定演算法不用初始化的特性受到许多研究者的重视。Hsu和Huang针对分散式网路中「最大配对」问题提出了自我稳定演算法，并利用变数函数分析法，证明了此演算法需耗用的时间复杂度为O(n^3)，然而Tel针对此一演算法提出不同的变数函数，证明最多需要O(n^2)的时间复杂度。在本论文中，我们将自我稳定系统的理论应用在完全图上的「最大权重配对」问题，设计出包含五个规则的自我稳定演算法，并针对此自我稳定演算法的正确性进行证明分析。最大权重问题是指当节点隔两配对之後，其线段权重两两交换并不会找到更大的值，也就是除了希望在图中找到最大配对之外，更进一步能够使配对的权重达到最大。因此我们结合了Hsu-Huang最大配对自我稳定演算法，以及崭新的交换配对规则，保留自我稳定系统容错及自我稳定的特性，设计了时间复杂度为O(n^2 + nk)的一个最大权重配对问题之自我稳定演算法。

关键词：自我穩定演算法系統容錯最大配對問題最大權重配對問題

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：