We show how multilayer optical-interconnect-based digital logic systems can be made fault-tolerant by distributed redundancy techniques implementable at the gate level, while incurring the expense of an increased number of gates with greater individual fan-in and fan-out. We demonstrate that braided logical interconnections between redundantly doubled, tripled, and quadrupled NOR gates enable the correction of device and interconnection errors. We present an extrapolated error analysis for the quadding, doubling, and tripling schemes, which shows the quadratic and cubic dependence of the system error on device error rates, in comparison with the linear relationship of a nonredundant system. Because the interconnections between the braided circuits are quite regular, they appear to be very amenable to optical implementations, and with the appropriate choice of device topology employing sparse device placement they are compatible with the regular, layered structure of conventional shift-invariant digital optical computer interconnects, without a penalty in circuit depth or latency. We show device topologies and interconnection architectures for the optical implementation of a fault-tolerant quadded programmable two-shuffle interconnection system that use holographic shift-invariant interconnects. Using these redundant optical logic schemes with only moderate device error probabilities, extremely low system error rates can be achieved.