Redundancy — TMR (triple modular redundancy), voting logic

5.5.25 · Coding › Embedded Systems & Real-Time Software

Overview

Triple Modular Redundancy (TMR) ek fault-tolerance technique hai jisme teen identical modules ek hi computation ko parallel mein execute karte hain, aur ek voter majority output select karta hai. Yeh aerospace, medical devices, aur autonomous vehicles jaise safety-critical systems mein single-point failures ko mask karta hai.

TMR kyun zaroori hai: Cosmic radiation ya hardware aging se ek single bit-flip ek spacecraft computer ko crash kar sakta hai. TMR ensure karta hai ki ek faulty module system output ko compromise na kar sake.

[!intuition] Core Idea

Teen ghariyon ke baare mein socho jo time dikhate hain. Agar ek toot jaaye aur galat time dikhaye, toh tum dono ghariyon par bharosa kar sakte ho jo agree karte hain. TMR computations ke saath yehi karta hai:

• Redundancy: Ek hi task ko 3 independent hardware/software modules par run karo
• Voting: Outputs compare karo; majority (2-out-of-3) jeet jaata hai
• Masking: Faulty module ki error ko system se chhupaao

Key insight: TMR space (3× hardware) aur power (3× computation) ko reliability ke liye trade karta hai (1 fault mask karta hai). Yeh detect nahi kar sakta ki kaunsa module fail hua, sirf yeh ki ek disagree karta hai.

[!definition] Formal Definition

Ek TMR system mein hota hai:

1. Teen identical modules $M_1,M_2,M_3$ jo function $f(x)$ compute karte hain
2. Ek voter $V$ jo majority function apply karta hai: $V(y_1,y_2,y_3)=\text{majority}(y_1,y_2,y_3)$ jahan $y_i=M_i(x)$ module $i$ ka output hai

Assumptions:

• Modules independently fail hote hain (koi common-cause failure nahi)
• Voter ultra-reliable hai (aksar hardened ya redundant khud)
• Failures fail-silent hain (ek faulty component output produce karna band kar deta hai ya error signal karta hai rather than galat data emit karna; contrast with ek fail-incorrect module jo plausible but galat values output karta rehta hai, jo voter ke liye handle karna mushkil hai)

[!formula] Reliability Derivation

Setup: Har module ki reliability $R$ hai (time $t$ mein correct operation ki probability). Exponential failure assume karo: $R(t)=e^{-\lambda t}$ jahan $\lambda$ failure rate hai.

Single Module System

$R_{\text{single}}(t)=R(t)=e^{-\lambda t}$

Kyun? Sirf ek module hai; agar yeh fail ho, system fail ho jaata hai. $R$ hi $R(t)=e^{-\lambda t}$ hai—koi extra factor nahi hai.

TMR System

System tab kaam karta hai jab 3 mein se kam se kam 2 modules kaam karein (voter majority pick karta hai).

Step 1: Probability ki teeno kaam karein: $P(\text{all 3 work})=R^3$

Kyun? Independent failures multiply hoti hain: $R\times R\times R$.

Step 2: Exactly 2 ke kaam karne ki probability (ek fail ho):

• Choose karo kaun se 2 kaam karein: $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3$ tarike
• Har scenario: $R^2(1-R)$ (do kaam karein, ek fail ho) $P(\text{exactly 2 work})=3R^2(1-R)$

Yeh step kyun? Binomial probability: 3 trials mein se 2 successes pick karo.

Step 3: Total TMR reliability: $R_{\text{TMR}}(t)=R^3+3R^2(1-R)=3R^2-2R^3$

Simplify: $R_{\text{TMR}}(t)=R^2(3-2R)$

Interpretation:

• Agar $R=0.9$: Single module $R_{\text{single}}=0.9$, TMR $R_{\text{TMR}}=0.81\times 1.2=0.972$ ✅ Behtar!
• Agar $R<0.5$: TMR single module se bura hai (unreliable modules good wale ko outvote karte hain)

Critical threshold: TMR sirf tab help karta hai jab $R>0.5$ (modules fail hone se zyada reliable hon).

[!example] Example 1: Sensor Reading Voter

Scenario: Teen temperature sensors ek furnace read kar rahe hain. Outputs: 850°C, 850°C, 920°C.

Voter logic (software):

def majority_vote(vals):
    """Returns majority value if 2+ agree, else None"""
    if vals[0] == vals[1] or vals[0] == vals[2]:
        return vals[0]
    elif vals[1] == vals[2]:
        return vals[1]
    else:
        return None  # All disagree - catastrophic failure
 
sensors = [850, 850, 920]
output = majority_vote(sensors)  # Returns 850

Yeh step kyun?

• Pair-wise compare karo: agar koi bhi do agree karein, woh majority hai
• Agar teeno disagree karein, TMR decide nahi kar sakta (higher redundancy chahiye jaise 5-modular)

Real-world: 920°C sensor mein likely bias fault hai (calibration drift). Voter use mask karta hai; system 850°C ke saath aage badhta hai.

[!example] Example 2: Critical Computation in Flight Control

Scenario: Aileron deflection angle compute karo $\delta =K\cdot ({\theta }_{\text{desired}}-{\theta }_{\text{actual}})$.

Modules:

• Module 1: ${\delta }_1=5.2°$
• Module 2: ${\delta }_2=5.2°$
• Module 3: ${\delta }_3=-1.8°$ (hardware glitch ne sign bit flip kiya)

Voter (hardware comparator):

• Bit-by-bit equality check karta hai
• ${\delta }_1={\delta }_2\ne {\delta }_3$ → Output $5.2°$

Yeh step kyun? Hardware voters bit-level comparison use karte hain (floating-point equality se faster). Agar koi bhi do outputs exactly match karein, woh value actuators ko bhejo.

Consequence: Aircraft stable roll maintain karta hai; faulty module mask ho jaata hai. Ground diagnostics baad mein Module 3 ko replacement ke liye identify karte hain.

[!example] Example 3: Voter Failure Modes

Scenario: Teeno modules alag-alag values output karte hain: 100, 105, 110 (sensor noise ke andar).

Problem: Strict equality voting fail ho jaata hai. Approximate voting chahiye:

def approximate_vote(vals, tolerance=5):
    """Majority within tolerance"""
    for i in range(len(vals)):
        matches = sum(1 for v in vals if abs(v - vals[i]) <= tolerance)
        if matches >= 2:
            return vals[i]
    return None  # No consensus
 
sensors = [100, 105, 110]
output = approximate_vote(sensors, tolerance=10)  # Returns 100 (first in majority)

Yeh step kyun? Analog sensors mein noise hota hai. Exact matching bahut strict hai; hum tolerance window use karke "close enough" values par vote karte hain.

Trade-off: Tolerance bahut bada → real faults mask ho jaayein. Tolerance bahut chhota → false disagreements.

[!mistake] Common Mistakes

Mistake 1: "TMR hamesha reliability improve karta hai"

Kyun sahi lagta hai: Zyada redundancy = zyada safety, sahi?

Kyun galat hai: Agar module reliability $R<0.5$ (kaam karne se zyada fail hone ki probability), TMR single module se bura hai.

Math:

• Single: $R=0.4$
• TMR: $R_{\text{TMR}}=3(0.4{)}^2-2(0.4{)}^3=0.48-0.128=0.352$ ❌ Bura!

Kyun? Do unreliable modules ek achhe module ko aksar outvote karte hain rather than teeno kaam karein.

Fix: TMR sirf tab use karo jab $R>0.5$. Unreliable components ke liye, pehle base reliability fix karo (behtar hardware, screening) phir redundancy add karo.

Mistake 2: "Voter sirf ek OR gate hai"

Kyun sahi lagta hai: OR gates simple hote hain; agar koi bhi module kaam kare, output accha hai.

Kyun galat hai: OR faulty output paas kar dega. Hume majority chahiye, na ki any:

Yeh step kyun? OR gate 1 output karta hai agar koi bhi input 1 ho (fault tolerance ke liye bekaar). Majority 1 output karta hai sirf jab zyaadatar inputs 1 hon (2 ya zyada).

Fix: Majority gate use karo (2-out-of-3 logic): $V=(M_1\cdot M_2)+(M_2\cdot M_3)+(M_1\cdot M_3)$.

Mistake 3: "TMR detect karta hai ki kaunsa module fail hua"

Kyun sahi lagta hai: Teen modules vote karte hain; hum jaante hain do agree kiye, toh teesra faulty hoga.

Kyun galat hai: TMR sirf faults ko mask karta hai, diagnose nahi karta. Tum jaante ho koi galat hai, lekin kaun nahi (jab tak comparison logic add na karo).

Example:

• Outputs: 50, 50, 75
• Voter: 50 pick karta hai (majority)
• Sawaal: Kya Module 3 broken hai, ya Modules 1 & 2 dono identically broken hain (common-cause)?

Fix: Self-checking pairs ya watchdog timers add karo faulty modules ko maintenance ke liye identify karne ke liye. TMR + diagnostics = robust system.

[!formula] Voter Logic Design

Boolean Majority Function (Digital)

Binary outputs $M_1,M_2,M_3\in \{0,1\}$ ke liye:

$V=M_1{M}_2+M_2{M}_3+M_1{M}_3$

Derivation:

• Output 1 hai agar kam se kam do inputs 1 hon
• Truth table approach:
  • $(M_1=1,M_2=1,M_3=?)$: Hamesha 1 → $M_1{M}_2$
  • $(M_1=1,M_2=?,M_3=1)$: Hamesha 1 → $M_1{M}_3$
  • $(M_1=?,M_2=1,M_3=1)$: Hamesha 1 → $M_2{M}_3$
• Inhe OR karo (agar koi bhi pair true ho, output true hai)

Yeh step kyun? Har product term ek pair ke agree karne ko represent karta hai. Inhe OR karna "koi bhi do agree karein" ko capture karta hai.

Hardware: 3 AND gates + 1 OR gate se implement karo. Propagation delay: 2 gate delays.

Analog Voter (Median Filter)

Continuous outputs $y_1,y_2,y_3\in \mathbb{R}$ ke liye:

$V=\text{median}(y_1,y_2,y_3)$

Median kyun, average kyun nahi?

• Average: $(100+100+1000)/3=400$ → faulty outlier result bigaar deta hai
• Median: $\text{median}(100,100,1000)=100$ → outlier ignore ho jaata hai ✅

Algorithm:

1. Values sort karo: $y_{\text{sorted}}$
2. Middle pick karo: $y_{\text{sorted}}[1]$

Hardware: Min/max find karne ke liye analog comparator circuits use karo, phir compute karo median = $\max (\min (y_1,y_2),\min (y_2,y_3),\min (y_1,y_3))$.

[!example] Example 4: Real-Time Voter Timing

Scenario: Flight control 100 Hz (10 ms period) par run kar raha hai. TMR modules ko deadline ke andar complete + vote karna hai.

Timing breakdown:

• Module computation: 3 ms each (parallel)
• Voter comparison: 0.5 ms
• Total: $\max (3,3,3)+0.5=3.5$ ms ✅ (10 ms ke andar)

Yeh step kyun? Parallel execution ka matlab hum sabse dheeme module ka wait karte hain, sum ka nahi. Voter serial delay add karta hai.

Failure case: Agar ek module hang ho jaaye (infinite loop), hume timeout chahiye:

import multiprocessing
 
def compute_with_timeout(func, args, timeout_ms):
    # Shared queue lets the child return its actual result
    q = multiprocessing.Queue()
 
    def worker(q, args):
        q.put(func(*args))
 
    p = multiprocessing.Process(target=worker, args=(q, args))
    p.start()
    p.join(timeout_ms / 1000.0)
    if p.is_alive():
        p.terminate()      # Kill the hung module
        p.join()
        return None        # Fail-silent: no output within deadline
    return q.get()         # Retrieve the module's real computed result

Kyun? Agar ek module time par respond nahi karta, use failed treat karo (None return karta hai). Result ko child process se shared Queue ke zariye wapas lena hota hai — doosre process mein ek plain function call seedha value return nahi kar sakta. Voter phir baaki do outputs use karta hai.

[!mnemonic] TMR Memory Hook

"Two Trusty, reject the Rogue"

• Two modules agree karein? Unpar Trust karo.
• Rogue outlier ko Reject karo.

Visual: Teen guards ka imagine karo jo "friend ya foe" par vote kar rahe hain. Do "friend" kehte hain → majority jeet jaati hai, chahe teesra guard confused ho.

[!recall]- Feynman Explanation (ELI12)

Socho tum math ka test de rahe ho, aur sure nahi ho ki tumhara answer sahi hai. Toh tum teen doston se kehte ho same problem solve karne ko. Agar do dost same answer laayein, tum uss par trust karte ho. Agar ek dost kuch bilkul alag laaya, shayad usne galti ki — lekin tum safe ho kyunki baaki do agree karte hain!

Isi tarah computers rockets ya hospital machines mein safe rehte hain. Woh same calculation teen baar teen alag "mini-computers" par run karte hain. Agar ek mini-computer toot jaaye (shayad ek tiny wire space radiation se zap ho gayi!), baaki do phir bhi kaam karte hain aur correct answer dete hain. "Voter" ek referee ki tarah hai jo woh answer pick karta hai jis par do computers agree karte hain.

Teen kyun, do kyun nahi? Do computers ke saath, agar woh disagree karein, tum nahi jaante kaun sahi hai! Teen ke saath, majority (do) almost hamesha sahi hoti hai — jab tak tum really unlucky na ho aur do exact same time par toot jaayein (bahut rare hai agar woh independent hain).

Connections

• Fault Tolerance Fundamentals — TMR ek pattern hai; N-version programming se compare karo
• Watchdog Timers — Hung modules detect karo jo time par output nahi karte
• Error Detection Codes — Hamming/CRC errors detect karte hain; TMR unhe correct karta hai
• Safety-Critical Systems Standards — DO-178C, IEC 61508 kuch SIL levels ke liye redundancy mandate karte hain
• Common-Cause Failures — TMR independence assume karta hai; diverse implementations common-mode risk reduce karti hain
• Byzantine Fault Tolerance — Jab modules maliciously jhooth bol sakten hain (sirf fail-silent nahi); 4+ modules chahiye
• Redundancy vs. Diversity — TMR identical modules use karta hai; N-version alag algorithms/languages use karta hai

Key Takeaways

1. TMR single faults mask karta hai teen parallel computations par vote karke (2-out-of-3 majority)
2. Reliability sirf tab improve hoti hai jab $R>0.5$ (module reliability threshold)
3. Voter ultra-reliable hona chahiye (aksar sabse weak link hota hai; hardened hardware ya voter redundancy use karo)
4. TMR diagnose nahi karta ki kaunsa module fail hua — sirf mask karta hai; maintenance ke liye self-checking add karo
5. Analog systems ko median voting chahiye (average outliers ke liye vulnerable hai)
6. Real-time systems ko voter delay budget karna chahiye aur timeouts handle karne chahiye (fail-silent assumption)

#flashcards/coding

Concept Map