Performaance Analysis of Distributed Deadlock Detection and Resolution Algorithms based on a Hybrid Wait-for Graph and Probe Generation Scheme

Abstract

본 논문은 분산 데이타베이스 시스템에서의 교착상태 검출 및 회복을 위한 연속 알고리즘을 제시한다. 이 알고리즘은 각 지역 사이트에 확장된 트랜잭션 대기 그래프를 유지하며 각 사이트간 메세지 전달의 수효를 최소화하기 위해 우선순위에 기초한 프로브 생성 기법을 변형하여 사용한다. 확장된 트랜잭션 대기 그래프는 로크-대기 정보 뿐만 아니라 트랜잭션 에이전트들간의 메세지-대기 정보, 수신한 프로브들, 그리고 트랜잭션 사이의 이행-대기 관계들에 관한 정보도 포함한다. 전역 교착상태는 어떤 프로브나 이행-대기 관계가 그 프로브를 개시한 트랜잭션의 어떤 에이전트로 전파될 때마다 선언된다. 교착상태의 거짓선언 확률을 최소화하기 위하여 제시한 알고리즘에 대하여 두가지 확장을 가했다. 이들은 교착상태 선언시 이의 정당성을 검증하는 부가적인 절차를 추가한 것이다. 세가지 제안한 방법의 성능을 시뮬레이션을 통하여 비교분석 하였다.

We present a continuous algorithm for deadlock detection and resolution in distributed database systems. our algorithm maintains at each local site an augmented transaction wait-for graph and used a modified priority-based probe generation scheme in order to minimize the number of intersite messages sent. The augmented transaction-wait for graph contains, in addition to lock-wait information, also information about message-wait relationships among the agents of a transaction, received probes and transitive wait-for relationships among transactions. Global deadlocks are declared whenerver a probe or transitive-wait relationship is propagated to an agent of the transaction that initiated the probe. In order to minimize the probability of false deadlocks, two extensions to the original algorithm are presented which make use of an additional validation procedure. We report on the results of simulation experiments that compare the performance of the three proposed schemes for deadlock detection and resolution.

We present a continuous algorithm for deadlock detection and resolution in distributed database systems. our algorithm maintains at each local site an augmented transaction wait-for graph and used a modified priority-based probe generation scheme in order to minimize the number of intersite messages sent. The augmented transaction-wait for graph contains, in addition to lock-wait information, also information about message-wait relationships among the agents of a transaction, received probes and transitive wait-for relationships among transactions. Global deadlocks are declared whenerver a probe or transitive-wait relationship is propagated to an agent of the transaction that initiated the probe. In order to minimize the probability of false deadlocks, two extensions to the original algorithm are presented which make use of an additional validation procedure. We report on the results of simulation experiments that compare the performance of the three proposed schemes for deadlock detection and resolution.