  Reconfigurable state machine replication is an important enabler of
elasticity for replicated cloud services, which must be able to dynamically
adjust their size as a function of changing load and resource availability. We
introduce a new generic framework to allow the reconfigurable state machine
implementation to be derived from a collection of arbitrary non-reconfigurable
state machines. Our reduction framework follows the black box approach, and
does not make any assumptions with respect to its execution environment apart
from reliable channels. It allows higher-level services to leverage speculative
command execution to ensure uninterrupted progress during the reconfiguration
periods as well as in situations where failures prevent the reconfiguration
agreement from being reached in a timely fashion. We apply our framework to
obtain a reconfigurable speculative state machine from the non-reconfigurable
Paxos implementation, and analyze its performance on a realistic distributed
testbed. Our results show that our framework incurs negligible overheads in the
absence of reconfiguration, and allows steady throughput to be maintained
throughout the reconfiguration periods.
