# UNDF: UNDF-2026-000000291
# spark-0003: Spark Standalone Master — completedApps ArrayBuffer.contains() O(n²) on worker failure

## Severity
MEDIUM — called on each worker failure; O(A × C) where A = running apps, C = completed apps;
materializes in long-running clusters where C grows to spark.deploy.retainedApplications (default 200)

## File
`core/src/main/scala/org/apache/spark/deploy/master/Master.scala`

## Lines
83 (`completedApps` field declaration), 1114 (`apps.filterNot(completedApps.contains(_))`)

## Pattern
CWE-407: O(n) ArrayBuffer.contains() used as predicate in filterNot over all running apps.

```scala
// DEFECTIVE (line 83)
private val completedApps = new ArrayBuffer[ApplicationInfo]

// DEFECTIVE (line 1114) — inside workerRemoved(worker), called for every worker failure
apps.filterNot(completedApps.contains(_)).foreach { app =>
    ...  // notify app of lost worker
}
```

`completedApps` is a `mutable.ArrayBuffer`. `filterNot(completedApps.contains(_))` iterates
every element of `apps` (HashSet[ApplicationInfo]) and calls `completedApps.contains(app)` —
O(completedApps.size) per app. Total: O(|apps| × |completedApps|).

By default, Spark retains 200 completed applications (`spark.deploy.retainedApplications`).
Each worker failure call becomes O(200 × A) where A is the current number of running apps.
In a large Spark cluster with 100 running apps and 200 completed: 20,000 comparisons instead of 100.

## Fix

Pre-build a `HashSet` before the filter, or use `toSet`:

```scala
// FIXED — option 1: convert at call site
val completedAppsSet = completedApps.toSet
apps.filterNot(completedAppsSet.contains(_)).foreach { app =>

// FIXED — option 2: maintain as HashSet
private val completedApps = new mutable.HashSet[ApplicationInfo]
```

Option 2 is preferred as `completedApps` is only ever tested for membership or iterated;
changing to HashSet gives O(1) contains with no behavior change.

## Complexity
- Before: O(A × C) per worker failure event
- After: O(A) per worker failure event

## Impact
Worker failures trigger master-level app notification. In a cluster under stress (many worker
failures), this compounds — each failure event is more expensive just as cluster load peaks.
With 200 completed apps, this is a 200x overhead per failure event.
