Make rebalance take a seed

(cherry picked from commit 9ee14f43190366e7a463c22e044ea98ac52ed1aa)