  Replicated services are inherently vulnerable to failures and security
breaches. In a long-running system, it is, therefore, indispensable to maintain
a reconfiguration mechanism that would replace faulty replicas with correct
ones. An important challenge is to enable reconfiguration without affecting the
availability and consistency of the replicated data: the clients should be able
to get correct service even when the set of service replicas is being updated.
  In this paper, we address the problem of reconfiguration in the presence of
Byzantine failures: faulty replicas or clients may arbitrarily deviate from
their expected behavior. We describe a generic technique for building
asynchronous and Byzantine fault-tolerant reconfigurable objects: clients can
manipulate the object data and issue reconfiguration calls without reaching
consensus on the current configuration. With the help of forward-secure digital
signatures, our solution makes sure that superseded and possibly compromised
configurations are harmless, that slow clients cannot be fooled into reading
stale data, and that Byzantine clients cannot cause a denial of service by
flooding the system with reconfiguration requests. Our approach is modular and
based on dynamic Byzantine lattice agreement abstraction, and we discuss how to
extend it to enable Byzantine fault-tolerant implementations of a large class
of reconfigurable replicated services.
