A Distributed Deadlock Detection and Resolution Algorithm Based on a Hybrid Graph Construction Probe Generation Scheme = 대기그래프와 프로브 생성에 기초한 교착상태의 분산 검출 및 회복 알고리즘

국문 초록 (Abstract)

본 논문은 분산 데이타베이스 시스템에서의 교착상태 검출 및 회복을 위한 주기적 알고리즘을 제시한다. 이 알고리즘은 명시적, 암시적 교착 상태들을 초기에 검출할 수 있도록 하며 이를 위해 각 사이트에 확정된 트랜잭션 대기 그래프(TWFG)를 유지한다. 확장된 트랜잭션 대기 그래프는 로크 정보 뿐만 아니라 트랜잭션 에이젼트들간의 메시지-대기 정보 및 주종 관계에 대한 정보, 그리고 트랜잭션 완료 프로토콜에 관련된 트랜잭션들의 상태정보들도 포함한다. 각 사이트 간 메시지의 수효를 최소로 가진 전역 교착상태를 검출하고 회복하기 위해서는 프로브 생성 기법을 변형하여 사용하며 제시된 알고니즘은 각 사이트에 두개의 메모리 풀을 유지한다. 하나의 풀은 수신한 프로브들을 유지하며, 다른 하나의 풀은 보낸 프로브들의 수신에 대한 정보를 유지한다. 각 지역 사이트의 트랜잭션 대기 그래프에 포함된 정보와 수령한 프로브드들을 사용하여 주기적으로 교착상태를 검사한다. 송신한 프로브에 대한 수신 정보는 동일한 프로브의 전송를 피하기 위해 사용하며 또한 대항 프로브들을 전송하기 위해서도 사용한다. 이 알고리즘은 다중 사이트에서 트랜잭션들의 병렬수행을 허가하며 다중 로크 모드 및 로크 변환을 지원한다.

다국어 초록 (Multilingual Abstract)

We present a periodic algorithm for deadlock detection and resolution in distributed database systems, which allows for early detection of explicit and implicit deadlocks. Our algorithm uses an augmented transaction wait-for graph (TWFG) at each site, which contains in addition to lock-wait information, also information about message-wait and master-slave relationships among agents of a transaction, and status of transactions with respect to the commitment protocol. In order to detect and resolve global deadlocks with a minimal number of inter-site messages we adopt a modified version of the probe generation scheme such that two pools are maintained at each site. One pool keeps probes received, while the other keeps the receipts of probes sent. Periodically, we check for deadlocks by using the information contained in the local TWFGs and the probes received. The receipts of probes sent are used to avoid retransmission of the same probe and also to transmit antiprobes. Our algorithm allows for parallel execution of transactions at multiple sites and supports multiple modes of locks and lock conversion.