# UNDF: UNDF-2026-000000570
# vertx-0001 — HAManager nodeLeft() nodes List.contains O(C²) in cluster failover scan

**Classification:** CWE-407 Algorithmic Complexity — Inefficient Membership Test
**Severity:** MEDIUM
**Component:** vert.x core — `io.vertx.core.impl.HAManager`
**File:** `vertx-core/src/main/java/io/vertx/core/impl/HAManager.java`
**Line:** 307–317

## Description

When a cluster node leaves, `HAManager.nodeLeft()` scans the entire `clusterMap` to find any
in-progress failovers that were themselves abandoned. For each entry in `clusterMap` it calls
`nodes.contains(entry.getKey())` where `nodes` is a `List<String>` returned by
`clusterManager.getNodes()`. The `List.contains()` is an O(N) linear scan, making the entire
loop O(C × N) = O(N²) in cluster size.

## Defective code

```java
// HAManager.java:307-317
List<String> nodes = clusterManager.getNodes();

for (Map.Entry<String, String> entry: clusterMap.entrySet()) {
    if (!leftNodeID.equals(entry.getKey()) && !nodes.contains(entry.getKey())) {
        JsonObject haInfo = new JsonObject(entry.getValue());
        checkFailover(entry.getKey(), haInfo);
    }
}
```

`nodes` is declared as `List<String> getNodes()` in `ClusteredNode.java:47`. The `clusterMap` has
one entry per cluster node. Both collections grow linearly with cluster size, so the inner
`nodes.contains()` is called C times, each taking O(N) time → O(N²) total.

## Fix

Convert `nodes` to a `HashSet<String>` before the loop:

```java
List<String> nodesList = clusterManager.getNodes();
Set<String> nodesSet = new HashSet<>(nodesList);   // O(N) one-time build

for (Map.Entry<String, String> entry: clusterMap.entrySet()) {
    if (!leftNodeID.equals(entry.getKey()) && !nodesSet.contains(entry.getKey())) {
        JsonObject haInfo = new JsonObject(entry.getValue());
        checkFailover(entry.getKey(), haInfo);
    }
}
```

The same fix applies to the second call site at line 319:
```java
// before:
if (clusterManager.getNodes().contains(nodeID) && ...
// after: use the already-constructed nodesSet
if (nodesSet.contains(nodeID) && ...
```

## Complexity

| | Before | After |
|---|---|---|
| `nodes.contains()` per call | O(N) | O(1) |
| Full `nodeLeft()` scan | O(N²) | O(N) |
| HashSet construction | — | O(N) one-time |

## Speedup estimate

At N=500 cluster nodes: ~500× operation-count reduction in the membership scan.
Typically triggered once per node departure event, so the absolute time is small in small
clusters. In large clusters (100–1000 nodes, common in cloud deployments) and high churn rates
this becomes a significant stall on the event-loop thread.

## Affected versions

All versions through current HEAD (2026-03-28).
