English  |  正體中文  |  简体中文  |  Items with full text/Total items : 65317/65317 (100%)
Visitors : 21290025      Online Users : 362
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version


    Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/8835


    Title: 低空間需求之分散式最佳同步交互器;Optimal Alternators with Reduced Space Complexity
    Authors: 賴博淵;Pao-Yuan Lai
    Contributors: 資訊工程研究所
    Keywords: 作業率;自我穩定;塗色問題;局部互斥;公平性;排程;graph homomorphism;scheduling;r-coloring;operating rate;alternator;fairness;self-stabilization;local mutual exclusion;interleaved multicoloring
    Date: 2004-06-21
    Issue Date: 2009-09-22 11:35:48 (UTC+8)
    Publisher: 國立中央大學圖書館
    Abstract: 從排程的角度來看,分散式系統中的交互器(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.
    Appears in Collections:[資訊工程研究所] 博碩士論文

    Files in This Item:

    File SizeFormat
    0KbUnknown411View/Open


    All items in NCUIR are protected by copyright, with all rights reserved.

    社群 sharing

    ::: Copyright National Central University. | 國立中央大學圖書館版權所有 | 收藏本站 | 設為首頁 | 最佳瀏覽畫面: 1024*768 | 建站日期:8-24-2009 :::
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback  - 隱私權政策聲明