False Deadlock Detection in Distributed Systems

Detecting a nonexistent deadlock in distributed systems has been referred to as false deadlock detection. This correspondence shows that false deadlock wi1l never occur in a system of two-phase locking transactions. We also describe an algorithm to avoid false deadlock detection when transactions are not two-phase locking.     

On Deadlock Detection in Distributed Systems

A hierarchically organized and a distributed protocol for deadlock detection in distributed databases are presented in [1]. In this paper we show that the distributed protocol is incorrect, and present possible remedies. However, the distributed protocol remains impractical because "condensations" of "transaction-wait-for" graphs make graph updates difficult to perform. Delayed graph updates cause the occurrence of false deadlocks in this as well as in some other deadlock detection protocols for distributed systems. The performance degradation that results from false deadlocks depends on the characteristics of each protocol.     

基于自动删除算法的分布式CFAR检测算法

研究分布式恒虚警(CFAR)检测系统在非均匀干扰背景中进行优化检测.针对多传感器分布式恒虚警检测系统在非均匀干扰背景中容易出现检测概率下降或者虚警率提高的问题,提出了一种基于自动删除算法的分布式恒虚警检测算法.算法是一种基于局部检测统计量的分布式CFAR检测算法,充分利用了局部检测器的观测信息,提高了检测性能,同时采用...     

Local Distributed Deadlock Detection by Cycle Detection and Clusterng

A distributed algorithm for the detection of deadlocks in store-and-forward communication networks is presented. At first, we focus on a static environment and develop an efficient knot detection algorithm for general graphs. The knot detection algorithm uses at most O(n²+ m) messages and O(log (n)) bits of memory to detect all deadlocked nodes in the static network. Using the knot detection algorithm as a building block, a deadlock detection algorithm in a dynamic environment is developed. This algorithm has the following properties: It detects all the nodes which cause the deadlock. The algorithm is triggered only when there is a potential for deadlock and only those nodes which are potentially deadlocked perform the algorithm. The algorithm does not affect other processes at the nodes.     

移动Agent系统的一种分布式死锁检测方案

传统的分布式死锁解决方案不适合于实体在网络中自由移动的MAS系统.本文描述了一种移动Agent系统的分布式死锁算法,使用专职Agent从事死锁检测和解决.该方案的特点是地点参考、拓扑独立、容错、异步操作.文中建立了StochasticPetri Net模型,并使用仿真试验给出它和Diffusion Computation算法的性能比较.     

基于门限自适应的分布式检测融合算法

贝叶斯检测融合策略是一种比较传统的分布式检测融合方法,必须给定待检测现象的先验概率和各局部传感器的虚警概率和漏检概率,而在现实应用中,统计量是未知的或者是随时间变化的.因此,研究了一种纽曼一皮尔逊准则下的门限自适应分布式检测系统的融合算法.算法可根据观测数据,自动在线调整门限,使得局部传感器检测达到最佳,从而提高系统的检测性能.计算机仿真的结果表明,算法能较快地收敛,相对局部传感器,融合中心的检测性能也明显地有了提高.     

一种基于依赖分析的并发程序潜在死锁检测算法

死锁是并发程序特有的一种运行时错误,由于并发程序在执行时的不确定性,死锁的检测和定位是非常困难的.本文提出了一种基于依赖分析的并发程序潜在死锁检测算法,该算法是一种静态分析算法,能检测并发程序中是否存在潜在死锁,并能定位死锁发生时各线程可能被挂起的语句节点.本文给出了算法的形式化定义和时间复杂度分析,实验测试结果表明算法是正确且有效的.     

Protocols for Deadlock Detection in Distributed Database Systems

In distributed databases, deadlocks may occur due to conflicts in data file lockings A system is in a deadlock if and only if there is a directed cycle in its demand graph. However, due to the inherent communication delay in a distributed system, it is not easy to construct a consistent demand graph for a distributed system. In this paper, three deadlock detection protocols are discussed. The first protocol uses two communication phases. The second protocol uses a single communication phase. Based on the second protocol, a one-phase hierarchical deadlock detection protocol is developed.     

Locking and Deadlock Detection in Distributed Data Bases

This paper descrbes two protocols for the detection of deadlocks in distributed data bases–a hierarchically organized one and a distributed one. A graph model which depicts the state of execution of all transactions in the system is used by both protocols. A cycle in this graph is a necessary and sufficient condition for a deadlock to exist. Nevertheless, neither protocol requires that the global graph be built and maintained in order for deadlocks to be detected. In the case of the hierarchical protocol, the communications cost can be optimized if the topology of the hierarachy is appropriately chosen.     

A New Link Failure Resilient Priority Based Fair Mutual Exclusion Algorithm for Distributed Systems

This paper aims towards designing a new token-based mutual exclusion algorithm for distributed systems. In some of the earlier work, token based algorithms for mutual exclusion are proposed for the distributed environment assuming inverted tree topology. In a wireless setup, such a stable, hierarchical topology is quite unrealistic due to frequent link failures. The proposed token-based algorithm works for processes with assigned priorities on any directed graph topology with or without cycles. The proposed algorithm, in spite of considering priorities of processes, ensures liveness in terms of token requests from low priority processes. Moreover, the algorithm keeps control message traffic reasonably low. The simulation results exhibit the performance of the proposed algorithm under varied contexts besides presenting a comparative performance with other recent algorithms for mutual exclusion like FAPP (Fairness Algorithm for Priority Process).     

A Novel Parallel Deadlock Detection Algorithm and Hardware for Multiprocessor System-on-a-Chip

Given the projected dramatic increase in the number of processors and resources in a system-on-a-chip, a quadratic increase in the likelihood of deadlock is predicted due to complex system behavior. To deal with this issue, we here present a novel parallel hardware-oriented deadlock detection algorithm with O(l) deadlock detection and 0(min(m,n)) preparation, where m and n are the numbers of processes and resources, respectively. Our contributions are (i) the first O(l) deadlock detection hardware implementation and (ii) a new algorithmic method of achieving 0(min(m,n)) overall run-time complexity. We implement our algorithm in Verilog HDL and demonstrate that deadlock detection always takes only two clock cycles regardless of the size of a system (i.e., m and n).     

一种基于优先级的网格调度算法

容错机制中基于任务数量的平均调度策略在处理跨度和服务质量方面存在不足,为此,提出一种基于优先级的网格调度算法,进而给出层次式集群系统的设计方案。在任务调度过程中引入任务剩余执行时间、任务价值密度、费用预算以及处理跨度的概念,以缩短任务处理跨度,提高服务质量。实验结果表明,与原机制调度策略和Max-Min算法相比,该算法在任务完成率、价值实现率和处理速率方面具有优势。利用该算法对原机制进行改进,能够有效提高系统的任务执行效率。     

分布式漏洞检测扫描调度算法

网络漏洞扫描器是一个用来自动检查本地或远程主机的安全漏洞的程序.依据漏洞检测的要求和实现的特点,构造一个分布式扫描任务调度模型,提出相应的扫描任务分配算法.该算法将扫描任务分配到与被检测主机同在一个子网的扫描服务器中执行,或将扫描任务尽可能均衡地分配到各个扫描服务器中,从而提高漏洞检测系统的运行效率.最后,从理论上证明该模型和算法的可行性和优越性.     

无线传感网络中基于信用度的分布式目标监测算法

无线传感器网络中的目标监测广泛应用于军事、生态、医疗、安全等领域,具有极强的现实研究意义.传统集中式目标监测算法对融合节点依赖性高、网络健壮性弱、二元决策机制导致误报率高,而且算法对网络覆盖的依赖会导致监测报警盲点的存在.因而,提出了基于信用度的分布式目标监测k-CD算法.算法首先根据邻居信用度对自身信用度进行调整,然后在发现目标的节点之间形成一个虚拟的节点集来完成信用度匹配决策融合,并且通过触发式移动节点来解决网络覆盖导致的盲点问题.仿真结果表明,相对于经典的多数投票决策(MV)算法,k-CD算法平均能在提高35%的监测准确率的同时降低62%的误报率,在不同的网络覆盖情况下网络生命周期也平均能得到44%的延长.     

基于两次应用优先级的GDP时隙分配算法模型

地面等待策略是空中交通流量管理中主要采用的一种方法,文中主要介绍了基于两次应用优先级的GDP时隙分配算法。初次优先级的使用是达到分组的目的,再次应用优先级则是为了解决初次分配后可能存在的在同一分组中航班竞争同一时隙的问题。文中对相应的算法实现做了详细介绍,并对成都双流机场的航班进行了多次仿真实验。同时和单纯的基于优先级的方法进行了对比,验证了该算法的可行性。     

分布式系统死锁的预防、避免和检测

分布式系统涉及到资源和数据的高度共享,从而可能引发死锁。分布式系统的死锁是由于资源和通讯产生的。从分布式系统死锁产生的条件,解决策略,以及分布式系统中死锁预防、避免和检测的各种算法进行了具体阐述。     

基于Petri网合成与化简的分布式数据库系统并发控制的死锁检测

利用模块化设计的思想，首先为分布式数据库系统中各事务的每一种操作(读锁、写锁、解锁)构造一个基本的加权Petri网模型，并给出了加权Petri网共享合成的概念、然后利用共享合成技术，动态地构造各站点的加权Petri网模型，以适应系统的动态变化．此外，本文利用Petri网的化简技术，极大地简化了各站点的Petri网模型，之后利用同步合成技术构造出整个系统的Petri网模型，较好地解决了Petri网的可达性分析中可能出现的状态“爆炸”问题．最后给出了判断整个系统是否出现死锁的充分必要条件．     

Comments on "Protocols for Deadlock Detection in Distributed Database Systems"

The two-phase deadlock detection protocol in the above paperl detects false deadlocks. This is contrary to what the authors claim. The false detection o. f deadlocks is shown using a counterexample.     

A Parallel Deadlock Detection Algorithm with O(1) Overall Run-time Complexity

This article proposes a novel parallel, hardware-oriented deadlock detection algorithm for multiprocessor system-on-chips. The proposed algorithm takes full advantage of hardware parallelism in computation and maintains information needed by deadlock detection through classifying all resource allocation events and performing class specific operations, which together make the overall run-time complexity of the new method O(1). We implement the proposed algorithm in Verilog HDL and demonstrate in the simulation that each algorithm invocation takes at most four clock cycles in hardware.     

一种基于相关性的分布式异常检测算法

提出了一种传感器网络异常检测算法,与传统的基于相邻节点数据对比的检测算法不同,该算法首先在节点内分析数据的时间相关性,仅在发生异常时,上传至簇头节点,分析空间相关性;对于不确定的异常数据,在相邻分簇内,计算数据的相关性.还给出了采用直方图计算均值和分析相关性的方法.实验表明,该算法减少了通信量,提高了异常检测的准确率.