We consider a geo-distributed system consisting of a set of data centers
\(\mathcal {D}=\lbrace 1, \dots , D\rbrace \)  that manage a large set of data items. A data item is
uniquely identified by its key. For scalability, the key space is split
into a set of logical partitions \(\mathcal {P}= \lbrace 1, \ldots , N\rbrace \) . Each data
center stores replicas of all partitions, scattered among its servers.
We let \(p ^m_d\)  be the replica of partition \(m\)  at data center \(d\) , and
we refer to replicas of the same partition as sibling replicas.
As is standard, we assume that \(D = 2f+1\)  and at most \(f\)  data centers may fail.
We call a data center that does not fail correct. If a data center fails,
all partition replicas it stores become unavailable. For simplicity, we do not
consider the failures of individual replicas within a data center: these can be
masked using standard state-machine replication protocols executing within a
data center [1]}, [2]}.
