An efficient one-pass method identifies reliable good chips quickly
Backtracking Candidate Elimination: A One-Pass Algorithm for the Chip Testing Problem
Data Structures and AlgorithmsDiscrete Mathematics
Summary
The chip testing problem involves finding one good chip among many, knowing that more than half are good but some lie about the status of others. Chips can test each other, with good chips always truthful while bad chips may lie. The authors present a new algorithm that checks chips in one pass, tracking candidates and discarding pairs when tests conflict, ensuring at most one test per chip. This method is simpler and faster than standard approaches, proving correctness through consistent chip groups and discarded bad chip pairs.
What this means in practice
- •For hardware testing teams: Identify a guaranteed good chip from a batch efficiently using a single-pass testing method adapted for adversarial test outcomes.
- •For security verification engineers: Implement an online fault detection process that resists misleading test reports by retaining consistent sets of trustworthy components.
Authors
Shiyi Chen
Abstract
In the chip testing problem, we are given $n$ chips, strictly more than half of which are good. Chips can test one another in pairs; a good chip always reports the status of the other chip correctly, whereas a bad chip may report arbitrarily and adversarially. The goal is to identify a single chip that is guaranteed to be good. The problem originates in system-level fault diagnosis and is closely related to the "knights and spies" puzzle. The standard textbook solution is a halving recursion that tests disjoint pairs in rounds and keeps one chip from each consistent pair. We present the Backtracking Candidate Elimination (BCE) algorithm, a sequential alternative that scans the chips once while maintaining a current candidate and a stack of retained chips. Every chip is tested at most once as the incoming chip; when a test is inconclusive the candidate and the incoming chip are discarded together, and the algorithm backtracks to the most recently retained chip. BCE uses at most $n-1$ tests and $O(n)$ time, needs no parity case analysis, and works online. Its correctness follows from two invariants: the retained chips all have the same type, and every discarded pair contains at least one bad chip. We explain how BCE can be viewed as the Boyer-Moore majority vote algorithm with its counter replaced by a stack of physical witnesses, and why that replacement is needed. We also give an early termination rule and a variant for the weaker model of one-directional tests.