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