资源描述：
《单向一致环自我稳定k-值谐齐时计.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、單向一致環自我穩定k-值諧齊時計Self-stabilizingk-valueunisonclocksforunidirectionaluniformrings江振瑞Jenh-RueyJiang玄奘人文社會學院資訊管理系HsuanChuangCollegeInformationManagementDepartment<<摘要>>在此篇論文中，我們提出一個自我穩定的隨機演算法以製作一個單向一致性環上之k-值(k³2)諧齊時計。我們所提出的演算法具有兩個性質：諧齊性質及自我穩定性質。諧齊性質使環上每個節點的時計值在等值之後會以一致的速率增加，而自我穩定特性則使得系統具有容錯特性；
2、也就是說，即使環上節點的時計值在起始狀態下並不一致，所有的時計值最終也會收斂於一個單一值。在此篇論文中，我們證明了所提演算法的正確性，並將所提的演算法與許多相關的方法做了比較。關鍵字：自我穩定，諧齊時計，容錯性，隨機演算法，單向一致環Self-stabilizingk-valueunisonclocksforunidirectionaluniformringsJenh-RueyJiangHsuanChuangCollegeInformationManagementDepartmentAbstractInthispaper,weproposeaself-stabilizingr
3、andomizedalgorithmthatmaintainsk-valueunisonclock,k³2,foruniformrings.Theproposedalgorithmhastwoproperties:unisonpropertyandself-stabilizationproperties.Theunisonpropertymeansthatonceallclocksareofasamevalue,theywillincreaseatthesameratehenceforth.Andtheself-stabilizationpropertymakesthesys
4、temfault-tolerant;namely,evenclocksareofdifferentvaluesinitially,theclockswillconvergetoasamevalueeventually.Wehaveprovedthecorrectnessofthealgorithmandcomparethealgorithmwithrelatedones.Keywords:self-stabilization,unisonclock,fault-tolerance,randomizedalgorithm,unidirectionaluniformring.1.
5、IntroductionInthispaper,weproposeaself-stabilizingrandomizedalgorithmthatmaintainsk-valueunisonclocks,k³2,foruniformrings.Wesaythataringisuniformifallnodes(processors)ontheringexecuteasamealgorithm.Thenodesexecutethealgorithmphasebyphase.Ateachphase,allnodessimultaneouslyreadtheclocksofthei
6、rleftneighborsandthenmodifytheirownclocks.Weassumetheringunidirectionalsinceeachnodeintheringreadstheleftneighbor’sclockonly.Theproposedalgorithmhasthepropertyofunison;i.e.,oncealltheclocksareofasamevalue,theywillallincreasebyoneineveryfollowingphase(andhencealltheclocksareofthesamevalueaga
7、inandagain).Theproposedalgorithmalsohasthepropertyofself-stabilization;i.e.,allclockswillconvergetoasamevalueeventhoughtheyareofdifferentvaluesinitially.Theconceptofself-stabilizationisfirstintroducedbyDijkstrain1974[Dijk74],andthestudyofself-stabilizing
