Practice/xAI/Group Test GPU Nodes

Group Test GPU Nodes

CodingMust

Problem Overview

You have n GPU nodes in a cluster, some of which are faulty. You need to identify all faulty nodes using a special group testing function.

You can call a test(S) function that tests a set of nodes:

• test(S) returns True if all nodes in S are good
• test(S) returns False if S contains at least one faulty node

Constraints:

• |S| >= 2 — You cannot test a single node by itself
• Tests can run in parallel, but a node cannot appear in multiple simultaneous tests
• There are at least 2 good nodes in the cluster (this is a critical assumption!)

Goal: Design an algorithm to identify all faulty nodes as efficiently as possible.

Why At Least 2 Good Nodes?

If there's only 1 good node G among n nodes:

• Any pair containing G also contains a faulty node → test({G, X}) = False
• Any pair NOT containing G has two faulty nodes → test({X, Y}) = False
• Every single test returns False! We cannot distinguish the good node from faulty ones.

This is a fundamental limitation of the group testing model with the |S| >= 2 constraint.

Key Insight

If we can find one known-good node G, we can test any other node X by calling test({G, X}):

• test({G, X}) = True → X is good
• test({G, X}) = False → X is faulty

This reduces the problem to: How do we efficiently find one good node?

Part 1: Finding a Known-Good Node

The first challenge is finding at least one good node. Use binary search to find a subset containing only good nodes, then pick any node from that subset as the reference.

Example

` nodes = [0, 1, 2, 3, 4, 5, 6, 7] # Hidden: nodes 2 and 5 are faulty

Test all nodes

test({0, 1, 2, 3, 4, 5, 6, 7}) # False (contains faulty nodes)

Test first half

test({0, 1, 2, 3}) # False (contains node 2)

Test second half

test({4, 5, 6, 7}) # False (contains node 5)

Test first quarter

test({0, 1}) # True! Both are good, pick node 0 as reference `

Requirements

• Use binary search to find a subset of all-good nodes
• If a subset tests as True, any node in it can be the reference
• Handle edge cases where good nodes are spread across subdivisions
• Fall back to testing pairs if binary search doesn't find a good subset

Clarification Questions to Ask

• Are there at least 2 good nodes? (Critical — if not, the problem is unsolvable!)
• Can we assume the test function is deterministic and doesn't have false positives/negatives?
• What's the expected ratio of faulty to good nodes?
• Should we optimize for total number of tests, or number of parallel rounds?
• Is there a cost difference between sequential and parallel tests?

Part 2: Testing All Nodes Against Reference

Once you have a known-good node, test each remaining node against it to classify as good or faulty.

Example

`

Assume we found node 0 is good

good_ref = 0 nodes = [1, 2, 3, 4, 5, 6, 7]

test({0, 1}) # True → node 1 is good test({0, 2}) # False → node 2 is faulty test({0, 3}) # True → node 3 is good test({0, 4}) # True → node 4 is good test({0, 5}) # False → node 5 is faulty test({0, 6}) # True → node 6 is good test({0, 7}) # True → node 7 is good

Result: {2, 5} are faulty

`

Requirements

• Test each node (except the known-good reference) against the reference
• Collect all nodes that fail the test as faulty nodes
• Return the set of faulty node indices