  We study the fault-tolerant variant of the online bin packing problem.
Similar to the classic bin packing problem, an online sequence of items of
various sizes should be packed into a minimum number of bins of uniform
capacity. For applications such as server consolidation, where bins represent
servers and items represent jobs of different loads, it is required to maintain
fault-tolerant solutions. In a fault-tolerant packing, any job is replicated
into f+1 servers, for some integer f > 1, so that the failure of up to f
servers does not interrupt service. We build over a practical model introduced
by Li and Tang [SPAA 2017] in which each job of load $x$ has a primary replica
of load $x$ and $f$ standby replicas, each of load $x/\eta$, where $\eta >1$ is
a parameter of the problem. Upon failure of up to $f$ servers, any primary
replica in a failed bin should be replaced by one of its standby replicas so
that the extra load of the new primary replica does not cause an overflow in
its bin. We study a general setting in which bins might fail while the input is
still being revealed. Our main contribution is an algorithm, named
Harmonic-Stretch, which maintains fault-tolerant packings under this general
setting. We prove that Harmonic-Stretch has an asymptotic competitive ratio of
at most 1.75. This is an improvement over the best existing asymptotic
competitive ratio 2 of an algorithm by Li and Tang [TPDS 2020], which works
under a model in which bins fail only after all items are packed.
