@techreport{TR-IC-99-22,
  number = {IC-99-22},
  author = {Islene Calciolari Garcia and Luiz Eduardo Buzato},
  title = {Checkpointing using Local Knowledge about Recovery Lines},
  month = {November},
  year = {1999}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 16 pages.
    \par\selectlanguage{english}\textbf{Abstract}
      A recovery line is the most recent consistent global checkpoint
      from which a distributed computation can be restarted after a
      failure. This paper presents a new quasi-synchronous
      checkpointing protocol where processes propagate their local
      knowledge about the recovery line, named PRL.
      \par
      Protocols that enforce rollback-dependency trackability (RDT)
      are domino-effect free and are usually based on vector clocks.
      Protocols that avoid the domino effect without enforcing RDT are
      usually index-based. The protocol proposed by Baldoni, Quaglia,
      and Ciciani (BQC) was the first non-RDT domino-effect free
      protocol to use a vector clock. In BQC, each process keeps and
      propagates a matrix of $n \times n$ of integers, where $n$ is
      the number of processes in the computation. PRL is also
      vector-clock based, domino-effect free, and non-RDT, but lowers
      the complexity of the required control information from $O(n^2)$
      to $O(n)$. We present theoretical and simulation results giving
      evidence that PRL reduces the number of induced checkpoints in
      comparison with BQC.
  }
}