@techreport{TR-IC-15-03,
   number = {IC-15-03},
   author  =  {Daniel  {Cason}  and  Parisa  J.  {Marandi} and Luiz E.
                   {Buzato} and Fernando {Pedone}},
   title = {Chasing the tail of atomic broadcast protocols},
   month = {May},
   year = {2015},
   institution = {Institute of Computing, University of Campinas},
   note = {In English, 20 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       Many  applications  today  rely  on  multiple  services,  whose 
       results  are  combined  to  form the application's response. In
       such  contexts,  the  most  unreliable  service and the slowest
       service  determine  the  application's reliability and response
       time,   respectively.   State-machine  replication  and  atomic 
       broadcast   are   fundamental   abstractions  to  build  highly 
       available  services.  In  this  paper,  we consider the latency
       variability  of  atomic  broadcast protocols. This is important
       because  atomic  broadcast  has a direct impact on the response
       time  of  services.  We  study  four  high  performance  atomic 
       broadcast  protocols  representative  of  different  classes of
       protocol   design   and   characterize   their   latency   tail  
       distribution under different workloads. Next, we assess how key
       design features of each protocol can possibly be related to the
       observed  latency  tail distributions. Our observations hint at
       request  batching  as a simple yet effective way to shorten the
       latency  tails of some of the studied protocols; an improvement
       within  the  reach  of  application  implementers.  Indeed, our
       observation  is  not only verified experimentally, it allows us
       to  assess  which of the protocol's key design principles favor
       the construction of latency predictable protocols.
  }
}