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.     

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.     

Deadlock Models and a General Algorithm for Distributed Deadlock Detection

This paper deals with the problem of deadlock detection in asynchronous message passing systems in a system model that covers unspecified receptions and non-FIFO channels. It presents a hierarchy of deadlock models and deadlock detection problems. It abstracts deadlocks by a general deadlock model that has the same modeling power as the OR-AND model; however, it has much concise expressive power. An abstract general definition of deadlocks in distributed systems is presented that defines deadlocks independently of the underlying deadlock model. This formulation can be used to design a single distributed deadlock detection algorithm which uniformly addresses all deadlocks in the context of various request models such as AND, OR, AND-OR, and k-out-of-n requests. A simple generalized deadlock detection algorithm that uses a circulating token is presented to illustrate the concept. The algorithm is formally described and proven correct. Moreover, possible refinements of the basic solution concerning improvements of token routing and parallel implementation are outlined and evaluated. Extensions to individual and global termination issues are also addressed. Since the proposed deadlock detection algorithm is designed around the abstract definition of deadlocks, it has some very favorable features.     

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

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

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.     

基于时戳的分布式数据库系统中的死锁预防策略

本文讨论了分布式数据库系统中基于时戳的死锁预防策略,分析了预防死锁问题的两种可行的动态优先级方案——等待一死亡方案和伤害一等待方案,提出了使用时戳的动态优先级死锁预防策略在解决分布式数据库系统并发控制的可行性和有效性,保证了产生死锁问题的条件不能发生,从而有效的预防了死锁,并给出了相应的实例。     

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 Priority Based Distributed Deadlock Detection Algorithm

Deadlock handling is an important component of transaction management in a database system. In this paper, we contribute to the development of techniques for transaction management by presenting an algorithm for detecting deadlocks in a distributed database system. The algorithm uses priorities for transactions to minimize the number of messages initiated for detecting deadlocks. It does not construct any wait-for graph but detects cycles by an edge-chasing method. It does not detect any phantom deadlock (in the absence of failures), and for the resolution of deadlocks it does not need any extra computation. The algorithm also incorporates a post-resolution computation that leaves information characterizing dependence relations of remaining transactions of the deadlock cycle in the system, and this will help in detecting and resolving deadlocks which may arise in the future. An interesting aspect of this algorithm is that it is possible to compute the exact number of messages generated for a given deadlock configuration. The complexity is comparable to the best algorithm reported. We first present a basic algorithm and then extend it to take into account shared and exclusive lock modes, simultaneous acquisition of multiple locks, and nested transactions.     

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

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

分布式多媒体数据库系统

着重分析分布式多媒体数据库系统的特有问题,包括实时性、时空同步以及服务质量的描述与实现等.给出了解决这些问题的策略和方法.研究了各种不同的实现途径——远程调用、中间件和Agent构造的方式;指出了这些实现方法的优点及其不足.     

On Characterization and Correctness of Distributed Deadlock Detection

Distributed deadlock detection requires identifying the presence of certain properties in the global state of distributed systems. Distributed deadlock detection is complicated due to the lack of both global memory and a common physical clock, and due to unpredictable message delays. We characterize the formation and detection of distributed deadlocks in terms of the contents of local memory of distributed nodes/sites. We describe how the interaction between deadlock detection and deadlock resolution can lead to the detection of false deadlocks that are impossible to avoid due to inherent system limitations. We define shadow, phantom, and pseudo deadlocks in the proposed framework. We give examples of existing incorrect deadlock detection algorithms to illustrate how they violate the developed requirements for distributed deadlock detection. The characterization provides an insight into the properties of distributed deadlocks, expresses inherent limitations of distributed deadlock detection, and yields new correctness criteria for distributed deadlock detection algorithms.     

浅谈分布式数据库系统查询优化

分布式数据库系统的查询优化,就是要寻找执行代价最小的查询执行策略,使系统执行效率达到最高。我们在应用中需要选择适当优化方法,在执行代价和便捷度之间得到最佳执行方案。     

分布式锁的Petri网建模及死锁检测

分布式锁管理DLM细化了锁模式的粒度,使得分布式系统具有更高的并发性,但死锁检测等锁的管理过程却更加复杂了,Petri网的应用能很好地解决该问题。为分布式锁建立Petri网模型,通过化简和合成建立系统的Petri网模型,借助Petri网的可达标识图实时检测出分布式系统的死锁状态,并查找死锁进程。     

数据库并发操作的可串行化调度与死锁检测算法

封锁与可串行化调度是数据库并发操作采取的两种主要措施。判断一个调度是否可串行化调度的最有效方法是两段锁协议。但是,一方面,事务遵守两段锁协议只是可串行化调度的充分条件而不是必要条件;另一方面,遵守两段锁协议的事务仍可能发生死锁。文中给出了一种算法,利用该算法,不仅可判断出一个调度是否为可串行化调度,而且可判断出该调度是否会发生死锁。     

Adaptive Algorithms for Join Processing in Distributed Database Systems

Distributed query processing algorithms usually perform data reduction by using a semijoin program, but the problem with these approaches is that they still require an explicit join of the reduced relations in the final phase. We introduce an efficient algorithm for join processing in distributed database systems that makes use of bipartite graphs in order to reduce data communication costs and local processing costs. The bipartite graphs represent the tuples that can be joined in two relations taking also into account the reduction state of the relations. This algorithm fully reduces the relations at each site. We then present an adaptive algorithm for response time optimization that takes into account the system configuration, i.e., the additional resources available and the data characteristics, in order to select the best strategy for response time minimization. We also report on the results of a set of experiments which show that our algorithms outperform a number of the recently proposed methods for total processing time and response time minimization.     

Evolutionary Algorithms for Allocating Data in Distributed Database Systems

A major cost in executing queries in a distributed database system is the data transfer cost incurred in transferring relations (fragments) accessed by a query from different sites to the site where the query is initiated. The objective of a data allocation algorithm is to determine an assignment of fragments at different sites so as to minimize the total data transfer cost incurred in executing a set of queries. This is equivalent to minimizing the average query execution time, which is of primary importance in a wide class of distributed conventional as well as multimedia database systems. The data allocation problem, however, is NP-complete, and thus requires fast heuristics to generate efficient solutions. Furthermore, the optimal allocation of database objects highly depends on the query execution strategy employed by a distributed database system, and the given query execution strategy usually assumes an allocation of the fragments. We develop a site-independent fragment dependency graph representation to model the dependencies among the fragments accessed by a query, and use it to formulate and tackle data allocation problems for distributed database systems based on query-site and move-small query execution strategies. We have designed and evaluated evolutionary algorithms for data allocation for distributed database systems.     

An Information-Based Model for Failure-Handling in Distributed Database Systems

We consider the failure atomicity problem of distributed transactions in conjunction with the maximization of database availability. We propose a new information-based model for the distributed transaction-execution, which explicitly expresses the information at each stage during a protocol. In addition to rederiving certain existing results, we prove a fundamental relation among the site failures and the network partitioning. We propose a realistic model for site failures under which we show that the costs of commit and termination protocols can be greatly reduced. Finally, we explore the possible recovery strategies for a failed site and show how they are improved under our site failure model.     

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

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