\documentclass{article}
\input{6897-preamble}

\begin{document}
\psetnum{3}
\date{2004/02/23}

\begin{pset}
  Suppose we have a data structure that performs operations in time
  $t$ and requires a global rebuilding procedure consisting of $m$
  steps of time $t$ to be performed every $m$ operations. We give a
  deamortization of the data structure that performs the same
  operations using $\bigO{t}$ worst-case runtime.

  To perform the deamortization, we maintain two copies of the data
  structure --- a primary structure and an auxiliary structure --- and
  perform operations on them independently. We also maintain a counter
  of the number of operations that have been performed in the current
  phase, and a FIFO queue to store previous requests.

  \paragraph{Initial phase}
  When we begin the algorithm, we initialize the primary data
  structure, and ignore the auxiliary structure for now. As we receive
  requests for operations, we perform them on the primary structure
  (using runtime $t$), and increment the counter. When the counter
  reaches $\nicefrac{m}{2}$, the primary structure will have had
  $\nicefrac{m}{2}$ operations performed on it. We then proceed to the
  rebuilding phase.


  \paragraph{Rebuilding phase}
  The rebuilding phase is always entered when the primary data structure
  has had $\nicefrac{m}{2}$ operations performed on it since the last
  rebuild. Upon entering the phase, we replace the auxiliary data
  structure with a direct copy of the primary structure. As each request
  for operations is received, we perform the request on the primary
  structure (using runtime $t$) to generate the result, and perform
  four rebuilding operations on the auxiliary structure (using runtime
  $4t$). We also add all requests received during this phase to a
  queue. Once we have performed $\nicefrac{m}{4}$ operations, we
  proceed to the replay phase. At this point, $\nicefrac{3m}{4}$
  operations have been performed on the primary structure since it was
  rebuilt. Moreover, the auxiliary data structure has been completely
  rebuilt.

  \paragraph{Replay phase}
  At the beginning of the replay phase, the primary data structure has
  had $\nicefrac{3m}{4}$ operations performed on it since its last
  rebuild, the auxiliary structure has just been rebuilt, and the
  queue contains $\nicefrac{m}{4}$ requests. As each new request is
  received, we perform the request on the primary structure to obtain the
  result, add the new request to the end of the queue, and perform the
  first two requests from the front of the queue (again requiring only
  $\bigO{t}$ time). We perform $\nicefrac{m}{4}$ requests in this
  phase. Note that after each request, the length of the queue
  decreases by 1, so at the end of the phase all operations in the
  queue will be performed. The auxiliary structure will have performed all
  $\nicefrac{m}{2}$ of the operations that have been requested since
  the rebuild took place. So we can now replace the primary structure
  with the auxiliary structure, and proceed to the rebuilding phase
  again.

  \paragraph{}
  Note that this algorithm performs all operations in worst-case
  $\bigO{t}$ time, and never performs more than $m$ operations on a
  copy of the structure between rebuilds. The correctness of the
  algorithm follows from the fact that the preconditions and
  postconditions of each phase are met. 
\end{pset}
\end{document}