diff --git a/conman/connection_manager.py b/conman/connection_manager.py
index 2ab4763..7e2b24b 100755
--- a/conman/connection_manager.py
+++ b/conman/connection_manager.py
@@ -8,6 +8,7 @@
 import json
 import logging
 import os
+import random
 import re
 import subprocess
 import time
@@ -202,7 +203,8 @@
                moca_tmp_dir='/tmp/cwmp/monitoring/moca2',
                wpa_control_interface='/var/run/wpa_supplicant',
                run_duration_s=1, interface_update_period=5,
-               wifi_scan_period_s=120, wlan_retry_s=15, acs_update_wait_s=10):
+               wifi_scan_period_s=120, wlan_retry_s=15, acs_update_wait_s=10,
+               bssid_cycle_length_s=30):
 
     self._tmp_dir = tmp_dir
     self._config_dir = config_dir
@@ -215,6 +217,7 @@
     self._wifi_scan_period_s = wifi_scan_period_s
     self._wlan_retry_s = wlan_retry_s
     self._acs_update_wait_s = acs_update_wait_s
+    self._bssid_cycle_length_s = bssid_cycle_length_s
     self._wlan_configuration = {}
 
     # Make sure all necessary directories exist.
@@ -658,7 +661,13 @@
     logging.info('Done scanning on %s', wifi.name)
     items = [(bss_info, 3) for bss_info in with_ie]
     items += [(bss_info, 1) for bss_info in without_ie]
-    wifi.cycler = cycler.AgingPriorityCycler(cycle_length_s=30, items=items)
+    if not hasattr(wifi, 'cycler'):
+      wifi.cycler = cycler.AgingPriorityCycler(
+          cycle_length_s=self._bssid_cycle_length_s)
+    # Shuffle items to undefined determinism in scan results + dict
+    # implementation unfairly biasing BSSID order.
+    random.shuffle(items)
+    wifi.cycler.update(items)
 
   def _find_bssids(self, band):
     def supports_autoprovisioning(oui, vendor_ie):
diff --git a/conman/connection_manager_test.py b/conman/connection_manager_test.py
index 0297ca1..954e2e3 100755
--- a/conman/connection_manager_test.py
+++ b/conman/connection_manager_test.py
@@ -6,6 +6,7 @@
 import os
 import shutil
 import tempfile
+import time
 
 import connection_manager
 import interface_test
@@ -539,6 +540,7 @@
                               run_duration_s=run_duration_s,
                               interface_update_period=interface_update_period,
                               wifi_scan_period_s=wifi_scan_period_s,
+                              bssid_cycle_length_s=0.05,
                               **cm_kwargs)
 
         c.test_interface_update_period = interface_update_period
@@ -805,8 +807,11 @@
   wvtest.WVFAIL(c.wifi_for_band(band).acs())
 
   c.can_connect_to_s2 = True
-  # Give it time to try all BSSIDs.
-  for _ in range(3):
+  # Give it time to try all BSSIDs.  This means sleeping long enough that
+  # everything in the cycler is active, then doing n+1 loops (the n+1st loop is
+  # when we decided that the SSID in the nth loop was successful).
+  time.sleep(c._bssid_cycle_length_s)
+  for _ in range(len(c.wifi_for_band(band).cycler) + 1):
     c.run_once()
   s2_bss = iw.BssInfo('01:23:45:67:89:ab', 's2')
   wvtest.WVPASSEQ(c.wifi_for_band(band).last_successful_bss_info, s2_bss)
@@ -954,8 +959,8 @@
   # The next 2.4 GHz scan will have results.
   c.interface_with_scan_results = c.wifi_for_band('2.4').name
   c.run_until_scan('2.4')
-  # Now run 3 cycles, so that s2 will have been tried.
-  for _ in range(3):
+  # Now run for enough cycles that s2 will have been tried.
+  for _ in range(len(c.wifi_for_band('2.4').cycler)):
     c.run_once()
   c.run_until_interface_update()
   wvtest.WVPASS(c.acs())
@@ -1044,10 +1049,10 @@
   wvtest.WVFAIL(c.wifi_for_band('2.4').current_route())
   wvtest.WVFAIL(c.wifi_for_band('5').current_route())
 
-  # The 2.4 GHz scan will have results that will lead to ACS access.
+  # The scan will have results that will lead to ACS access.
   c.interface_with_scan_results = c.wifi_for_band('2.4').name
   c.run_until_scan('5')
-  for _ in range(3):
+  for _ in range(len(c.wifi_for_band('2.4').cycler)):
     c.run_once()
   c.run_until_interface_update()
   wvtest.WVPASS(c.acs())
diff --git a/conman/cycler.py b/conman/cycler.py
index ff65bfc..23f2ce4 100755
--- a/conman/cycler.py
+++ b/conman/cycler.py
@@ -27,9 +27,10 @@
       queue after being automatically reinserted.
       items: Initial items for the queue, as tuples of (item, priority).
     """
-    t = time.time()
-    self._items = {item: [priority, t] for item, priority in items}
     self._min_time_in_queue_s = cycle_length_s
+    self._items = {}
+    if items:
+      self.update(items)
 
   def empty(self):
     return not self._items
@@ -79,3 +80,23 @@
 
     return result
 
+  def update(self, items):
+    """Update to the given items, adding new ones and removing old ones.
+
+    Args:
+      items:  An iterable of (item, priority).
+    """
+    now = time.time()
+    new_items = {}
+    for item, priority in items:
+      t = now
+      existing = self._items.get(item, None)
+      if existing:
+        t = existing[1]
+      new_items[item] = [priority, t]
+
+    self._items = new_items
+
+  def __len__(self):
+    return len(self._items)
+
diff --git a/conman/cycler_test.py b/conman/cycler_test.py
index c4e498b..de1e6c0 100755
--- a/conman/cycler_test.py
+++ b/conman/cycler_test.py
@@ -20,26 +20,40 @@
   # We should get all three in order, since they all have the same insertion
   # time.  They will all get slightly different insertion times, but next()
   # should be fast enough that the differences don't make much difference.
-  wvtest.WVPASS(c.peek() == 'A')
-  wvtest.WVPASS(c.next() == 'A')
-  wvtest.WVPASS(c.next() == 'B')
-  wvtest.WVPASS(c.next() == 'C')
+  wvtest.WVPASSEQ(c.peek(), 'A')
+  wvtest.WVPASSEQ(c.next(), 'A')
+  wvtest.WVPASSEQ(c.next(), 'B')
+  wvtest.WVPASSEQ(c.next(), 'C')
   wvtest.WVPASS(c.peek() is None)
   wvtest.WVPASS(c.next() is None)
   wvtest.WVPASS(c.next() is None)
 
   # Now, wait for items to be ready again and just cycle one of them.
   time.sleep(cycle_length_s)
-  wvtest.WVPASS(c.next() == 'A')
+  wvtest.WVPASSEQ(c.next(), 'A')
 
   # Now, if we wait 1.9 cycles, the aged priorities will be as follows:
   # A: 0.9 * 10 = 9
   # B: 1.9 * 5 = 9.5
   # C: 1.9 * 1 = 1.9
   time.sleep(cycle_length_s * 1.9)
-  wvtest.WVPASS(c.next() == 'B')
-  wvtest.WVPASS(c.next() == 'A')
-  wvtest.WVPASS(c.next() == 'C')
+  wvtest.WVPASSEQ(c.next(), 'B')
+  wvtest.WVPASSEQ(c.next(), 'A')
+  wvtest.WVPASSEQ(c.next(), 'C')
+
+  # Update c, keeping A as-is, removing B, updating C's priority, and adding D.
+  # Sleep for two cycles.  After the first cycle, D has priority 20 and A and C
+  # have priority 0 (since we just cycled them).  After the second cycle, the
+  # priorities are as follows:
+  # A: 1 * 10 = 10
+  # C: 1 * 20 = 20
+  # D: 2 * 20 = 40
+  c.update((('A', 10), ('C', 20), ('D', 20)))
+  time.sleep(cycle_length_s * 2)
+  wvtest.WVPASSEQ(c.next(), 'D')
+  wvtest.WVPASSEQ(c.next(), 'C')
+  wvtest.WVPASSEQ(c.next(), 'A')
+  wvtest.WVPASS(c.next() is None)
 
 if __name__ == '__main__':
   wvtest.wvtest_main()