CAJ | 학술논문

异构分布式系统性能得到大幅度提升的同时,却造成故障率大增,以有向无环图(Directed Acyclic Graph,DAG)任务模型研究异构分布式系统的容错调度成为当前的研究热点.广泛采用的基于任务复制的容错算法存在以下问题:(1) DAG任务可靠性需求与DAG可靠性需求的约束存在缺陷且缺乏严谨的理论证明;(2)每个任务仅有一个副版任务,不足以应对任务潜在的多次发生的故障;(3)盲目地使每个任务拥有e+l个副版来容忍可能的ε个故障,虽然提高了系统的可靠性但易造成系统冗余度过高,并付出昂贵的计算资源.文中首先分析DAG图中任务依赖关系,确定DAG任务的可靠性概率模型,并建立DAG可靠性模型;接着提出满足可靠性目标的任务复制下限值算法、经济的任务复制策略算法和贪婪的任务复制策略算法,精确量化各个任务需要复制的次数,最后在上述算法的基础上提出可选策略的DAG容错算法OPDFT(Optional Policy on DAG Fault-Tolerant).实验表明,OPDFT 算法的经济复制策略和贪婪复制策略的可靠性代价分别是盲目策略算法可靠性代价的60％和70％左右.
이구분포식계통성능득도대폭도제승적동시,각조성고장솔대증,이유향무배도(Directed Acyclic Graph,DAG)임무모형연구이구분포식계통적용착조도성위당전적연구열점.엄범채용적기우임무복제적용착산법존재이하문제:(1) DAG임무가고성수구여DAG가고성수구적약속존재결함차결핍엄근적이론증명;(2)매개임무부유일개부판임무,불족이응대임무잠재적다차발생적고장;(3)맹목지사매개임무옹유e+l개부판래용인가능적ε개고장,수연제고료계통적가고성단역조성계통용여도과고,병부출앙귀적계산자원.문중수선분석DAG도중임무의뢰관계,학정DAG임무적가고성개솔모형,병건립DAG가고성모형;접착제출만족가고성목표적임무복제하한치산법、경제적임무복제책략산법화탐람적임무복제책략산법,정학양화각개임무수요복제적차수,최후재상술산법적기출상제출가선책략적DAG용착산법OPDFT(Optional Policy on DAG Fault-Tolerant).실험표명,OPDFT 산법적경제복제책략화탐람복제책략적가고성대개분별시맹목책략산법가고성대개적60％화70％좌우.