  Modern Internet services commonly replicate critical data across several
geographical locations using state-machine replication (SMR). Due to their
reliance on a leader replica, classical SMR protocols offer limited scalability
and availability in this setting. To solve this problem, recent protocols
follow instead a leaderless approach, in which each replica is able to make
progress using a quorum of its peers. In this paper, we study this new emerging
class of SMR protocols and states some of their limits. We first propose a
framework that captures the essence of leaderless state-machine replication
(Leaderless SMR). Then, we introduce a set of desirable properties for these
protocols: (R)eliability, (O)ptimal (L)atency and (L)oad Balancing. We show
that protocols matching all of the ROLL properties are subject to a trade-off
between performance and reliability. We also establish a lower bound on the
message delay to execute a command in protocols optimal for the ROLL
properties. This lower bound explains the persistent chaining effect observed
in experimental results.
