Analysis of Queue-batch Algorithm Clause Samples

Analysis of Queue-batch Algorithm. The main idea of the Queue-batch algorithm exploits the idle rekey interval to pre-process certain rekeying opera- tions. When we compare its performance with the Rebuild or Batch algorithms, we only need to consider the rekey op- erations occurring at the beginning of each rekey interval. When , Queue-batch is equivalent to Batch in the pure leave scenario. For , the number of re- newed nodes in Queue-batch during the Queue-merge phase is equivalent to that of Batch when . Thus, the ex- pected number of renewed nodes is if and if and