# ray-0001: local node provider list_of_node_ips O(N²) membership test during cluster reconciliation

**Severity:** MEDIUM
**CWE:** CWE-407 (Algorithmic Complexity — linear membership test in hot loop)
**Speedup:** ~Nx at N=200 node cluster (verified by unit test)
**Target:** Ray (ray-project/ray)
**Files:**
- `python/ray/autoscaler/_private/local/node_provider.py:79-83` — `ClusterState.__init__`: list_of_node_ips linear scan
- `python/ray/autoscaler/_private/local/node_provider.py:147-149` — `OnPremCoordinatorState.__init__`: same pattern

## Description

In `ClusterState.__init__`, node IP reconciliation builds a list and then scans it linearly
inside a loop over all tracked workers:

```python
list_of_node_ips = list(provider_config["worker_ips"])   # line 79 — creates a list
list_of_node_ips.append(provider_config["head_ip"])
for worker_ip in list(workers):                           # O(N) outer loop
    if worker_ip not in list_of_node_ips:                 # O(N) linear scan — O(N²) total
        del workers[worker_ip]
```

`list_of_node_ips` is a Python `list`. The `not in` test on a list is O(N) via sequential
comparison. With N cluster nodes, total cost is O(N²).

The same pattern appears in `OnPremCoordinatorState.__init__` (line 147-149), where
`list_of_node_ips` is a list parameter passed from the caller, and the same O(N²) scan
occurs during coordinator state initialization.

Both `ClusterState.__init__` and `OnPremCoordinatorState.__init__` are called during
every cluster state sync (`create_or_update` call path), meaning the O(N²) cost is
incurred on the autoscaler's hot reconciliation loop.

## Root Cause

`list()` was used to convert `provider_config["worker_ips"]` (which may be any iterable)
into a concrete sequence. Python `list` was chosen without considering that membership
tests would be performed against it inside a loop. Converting to a `set` at construction
time gives O(1) average membership test with no semantic change.

## Patch

See `patch/ray-0001-local-node-provider-list-membership.patch`

## Complexity Before

`worker_ip not in list_of_node_ips`: **O(N)**
Total across N workers: **O(N²)**

## Complexity After

`worker_ip not in node_ip_set` (set): **O(1)** average
Total: **O(N)**

## Reproduction

```
cd defects/ray/unit && javac -d . RayTest.java && java -ea unit.RayTest
```
