[FEA]: canonicalize ComputeInstances discovery and provider fan-out order

[teerthsharma]

Version

main at 7607854c8d6b6509b52a9296d7ce149968c011ba (2026-07-22).

Installation method

Source inspection and unit-test analysis.

Describe the bug

Equivalent sets of compute instances do not currently have a canonical discovery order before provider calls. Several paths derive ordered slices from unordered maps or from upstream list encounter order:

• pkg/engines/slurm/slurm.go:128-153: aggregateComputeInstances ranges over the i2n map and appends regions on first encounter. The returned []ComputeInstances region order therefore depends on Go map iteration. TestAggregateComputeInstances uses ElementsMatch, which masks this property.
• internal/k8s/utils.go:107-133: GetComputeInstances preserves the first-seen region order from NodeList.Items instead of defining a canonical region order.
• pkg/engines/slinky/engine.go:249-282: the Slinky-specific builder repeats the same first-seen-region behavior.
• pkg/topology/request.go:122-130: GetNodeNameList ranges over each Instances map without sorting. This list feeds both bare-metal pdsh and getIbTree, so the host/probe sequence can vary for the same logical request.
• pkg/providers/aws/instance_topology.go:61-66: DescribeInstanceTopologyInput.InstanceIds is built directly from an Instances map.

The final Slurm serializers already sort many topology structures, so this report does not claim that every successful run emits different topology.conf bytes. The nondeterminism occurs earlier: region API fan-out order, explicit provider request order, InfiniBand probe-host order, logs/metrics, and which error is returned first when more than one region or probe can fail.

Minimum reproducible example

A deterministic regression test can construct the same logical mapping through every permutation of input node order, for example:

instances := map[string]string{
    "i-b": "node-b",
    "i-a": "node-a",
    "i-c": "node-c",
}
regions := map[string]string{
    "node-b": "region-b",
    "node-a": "region-a",
    "node-c": "region-b",
}

Today, the Slurm aggregation test cannot assert one exact result because region creation follows map iteration. Likewise, a fake AWS client or fake IBNetDiscover runner can observe different ID/host call order unless the caller sorts first.

Expected deterministic behavior

Define one canonical ordering at the ComputeInstances boundary:

1. regions sorted lexicographically;
2. instance IDs sorted lexicographically within each region whenever converted to a slice;
3. node names sorted lexicographically for host-oriented command/probe lists.

The ordering should be applied before external provider/API/exec calls, not only during final serialization. Canonicalization must not mutate the caller-owned request and must not change the canonical topology.Graph shape.

Proposed implementation

• Add small shared sorting helpers near topology.ComputeInstances rather than duplicating ordering logic across engines/providers.
• Make Slurm, Kubernetes, and Slinky aggregation return regions in the same canonical order.
• Make GetNodeNameList return a sorted list while preserving its current membership semantics.
• Sort AWS explicit InstanceIds before DescribeInstanceTopology; audit other map-to-request conversions in DSX/OCI/InfiniBand and use the same helper where applicable.
• Keep provider discovery sequential unless concurrency is separately designed; deterministic sequencing also makes first-error precedence stable.

Acceptance criteria

• Slurm, Kubernetes, and Slinky produce identical, exactly ordered []ComputeInstances for every permutation of the same logical nodes.
• GetNodeNameList has an exact-order test; callers receive the same host sequence for permuted map construction.
• Fake AWS and InfiniBand clients record the same request/probe sequence for equivalent inputs.
• Multi-region failure tests establish deterministic first-error precedence.
• Tests enumerate/permutate inputs and assert exact traces; they do not rely on running a map iteration repeatedly and hoping the runtime changes order.
• Existing generated topology output remains byte-identical for the same successful logical input.
• make qualify passes, documentation impact is evaluated, and the user-visible determinism fix is recorded under CHANGELOG.md [Unreleased].

Alternatives considered

Sorting only the final topology.conf or JSON output is insufficient because provider calls and failure selection have already occurred. Relying on Kubernetes list order is also insufficient because it would leave the Slurm and Go-map paths unordered and would make engine behavior inconsistent.

---

By submitting this issue, I agree to follow the project's Code of Conduct and contributing guidelines. I searched open and closed issues and PRs for ComputeInstances ordering, map iteration, provider call order, GetNodeNameList, InfiniBand probe order, and region ordering; I found no duplicate.

[dmitsh]

Why is it a bug?

[teerthsharma]

Because Go map iteration is unspecified, the same ComputeInstances set can call regions and hosts in a different order. That changes observable behavior before serialization—especially which region error is returned first and which host is probed first—making retries and diagnostics non-reproducible even when successful topology bytes are unchanged. #422 only canonicalizes that sequencing; it does not change graph shape or membership.

[dmitsh]

Still, it's not a bug, nor the requirement, but rather a feature request.
The topology discovery is accurate and correct.

[teerthsharma]

Still, it's not a bug, nor the requirement, but rather a feature request.
The topology discovery is accurate and correct.

Yes , I believe that too but I wasn't sure at the time of submission