A fault-tolerant memory device provided with a variable domain redundancy replacement (VDRR) arrangement is described. The memory device includes: a plurality of primary memory arrays; a plurality of domains having at least portions of one domain common to another domain to form an overlapped domain area, and at least one of the domains overlapping portions of at least two of the primary memory arrays; redundancy units, coupled to each of the domains, for replacing faults contained within each of the domains; control circuitry for directing at least one of the faults within one of the domains to be replaced with the redundancy units, wherein at least one other fault of the one domain is replaced by the redundancy unit coupled to another of the domains, if the at least one other fault is positioned within the overlapped domain area. Each redundancy unit supporting the primary memory arrays includes a plurality of redundant elements. Unlike the conventional fixed domain redundancy replacement scheme, RUs are assigned to at least two variable domains, wherein at least a portion of the domain is common to that of another domain. The VDRR makes it possible to choose the most effective domain, and in particular, a smaller domain for repairing a random fault or a larger domain for repairing a clustered faults.