# onos-0003: DeviceManager RoleInfo.backups() ImmutableList.contains() — O(n) per role event

## Status
PATCHED

## Target
opennetworkinglab/onos

## File
`core/api/src/main/java/org/onosproject/cluster/RoleInfo.java`
`core/net/src/main/java/org/onosproject/net/device/impl/DeviceManager.java`

## Symptom
On every mastership role change event, `DeviceManager` checks whether `localNodeId` is in
the backup list using `List.contains()` on an `ImmutableList`. With C ONOS cluster nodes,
the backup list has up to C-1 entries. In large clusters (10–50 nodes) this is O(C) per
device event. With D managed devices, each failover triggers D events — O(D×C) total.

## Root cause
```java
// RoleInfo.java:32,36
private final List<NodeId> backups;
this.backups = ImmutableList.copyOf(backups);   // O(n) contains

// DeviceManager.java:1159
} else if (event.roleInfo().backups().contains(localNodeId)) {
```

`backups()` returns `ImmutableList<NodeId>` — linear scan backed by an array.

## Fix
Change `backups` to `ImmutableSet<NodeId>`. Order of backup list is not meaningful for
membership tests; `ImmutableSet.contains()` is O(1) hash lookup.

## Complexity
| Before | After |
|--------|-------|
| O(C) per role event | O(1) per role event |

## Patch
`defects/onos/patch/onos-0003-roleinfo-backups-immutablelist-linear.patch`

## Unit test
`defects/onos/unit/OnosRoleInfoTest.java`