Katkat
Back

Find All Faulty GPU Nodes with Parallel Group Tests That Cannot Share Nodes

xAIMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteSoftware Engineering Fundamentals

Last updated

An algorithm design question about finding every faulty GPU node when the only tool is a group test that fails if any node in the set is bad. Tests need at least two nodes and parallel tests cannot share nodes, so it tests adaptive testing strategies, identifiability, and cost in rounds and tests.

A cluster has n GPU nodes, numbered 0 to n - 1, and some of them are bad. The only diagnostic is a group test: test(S) runs a job on a set S of nodes and returns False if at least one node in S is bad, or True if every node in S is good.

Tests can run in parallel, with two restrictions:

  • a node cannot take part in two tests that run at the same time;
  • every test must include at least two nodes (|S| >= 2).

Design an algorithm that identifies exactly which nodes are bad, as efficiently as possible, and implement it. Model the parallelism as rounds: one call to run_tests is one round of tests running at the same time.

def run_tests(groups: list[list[int]]) -> list[bool]:
 """Runs every group as one parallel round and returns one result per group.
 Groups in one call must be pairwise disjoint, and each must contain at least two nodes."""

def find_bad_nodes(n: int, run_tests) -> set[int]:
 ...

Constraints and Clarifications

  • Tests are reliable: the same set always gives the same result.
  • A node's status does not change while the procedure runs.
  • The procedure must return the exact set of bad nodes whenever the test results make that set identifiable.

Clarifying Questions

  • What does "efficient" mean here: the number of parallel rounds (wall-clock time), the total number of tests (cluster time), or both?
  • Is there a known bound on, or an estimate of, how many nodes are bad?
  • Does a test's duration or reliability depend on how many nodes it includes?
  • Is at least one good node, or a pair of good nodes, guaranteed? What should happen if nearly every node is bad?
  • May one round mix tests of different sizes, and may a node sit out a round?

Hints

Hint 1

What a failure means: Consider how the meaning of a failing test changes depending on what you already know about the other nodes in it.

Hint 2

Count rounds, not only tests: Once you have a strategy that works, ask how many nodes it can resolve in one round, and how that number can grow from one round to the next.

Follow-up questions

  • If you know that only a handful of the `n` nodes are bad, how can you use far fewer tests than one per node?
  • Tests become flaky: a set of good nodes occasionally fails. How do you adapt, and how confident can you be in each verdict?
  • A test's duration grows with the number of nodes in it. How does that change your choice of group sizes?
  • How would you run this continuously on a production cluster where nodes join, leave and fail over time?