低空間需求之分散式最佳同步交互器; Optimal Alternators with Reduced Space Complexity

NCU Institutional Repository > 資訊電機學院 > 資訊工程研究所 > 博碩士論文 > Item 987654321/8835

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/8835

题名:	低空間需求之分散式最佳同步交互器;Optimal Alternators with Reduced Space Complexity
作者:	賴博淵;Pao-Yuan Lai
贡献者:	資訊工程研究所
关键词:	作業率;自我穩定;塗色問題;局部互斥;公平性;排程;graph homomorphism;scheduling;r-coloring;operating rate;alternator;fairness;self-stabilization;local mutual exclusion;interleaved multicoloring
日期:	2004-06-21
上传时间:	2009-09-22 11:35:48 (UTC+8)
出版者:	國立中央大學圖書館
摘要:	從排程的角度來看，分散式系統中的交互器（alternator）其實可視為一種排程器（scheduler），它確保每次所排定能夠執行臨界步驟的處理器構成一個獨立集而且每個處理器能夠隨著無窮的計算序列執行無限次數。先前的研究指出了排程與塗色之間的關聯，從這當中我們證明了一個具備公平性的最佳排程必定具備強公平性並探究對於一般情形下的交互器設計其最佳塗色為何。在原先提出用以設計俱備最佳公平性之交互器的一般性方法中，空間需求主要來自最佳塗色與相位同步，我們進一步移除相位同步的步驟使得空間需求降低，然後提出一個改良過的一般性設計方法。接著以這個方法為基礎，我們展示了一個適用於單向一致任意大小之環狀拓墣結構上空間需求最少的最佳交互器並分析其共時性（concurrency）與公平性（fairness）。研究成果較先前改良許多，無論是從空間複雜度、模型假設…等等來比較均是如此。 From the viewpoint of scheduling, an alternator in a distributed system can be regarded as a scheduler which ensures that each time the scheduled processors executing their critical steps constitute an independent set and that each processor is scheduled infinitely often along any infinite computation sequence. Recent work relates scheduling to coloring. According to the relation, we prove that an optimal fair scheduling is strongly fair and clarify what is an optimal coloring in general for the design of optimal 1-fair alternators. The space complexity of the previous proposed general approach to designing optimal 1-fair alternators comes from an optimal coloring and clock synchronization.We further remove the need to perform clock synchronization. This leads to an improved general approach to designing optimal 1-fair alternators with reduced space complexity. Based on the improved general approach, we demonstrate an optimal two-state alternator on synchronous uniform unidirectional rings of any size and analyze its concurrency as well as fairness. Our results greatly dominate the previous work in terms of space complexity, model assumptions and so forth.
显示于类别:	[資訊工程研究所] 博碩士論文

文件中的档案:

档案	大小	格式	浏览次数

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....