\begin{frame} \frametitle{Deadlock Handling via Wait-for-Graphs} \begin{goal}{Deadlock Detection via Wait-for-Graphs} The system maintains a \emph{waits-for-graph}: \begin{itemize} \item Nodes of the graph are transactions. \item Edge $T_1 \to T_2$ means $T_1$ is blocked by a lock held by $T_2$.\\ \remark{Hence $T_1$ waits for $T_2$ to release the lock.} \end{itemize} \pause\smallskip The system checks periodically for \emph{cycles} in the graph: \begin{itemize} \item If a cycle is detected, then the deadlock is \emph{resolved} by \emph{aborting} one or more transactions. \end{itemize} \end{goal} \pause\smallskip \begin{alertblock}{Selecting the \emph{victim} is a challenge} \begin{itemize} \item Aborting \emph{young} transactions might lead to starvation. The same transaction may be cancelled again and again. \item Aborting \emph{old} transactions may cause a lot of computational investment to be thrown away. \end{itemize} \end{alertblock} \end{frame}