# UNDF: UNDF-2026-000000615
# UNDF: (pending)
# vertx-core-0001: HAManager.nodeLeft — O(N×M) nodes List.contains inside clusterMap loop

## CWE-407 — Algorithmic Complexity: Unnecessary Quadratic Complexity (List membership inside loop)

| Field | Value |
|-------|-------|
| ID | vertx-core-0001 |
| Severity | HIGH |
| Ecosystem | vertx-core |
| Package | io.vertx.core.impl |
| File | `vertx-core/src/main/java/io/vertx/core/impl/HAManager.java` |
| Lines | 307–314 |
| Complexity | O(N×M) |
| Hot path | every cluster node departure event |

## Defect

`HAManager.nodeLeft()` is called whenever a node leaves a Vert.x cluster. It
resumes any prior failed failovers by scanning `clusterMap` for entries not in
the current live node list. The live node list is obtained from
`clusterManager.getNodes()` which returns a `List<String>`. For each of the N
entries in `clusterMap`, it calls `nodes.contains(entry.getKey())` — an O(M)
linear scan of the node list. With N cluster-map entries and M live nodes the
total cost is O(N×M) per node-departure event.

```java
// HAManager.java line 307-314
List<String> nodes = clusterManager.getNodes();   // returns List<String>

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

The same pattern appears in `addHaInfoIfLost()` (line 319):
```java
if (clusterManager.getNodes().contains(nodeID) && ...)  // O(M) single call, low risk
```

## Fix

Convert the node list to a `HashSet` before the loop so membership checks are O(1).

```java
Set<String> nodesSet = new HashSet<>(clusterManager.getNodes());

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);
    }
}
```

For `addHaInfoIfLost()` the single call is not in a loop so is low risk — but can be converted similarly if consistency is desired.

## Speedup

| N (clusterMap entries) | M (nodes) | Before (ops) | After (ops) | Speedup |
|------------------------|-----------|-------------|-------------|---------|
| 100 | 100 | 10,000 | 100 | 100× |
| 500 | 500 | 250,000 | 500 | 500× |
| 1,000 | 1,000 | 1,000,000 | 1,000 | 1,000× |

In large Vert.x HA clusters with many concurrent deployments the quadratic
cost is paid on every node failure event — exactly when latency matters most
for failover speed.
