  We consider replication-based distributed storage systems in which each node
stores the same quantum of data and each data bit stored has the same
replication factor across the nodes. Such systems are referred to as balanced
distributed databases. When existing nodes leave or new nodes are added to this
system, the balanced nature of the database is lost, either due to the
reduction in the replication factor, or the non-uniformity of the storage at
the nodes. This triggers a rebalancing algorithm, that exchanges data between
the nodes so that the balance of the database is reinstated. The goal is then
to design rebalancing schemes with minimal communication load. In a recent work
by Krishnan et al., coded transmissions were used to rebalance a carefully
designed distributed database from a node removal or addition. These coded
rebalancing schemes have optimal communication load, however, require the
file-size to be at least exponential in the system parameters. In this work, we
consider a cyclic balanced database (where data is cyclically placed in the
system nodes) and present coded rebalancing schemes for node removal and
addition in such a database. These databases (and the associated rebalancing
schemes) require the file-size to be only cubic in the number of nodes in the
system. We bound the advantage of our node removal rebalancing scheme over the
uncoded scheme, and show that our scheme has a smaller communication load. In
the node addition scenario, the rebalancing scheme presented is a simple
uncoded scheme, which we show has optimal load.
