diff --git a/impl/src/main/java/org/onosproject/segmentrouting/DefaultRoutingHandler.java b/impl/src/main/java/org/onosproject/segmentrouting/DefaultRoutingHandler.java
index 7a65e95..e085c63 100644
--- a/impl/src/main/java/org/onosproject/segmentrouting/DefaultRoutingHandler.java
+++ b/impl/src/main/java/org/onosproject/segmentrouting/DefaultRoutingHandler.java
@@ -22,6 +22,8 @@
 import com.google.common.collect.Maps;
 import com.google.common.collect.Sets;
 
+import com.google.common.hash.Hasher;
+import com.google.common.hash.Hashing;
 import org.onlab.packet.EthType;
 import com.google.common.collect.Streams;
 import org.onlab.packet.Ip4Address;
@@ -67,6 +69,7 @@
 import java.util.concurrent.TimeUnit;
 import java.util.concurrent.locks.Lock;
 import java.util.concurrent.locks.ReentrantLock;
+import java.util.function.Function;
 import java.util.stream.Collectors;
 import java.util.stream.Stream;
 
@@ -107,10 +110,13 @@
     private Instant lastRoutingChange = Instant.EPOCH;
     private Instant lastFullReroute = Instant.EPOCH;
 
-    // Distributed store to keep track of ONOS instance that should program the
-    // device pair. There should be only one instance (the king) that programs the same pair.
-    Map<Set<DeviceId>, NodeId> shouldProgram;
-    Map<DeviceId, Boolean> shouldProgramCache;
+    /*
+     * Store to keep track of ONOS instance that should program the device pair.
+     * There should be only one instance (the leader) that programs the same pair.
+     * This EC map is used as first source of truth. WorkPartitionService is used
+     * to elect a leader when shouldProgram is empty.
+     */
+    Map<DeviceId, NodeId> shouldProgram;
 
     // Distributed routes store to keep track of the routes already seen
     // destination device is the key and target sw is the value
@@ -136,12 +142,32 @@
     }
 
     /**
+     * Deterministic hashing for the shouldProgram logic.
+     */
+    private static Long consistentHasher(EdgePair pair) {
+        Hasher hasher = Hashing.md5().newHasher();
+        long dev1Hash = hasher.putUnencodedChars(pair.dev1.toString())
+                .hash()
+                .asLong();
+        hasher = Hashing.md5().newHasher();
+        long dev2Hash = hasher.putUnencodedChars(pair.dev2.toString())
+                .hash()
+                .asLong();
+        return dev1Hash + dev2Hash;
+    }
+
+    /**
+     * Implements the hash function for the shouldProgram logic.
+     */
+    protected static final Function<EdgePair, Long> HASH_FUNCTION = DefaultRoutingHandler::consistentHasher;
+
+    /**
      * Creates a DefaultRoutingHandler object.
      *
      * @param srManager SegmentRoutingManager object
      */
     DefaultRoutingHandler(SegmentRoutingManager srManager) {
-        this.shouldProgram = srManager.storageService.<Set<DeviceId>, NodeId>consistentMapBuilder()
+        this.shouldProgram = srManager.storageService.<DeviceId, NodeId>consistentMapBuilder()
                 .withName("sr-should-program")
                 .withSerializer(Serializer.using(KryoNamespaces.API))
                 .withRelaxedReadConsistency()
@@ -151,7 +177,6 @@
                 .withSerializer(Serializer.using(KryoNamespaces.API))
                 .withRelaxedReadConsistency()
                 .build();
-        this.shouldProgramCache = Maps.newConcurrentMap();
         update(srManager);
         this.routePopulators = new PredictableExecutor(DEFAULT_THREADS,
                                                       groupedThreads("onos/sr", "r-populator-%d", log));
@@ -290,6 +315,8 @@
             }
 
             log.debug("seenBeforeRoutes size {}", seenBeforeRoutes.size());
+            seenBeforeRoutes.forEach(entry -> log.debug("{} -> {}", entry.getValue(), entry.getKey()));
+
             if (!redoRouting(routeChanges, edgePairs, null)) {
                 log.debug("populateAllRoutingRules: populationStatus is ABORTED");
                 populationStatus = Status.ABORTED;
@@ -351,7 +378,10 @@
                     log.trace("  Current/Existing SPG: {}", entry.getValue());
                 }
             });
+
             log.debug("seenBeforeRoutes size {}", seenBeforeRoutes.size());
+            seenBeforeRoutes.forEach(entry -> log.debug("{} -> {}", entry.getValue(), entry.getKey()));
+
             Set<EdgePair> edgePairs = new HashSet<>();
             Set<ArrayList<DeviceId>> routeChanges = new HashSet<>();
             boolean handleRouting = false;
@@ -505,6 +535,7 @@
             log.debug("populateRoutingRulesForLinkStatusChange: "
                     + "populationStatus is STARTED");
             log.debug("seenBeforeRoutes size {}", seenBeforeRoutes.size());
+            seenBeforeRoutes.forEach(entry -> log.debug("{} -> {}", entry.getValue(), entry.getKey()));
             populationStatus = Status.STARTED;
             rulePopulator.resetCounter(); //XXX maybe useful to have a rehash ctr
             boolean hashGroupsChanged = false;
@@ -1351,7 +1382,7 @@
 
     /**
      * Populates IP rules for a route that has direct connection to the switch
-     * if the current instance is the master of the switch.
+     * if the current instance is leading the programming of the switch.
      *
      * @param deviceId device ID of the device that next hop attaches to
      * @param prefix IP prefix of the route
@@ -1372,7 +1403,7 @@
 
     /**
      * Removes IP rules for a route when the next hop is gone.
-     * if the current instance is the master of the switch.
+     * if the current instance is leading the programming of the switch.
      *
      * @param deviceId device ID of the device that next hop attaches to
      * @param prefix IP prefix of the route
@@ -1423,7 +1454,7 @@
     }
 
     /**
-     * Populates IP rules for a route when the next hop is double-tagged.
+     * Program IP rules for a route when the next hop is double-tagged.
      *
      * @param deviceId  device ID that next hop attaches to
      * @param prefix    IP prefix of the route
@@ -1432,56 +1463,24 @@
      * @param outerVlan Outer Vlan ID of the next hop
      * @param outerTpid Outer TPID of the next hop
      * @param outPort   port that the next hop attaches to
+     * @param install   whether or not install the route
      */
-    void populateDoubleTaggedRoute(DeviceId deviceId, IpPrefix prefix, MacAddress hostMac, VlanId innerVlan,
-                                   VlanId outerVlan, EthType outerTpid, PortNumber outPort) {
-        if (srManager.mastershipService.isLocalMaster(deviceId)) {
-            srManager.routingRulePopulator.populateDoubleTaggedRoute(
-                    deviceId, prefix, hostMac, innerVlan, outerVlan, outerTpid, outPort);
+    void programDoubleTaggedRoute(DeviceId deviceId, IpPrefix prefix, MacAddress hostMac, VlanId innerVlan,
+                                  VlanId outerVlan, EthType outerTpid, PortNumber outPort, boolean install) {
+        if (shouldProgram(deviceId)) {
+            if (install) {
+                srManager.routingRulePopulator.populateDoubleTaggedRoute(
+                        deviceId, prefix, hostMac, innerVlan, outerVlan, outerTpid, outPort);
+            } else {
+                srManager.routingRulePopulator.revokeDoubleTaggedRoute(
+                        deviceId, prefix, hostMac, innerVlan, outerVlan, outerTpid, outPort);
+            }
             srManager.routingRulePopulator.processDoubleTaggedFilter(
-                    deviceId, outPort, outerVlan, innerVlan, true);
+                    deviceId, outPort, outerVlan, innerVlan, install);
         }
     }
 
     /**
-     * Revokes IP rules for a route when the next hop is double-tagged.
-     *
-     * @param deviceId  device ID that next hop attaches to
-     * @param prefix    IP prefix of the route
-     * @param hostMac   MAC address of the next hop
-     * @param innerVlan Inner Vlan ID of the next hop
-     * @param outerVlan Outer Vlan ID of the next hop
-     * @param outerTpid Outer TPID of the next hop
-     * @param outPort   port that the next hop attaches to
-     */
-    void revokeDoubleTaggedRoute(DeviceId deviceId, IpPrefix prefix, MacAddress hostMac, VlanId innerVlan,
-                                 VlanId outerVlan, EthType outerTpid, PortNumber outPort) {
-        // Revoke route either if this node have the mastership (when device is available) or
-        // if this node is the leader (even when device is unavailable)
-        if (!srManager.mastershipService.isLocalMaster(deviceId)) {
-            if (srManager.deviceService.isAvailable(deviceId)) {
-                // Master node will revoke specified rule.
-                log.debug("This node is not a master for {}, stop revoking route.", deviceId);
-                return;
-            }
-
-            // isLocalMaster will return false when the device is unavailable.
-            // Verify if this node is the leader in that case.
-            NodeId leader = srManager.leadershipService.runForLeadership(
-                    deviceId.toString()).leaderNodeId();
-            if (!srManager.clusterService.getLocalNode().id().equals(leader)) {
-                // Leader node will revoke specified rule.
-                log.debug("This node is not a master for {}, stop revoking route.", deviceId);
-                return;
-            }
-        }
-
-        srManager.routingRulePopulator.revokeDoubleTaggedRoute(deviceId, prefix, hostMac,
-                innerVlan, outerVlan, outerTpid, outPort);
-        srManager.routingRulePopulator.processDoubleTaggedFilter(deviceId, outPort, outerVlan, innerVlan, false);
-    }
-
-    /**
      * Purges seen before routes for a given device.
      * @param deviceId the device id
      */
@@ -1533,6 +1532,12 @@
                                        MASTER_CHANGE_DELAY, TimeUnit.MILLISECONDS);
     }
 
+    /*
+     * Even though the current implementation does not heavily rely
+     * on mastership, we keep using the mastership and cluster events
+     * as heuristic to perform full reroutes and to make sure we don't
+     * lose any event when instances fail.
+     */
     protected final class MasterChange implements Runnable {
         private DeviceId devId;
         private MastershipEvent me;
@@ -1589,16 +1594,16 @@
                 log.warn("Mastership changed for dev: {}/{} while programming route-paths "
                         + "due to clusterEvent {} ms ago .. attempting full reroute",
                          devId, me.roleInfo(), lce);
-                if (srManager.mastershipService.isLocalMaster(devId)) {
-                    // old master could have died when populating filters
+                if (shouldProgram(devId)) {
+                    // old leader could have died when populating filters
                     populatePortAddressingRules(devId);
                 }
-                // old master could have died when creating groups
+                // old leader could have died when creating groups
                 // XXX right now we have no fine-grained way to only make changes
                 // for the route paths affected by this device. Thus we do a
                 // full reroute after purging all hash groups. We also try to do
                 // it only once, irrespective of the number of devices
-                // that changed mastership when their master instance died.
+                // that changed mastership when their leader instance died.
                 long lfrr = Instant.now().toEpochMilli() - lastFullReroute.toEpochMilli();
                 boolean doFullReroute = lfrr > FULL_REROUTE_THRESHOLD;
                 if (doFullReroute) {
@@ -1675,7 +1680,7 @@
                 continue;
             }
             for (DeviceId rootSw : deviceAndItsPair(sw.id())) {
-                // check for mastership change since last run
+                // check for leadership change since last run
                 if (!lastProgrammed.contains(sw.id())) {
                     log.warn("New responsibility for this node to program dev:{}"
                             + " ... nuking current ECMPspg", sw.id());
@@ -1766,7 +1771,7 @@
                                   link.dst().deviceId());
                     }
                 }
-                // check for mastership change since last run
+                // check for leadership change since last run
                 if (!lastProgrammed.contains(sw.id())) {
                     log.warn("New responsibility for this node to program dev:{}"
                             + " ... nuking current ECMPspg", sw.id());
@@ -1806,8 +1811,7 @@
             if (!pairDev.isPresent() || !srManager.deviceService.isAvailable(pairDev.get())) {
                 log.debug("Proxy Route changes to downed Sw:{}", failedSwitch);
                 srManager.deviceService.getDevices().forEach(dev -> {
-                    if (!dev.id().equals(failedSwitch) &&
-                            srManager.mastershipService.isLocalMaster(dev.id())) {
+                    if (!dev.id().equals(failedSwitch) && shouldProgram(dev.id())) {
                         log.debug(" : {}", dev.id());
                         changedRtBldr.add(Lists.newArrayList(dev.id(), failedSwitch));
                     }
@@ -1970,89 +1974,47 @@
     }
 
     /**
-     * Determines whether this controller instance should program the
-     * given {@code deviceId}, based on mastership and pairDeviceId if one exists.
-     * <p>
-     * Once an instance is elected, it will be the only instance responsible for programming
-     * both devices in the pair until it goes down.
+     * Determines whether this controller instance should program the given deviceId, based on
+     * workPartitionService and pairDeviceId if one exists. Once an instance is elected, it will
+     * be the only instance responsible for programming both devices in the pair until it goes down.
      *
-     * @param deviceId device identifier to consider for routing
-     * @return true if current instance should handle the routing for given device
+     * @param deviceId the device id
+     * @return true if this instance leads the programming, false otherwise
      */
-    boolean shouldProgram(DeviceId deviceId) {
-        Boolean cached = shouldProgramCache.get(deviceId);
-        if (cached != null) {
-            log.debug("shouldProgram dev:{} cached:{}", deviceId, cached);
-            return cached;
-        }
-
-        Optional<DeviceId> pairDeviceId = srManager.getPairDeviceId(deviceId);
-
+    public boolean shouldProgram(DeviceId deviceId) {
+        NodeId leader = shouldProgram.get(deviceId);
         NodeId currentNodeId = srManager.clusterService.getLocalNode().id();
-        NodeId masterNodeId = srManager.mastershipService.getMasterFor(deviceId);
-        Optional<NodeId> pairMasterNodeId = pairDeviceId.map(srManager.mastershipService::getMasterFor);
-        log.debug("Evaluate shouldProgram {}/pair={}. currentNodeId={}, master={}, pairMaster={}",
-                deviceId, pairDeviceId, currentNodeId, masterNodeId, pairMasterNodeId);
-
-        // No pair device configured. Only handle when current instance is the master of the device
-        if (!pairDeviceId.isPresent()) {
-            log.debug("No pair device. currentNodeId={}, master={}", currentNodeId, masterNodeId);
-            return currentNodeId.equals(masterNodeId);
+        if (leader != null) {
+            log.trace("shouldProgram dev:{} leader:{}", deviceId, leader);
+            return currentNodeId.equals(leader);
         }
 
-        // Should not handle if current instance is not the master of either switch
-        if (!currentNodeId.equals(masterNodeId) &&
-                !(pairMasterNodeId.isPresent() && currentNodeId.equals(pairMasterNodeId.get()))) {
-            log.debug("Current nodeId {} is neither the master of target device {} nor pair device {}",
-                    currentNodeId, deviceId, pairDeviceId);
-            return false;
-        }
+        // hash function is independent from the order of the devices in the edge pair
+        Optional<DeviceId> pairDeviceId = srManager.getPairDeviceId(deviceId);
+        EdgePair edgePair = new EdgePair(deviceId, pairDeviceId.orElse(DeviceId.NONE));
 
-        Set<DeviceId> key = Sets.newHashSet(deviceId, pairDeviceId.get());
-
-        NodeId king = shouldProgram.compute(key, ((k, v) -> {
-            if (v == null) {
-                // There is no value in the map. Elect a node
-                return elect(Lists.newArrayList(masterNodeId, pairMasterNodeId.orElse(null)));
-            } else {
-                if (v.equals(masterNodeId) || v.equals(pairMasterNodeId.orElse(null))) {
-                    // Use the node in the map if it is still alive and is a master of any of the two switches
-                    return v;
-                } else {
-                    // Previously elected node is no longer the master of either switch. Re-elect a node.
-                    return elect(Lists.newArrayList(masterNodeId, pairMasterNodeId.orElse(null)));
-                }
-            }
-        }));
-
-        if (king != null) {
-            log.debug("{} is king, should handle routing for {}/pair={}", king, deviceId, pairDeviceId);
-            shouldProgramCache.put(deviceId, king.equals(currentNodeId));
-            return king.equals(currentNodeId);
+        leader = srManager.workPartitionService.getLeader(edgePair, HASH_FUNCTION);
+        if (leader != null) {
+            log.debug("{} is the leader, should handle routing for {}/pair={}", leader, deviceId,
+                    pairDeviceId);
+            shouldProgram.put(deviceId, leader);
+            return leader.equals(currentNodeId);
         } else {
-            log.error("Fail to elect a king for {}/pair={}. Abort.", deviceId, pairDeviceId);
-            shouldProgramCache.remove(deviceId);
+            log.error("Fail to elect a leader for {}/pair={}. Abort.", deviceId, pairDeviceId);
+            shouldProgram.remove(deviceId);
             return false;
         }
     }
 
-    /**
-     * Elects a node who should take responsibility of programming devices.
-     * @param nodeIds list of candidate node ID
-     *
-     * @return NodeId of the node that gets elected, or null if none of the node can be elected
-     */
-    private NodeId elect(List<NodeId> nodeIds) {
-        // Remove all null elements. This could happen when some device has no master
-        nodeIds.removeAll(Collections.singleton(null));
-        nodeIds.sort(null);
-        return nodeIds.size() == 0 ? null : nodeIds.get(0);
+    void invalidateShouldProgram(DeviceId deviceId) {
+        shouldProgram.remove(deviceId);
     }
 
-    void invalidateShouldProgramCache(DeviceId deviceId) {
-        shouldProgramCache.remove(deviceId);
+    void invalidateShouldProgram() {
+        shouldProgram.clear();
     }
 
+
     /**
      * Returns a set of device ID, containing given device and its pair device if exist.
      *
@@ -2147,7 +2109,8 @@
     /**
      * Populates filtering rules for port, and punting rules
      * for gateway IPs, loopback IPs and arp/ndp traffic.
-     * Should only be called by the master instance for this device/port.
+     * Should only be called by the instance leading the programming
+     * for this device/port.
      *
      * @param deviceId Switch ID to set the rules
      */
diff --git a/impl/src/main/java/org/onosproject/segmentrouting/HostHandler.java b/impl/src/main/java/org/onosproject/segmentrouting/HostHandler.java
index 07e619f..a039892 100644
--- a/impl/src/main/java/org/onosproject/segmentrouting/HostHandler.java
+++ b/impl/src/main/java/org/onosproject/segmentrouting/HostHandler.java
@@ -144,7 +144,7 @@
         // ensure dual-homed host locations have viable uplinks
         if (effectiveLocations(host).size() > 1 || srManager.singleHomedDown) {
             effectiveLocations(host).forEach(loc -> {
-                if (srManager.mastershipService.isLocalMaster(loc.deviceId())) {
+                if (srManager.shouldProgram(loc.deviceId())) {
                     srManager.linkHandler.checkUplinksForHost(loc);
                 }
             });
@@ -442,7 +442,7 @@
         // ensure dual-homed host locations have viable uplinks
         if (newLocations.size() > prevLocations.size() || srManager.singleHomedDown) {
             newLocations.forEach(loc -> {
-                if (srManager.mastershipService.isLocalMaster(loc.deviceId())) {
+                if (srManager.shouldProgram(loc.deviceId())) {
                     srManager.linkHandler.checkUplinksForHost(loc);
                 }
             });
@@ -688,13 +688,8 @@
         }
         log.info("{} routing rule for double-tagged host {} at {}",
                  revoke ? "Revoking" : "Populating", ip, location);
-        if (revoke) {
-            srManager.defaultRoutingHandler.revokeDoubleTaggedRoute(
-                    deviceId, ip.toIpPrefix(), mac, innerVlan, outerVlan, outerTpid, port);
-        } else {
-            srManager.defaultRoutingHandler.populateDoubleTaggedRoute(
-                    deviceId, ip.toIpPrefix(), mac, innerVlan, outerVlan, outerTpid, port);
-        }
+        srManager.defaultRoutingHandler.programDoubleTaggedRoute(
+                deviceId, ip.toIpPrefix(), mac, innerVlan, outerVlan, outerTpid, port, !revoke);
     }
 
     void populateAllDoubleTaggedHost() {
diff --git a/impl/src/main/java/org/onosproject/segmentrouting/LinkHandler.java b/impl/src/main/java/org/onosproject/segmentrouting/LinkHandler.java
index 229d32c..c8acc75 100644
--- a/impl/src/main/java/org/onosproject/segmentrouting/LinkHandler.java
+++ b/impl/src/main/java/org/onosproject/segmentrouting/LinkHandler.java
@@ -160,7 +160,7 @@
                     .populateRoutingRulesForLinkStatusChange(null, ulink, null,
                             (seenBefore.contains(ulink) && seenBefore.contains(getReverseLink(ulink))));
 
-            if (srManager.mastershipService.isLocalMaster(ulink.src().deviceId())) {
+            if (srManager.shouldProgram(ulink.src().deviceId())) {
                 // handle edge-ports for dual-homed hosts
                 updateHostPorts(ulink, true);
 
@@ -215,7 +215,7 @@
             log.warn("received a link down for the link {} which is not in the store", link);
         }
         // handle edge-ports for dual-homed hosts
-        if (srManager.mastershipService.isLocalMaster(link.src().deviceId())) {
+        if (srManager.shouldProgram(link.src().deviceId())) {
             updateHostPorts(link, false);
         }
 
@@ -252,16 +252,16 @@
             DefaultGroupHandler groupHandler = srManager.groupHandlerMap
                     .get(ulink.src().deviceId());
             if (groupHandler != null) {
-                if (srManager.mastershipService.isLocalMaster(ulink.src().deviceId())
+                if (srManager.shouldProgram(ulink.src().deviceId())
                         && isParallelLink(ulink)) {
                     log.debug("* retrying hash for parallel link removed:{}", ulink);
                     groupHandler.retryHash(ulink, true, false);
                 } else {
                     log.debug("Not attempting retry-hash for link removed: {} .. {}",
                               ulink,
-                              (srManager.mastershipService.isLocalMaster(ulink
+                              (srManager.shouldProgram(ulink
                                       .src().deviceId())) ? "not parallel"
-                                                          : "not master");
+                                                          : "not handling programming");
                 }
                 // ensure local stores are updated after all rerouting or rehashing
                 groupHandler.portDownForLink(ulink);
diff --git a/impl/src/main/java/org/onosproject/segmentrouting/RoutingRulePopulator.java b/impl/src/main/java/org/onosproject/segmentrouting/RoutingRulePopulator.java
index 5e29dde..80666c5 100644
--- a/impl/src/main/java/org/onosproject/segmentrouting/RoutingRulePopulator.java
+++ b/impl/src/main/java/org/onosproject/segmentrouting/RoutingRulePopulator.java
@@ -1382,8 +1382,8 @@
             return;
         }
 
-        if (request && !srManager.mastershipService.isLocalMaster(deviceId)) {
-            log.debug("Not installing port-IP punts - not the master for dev:{} ",
+        if (request && !srManager.shouldProgram(deviceId)) {
+            log.debug("Not installing port-IP punts - not handling programming for dev:{} ",
                       deviceId);
             return;
         }
@@ -1468,8 +1468,8 @@
      */
     void populateArpNdpPunts(DeviceId deviceId) {
         // We are not the master just skip.
-        if (!srManager.mastershipService.isLocalMaster(deviceId)) {
-            log.debug("Not installing ARP/NDP punts - not the master for dev:{} ",
+        if (!srManager.shouldProgram(deviceId)) {
+            log.debug("Not installing ARP/NDP punts - not handling programming for dev:{} ",
                       deviceId);
             return;
         }
@@ -1967,7 +1967,7 @@
     void updateSpecialVlanFilteringRules(boolean pushVlan, VlanId oldVlanId,
                                          VlanId newVlanId) {
         for (Device dev : srManager.deviceService.getAvailableDevices()) {
-            if (srManager.mastershipService.isLocalMaster(dev.id())) {
+            if (srManager.shouldProgram(dev.id())) {
                 for (Port p : srManager.deviceService.getPorts(dev.id())) {
                     if (!hasIPConfiguration(new ConnectPoint(dev.id(), p.number()))
                             && p.isEnabled()) {
diff --git a/impl/src/main/java/org/onosproject/segmentrouting/SegmentRoutingManager.java b/impl/src/main/java/org/onosproject/segmentrouting/SegmentRoutingManager.java
index 13a9b99..c81ee56 100644
--- a/impl/src/main/java/org/onosproject/segmentrouting/SegmentRoutingManager.java
+++ b/impl/src/main/java/org/onosproject/segmentrouting/SegmentRoutingManager.java
@@ -35,7 +35,6 @@
 import org.onosproject.cluster.ClusterEvent;
 import org.onosproject.cluster.ClusterEventListener;
 import org.onosproject.cluster.ClusterService;
-import org.onosproject.cluster.LeadershipService;
 import org.onosproject.cluster.NodeId;
 import org.onosproject.core.ApplicationId;
 import org.onosproject.core.CoreService;
@@ -198,7 +197,6 @@
 public class SegmentRoutingManager implements SegmentRoutingService {
 
     private static Logger log = LoggerFactory.getLogger(SegmentRoutingManager.class);
-    private static final String NOT_MASTER = "Current instance is not the master of {}. Ignore.";
 
     @Reference(cardinality = ReferenceCardinality.MANDATORY)
     private ComponentConfigService compCfgService;
@@ -257,9 +255,6 @@
     @Reference(cardinality = ReferenceCardinality.MANDATORY)
     public WorkPartitionService workPartitionService;
 
-    @Reference(cardinality = ReferenceCardinality.MANDATORY)
-    public LeadershipService leadershipService;
-
     @Reference(cardinality = ReferenceCardinality.OPTIONAL,
             policy = ReferencePolicy.DYNAMIC)
     public volatile XconnectService xconnectService;
@@ -1063,19 +1058,23 @@
 
     @Override
     public Map<Set<DeviceId>, NodeId> getShouldProgram() {
+        return ImmutableMap.of();
+    }
+
+    @Override
+    public Map<DeviceId, Boolean> getShouldProgramCache() {
+        return ImmutableMap.of();
+    }
+
+    @Override
+    public Map<DeviceId, NodeId> getShouldProgramLeaders() {
         return defaultRoutingHandler == null ? ImmutableMap.of() :
                 ImmutableMap.copyOf(defaultRoutingHandler.shouldProgram);
     }
 
     @Override
-    public Map<DeviceId, Boolean> getShouldProgramCache() {
-        return defaultRoutingHandler == null ? ImmutableMap.of() :
-                ImmutableMap.copyOf(defaultRoutingHandler.shouldProgramCache);
-    }
-
-    @Override
     public boolean shouldProgram(DeviceId deviceId) {
-        return defaultRoutingHandler.shouldProgram(deviceId);
+        return defaultRoutingHandler != null && defaultRoutingHandler.shouldProgram(deviceId);
     }
 
     @Override
@@ -1343,7 +1342,7 @@
      */
     public void updateMacVlanTreatment(DeviceId deviceId, MacAddress hostMac,
                                        VlanId hostVlanId, PortNumber port, int nextId) {
-        // Check if we are the king of this device
+        // Check if we are the leader of this device
         // just one instance should perform this update
         if (!defaultRoutingHandler.shouldProgram(deviceId)) {
             log.debug("This instance is not handling the routing towards the "
@@ -1462,6 +1461,16 @@
                                 + "for available device {}",
                                  event.type(), ((Device) event.subject()).id());
                         processDeviceAdded((Device) event.subject());
+                        /*
+                         * This is a mere heuristic as there is not yet stable mastership in ONOS, and it is based on
+                         * the fact that DEVICE is marked online only if there is a master around. processDeviceAdded
+                         * can be called on config change and link events and there is no check of the availability.
+                         * In this scenarios, we could not have a master and pr is broken as nobody can admin enable
+                         * the ports. We keep in processDeviceAdded the code that is already idempotent
+                         */
+                        if (event.type() == DeviceEvent.Type.DEVICE_AVAILABILITY_CHANGED) {
+                            phasedRecoveryService.init(deviceId);
+                        }
                     } else {
                         if (event.type() == DeviceEvent.Type.DEVICE_ADDED) {
                             // Note: For p4 devices, the device will be added but unavailable at the beginning.
@@ -1584,13 +1593,13 @@
                 } else if (event.type() == MastershipEvent.Type.MASTER_CHANGED) {
                     MastershipEvent me = (MastershipEvent) event;
                     DeviceId deviceId = me.subject();
-                    Optional<DeviceId> pairDeviceId = getPairDeviceId(deviceId);
-                    log.info(" ** MASTERSHIP CHANGED Invalidating shouldProgram cache"
-                            + " for {}/pair={} due to change", deviceId, pairDeviceId);
-                    defaultRoutingHandler.invalidateShouldProgramCache(deviceId);
-                    pairDeviceId.ifPresent(defaultRoutingHandler::invalidateShouldProgramCache);
+                    log.info(" ** Mastership changed check full reroute for {} due to change", deviceId);
                     defaultRoutingHandler.checkFullRerouteForMasterChange(deviceId, me);
 
+                } else if (event.type() == ClusterEvent.Type.INSTANCE_DEACTIVATED ||
+                        event.type() == ClusterEvent.Type.INSTANCE_REMOVED) {
+                    log.info(" ** Cluster event invalidating shouldProgram");
+                    defaultRoutingHandler.invalidateShouldProgram();
                 } else {
                     log.warn("Unhandled event type: {}", event.type());
                 }
@@ -1618,7 +1627,7 @@
     }
 
     private void processDeviceAddedInternal(DeviceId deviceId) {
-        // Irrespective of whether the local is a MASTER or not for this device,
+        // Irrespective of whether the local is leading the programming or not for this device,
         // we need to create a SR-group-handler instance. This is because in a
         // multi-instance setup, any instance can initiate forwarding/next-objectives
         // for any switch (even if this instance is a SLAVE or not even connected
@@ -1644,13 +1653,11 @@
             groupHandlerMap.put(deviceId, groupHandler);
         }
 
-        if (mastershipService.isLocalMaster(deviceId)) {
+        if (shouldProgram(deviceId)) {
             defaultRoutingHandler.populatePortAddressingRules(deviceId);
-            defaultRoutingHandler.purgeSeenBeforeRoutes(deviceId);
             DefaultGroupHandler groupHandler = groupHandlerMap.get(deviceId);
             groupHandler.createGroupsFromVlanConfig();
             routingRulePopulator.populateSubnetBroadcastRule(deviceId);
-            phasedRecoveryService.init(deviceId);
         }
 
         appCfgHandler.init(deviceId);
@@ -1684,6 +1691,8 @@
         defaultRoutingHandler
             .populateRoutingRulesForLinkStatusChange(null, null, device.id(), true);
         defaultRoutingHandler.purgeEcmpGraph(device.id());
+        // Removes routes having as target the device down
+        defaultRoutingHandler.purgeSeenBeforeRoutes(device.id());
 
         // Cleanup all internal groupHandler stores for this device. Should be
         // done after all rerouting or rehashing has been completed
@@ -1723,8 +1732,8 @@
             lastEdgePortEvent = Instant.now();
         }
 
-        if (!mastershipService.isLocalMaster(device.id()))  {
-            log.debug("Not master for dev:{} .. not handling port updated event "
+        if (shouldProgram(device.id()))  {
+            log.debug("Should not program dev:{} .. not handling port updated event "
                     + "for port {}", device.id(), port.number());
             return;
         }
@@ -1734,7 +1743,7 @@
     /**
      * Adds or remove filtering rules for the given switchport. If switchport is
      * an edge facing port, additionally handles host probing and broadcast
-     * rules. Must be called by local master of device.
+     * rules. Must be called by the instance leading the programming of the device.
      *
      * @param deviceId the device identifier
      * @param port the port to update
@@ -2116,6 +2125,7 @@
             case INSTANCE_REMOVED:
                 log.info("** Cluster event {}", event.type());
                 lastClusterEvent = Instant.now();
+                mainEventExecutor.execute(new InternalEventHandler(event));
                 break;
             default:
                 break;
diff --git a/impl/src/main/java/org/onosproject/segmentrouting/SegmentRoutingService.java b/impl/src/main/java/org/onosproject/segmentrouting/SegmentRoutingService.java
index 061e246..71df2ef 100644
--- a/impl/src/main/java/org/onosproject/segmentrouting/SegmentRoutingService.java
+++ b/impl/src/main/java/org/onosproject/segmentrouting/SegmentRoutingService.java
@@ -329,21 +329,36 @@
      * Returns shouldProgram map.
      *
      * @return shouldProgram map
+     * @deprecated in trellis-control-3.0.1
      */
+    @Deprecated
     Map<Set<DeviceId>, NodeId> getShouldProgram();
 
     /**
      * Returns shouldProgram local cache.
      *
      * @return shouldProgram local cache
+     * @deprecated in trellis-control-3.0.1
      */
+    @Deprecated
     Map<DeviceId, Boolean> getShouldProgramCache();
 
     /**
-     * Returns whether instance should program device or not.
+     * Returns shouldProgram leaders.
      *
-     * @param deviceId .
-     * @return boolean status saying instance should program device or not.
+     * @return shouldProgram mapping device to node
+     */
+    Map<DeviceId, NodeId> getShouldProgramLeaders();
+
+    /**
+     * Determines whether this controller instance should program the
+     * given {@code deviceId}, based on work partition service and pairDeviceId if one exists.
+     * <p>
+     * Once an instance is elected, it will be the only instance responsible for programming
+     * both devices in the pair until it goes down.
+     *
+     * @param deviceId device identifier to consider for routing
+     * @return true if current instance should handle the routing for given device
      */
     boolean shouldProgram(DeviceId deviceId);
 
@@ -468,4 +483,5 @@
      * @return the default internal vlan id
      */
     VlanId getDefaultInternalVlan();
+
 }
diff --git a/impl/src/main/java/org/onosproject/segmentrouting/cli/ShouldProgramCommand.java b/impl/src/main/java/org/onosproject/segmentrouting/cli/ShouldProgramCommand.java
index 250fb3b..01e62a0 100644
--- a/impl/src/main/java/org/onosproject/segmentrouting/cli/ShouldProgramCommand.java
+++ b/impl/src/main/java/org/onosproject/segmentrouting/cli/ShouldProgramCommand.java
@@ -24,7 +24,6 @@
 import org.onosproject.segmentrouting.SegmentRoutingService;
 
 import java.util.Map;
-import java.util.Set;
 
 /**
  * Display current shouldProgram map.
@@ -36,13 +35,9 @@
     @Override
     protected void doExecute() {
         SegmentRoutingService srService = AbstractShellCommand.get(SegmentRoutingService.class);
-        Map<Set<DeviceId>, NodeId> shouldProgram = srService.getShouldProgram();
-        Map<DeviceId, Boolean> shouldProgramCache = srService.getShouldProgramCache();
+        Map<DeviceId, NodeId> shouldProgram = srService.getShouldProgramLeaders();
 
         print("shouldProgram");
         shouldProgram.forEach((k, v) -> print("%s -> %s", k, v));
-
-        print("shouldProgramCache");
-        shouldProgramCache.forEach((k, v) -> print("%s -> %s", k, v));
     }
 }
\ No newline at end of file
diff --git a/impl/src/main/java/org/onosproject/segmentrouting/grouphandler/DefaultGroupHandler.java b/impl/src/main/java/org/onosproject/segmentrouting/grouphandler/DefaultGroupHandler.java
index 7920e67..c33c457 100644
--- a/impl/src/main/java/org/onosproject/segmentrouting/grouphandler/DefaultGroupHandler.java
+++ b/impl/src/main/java/org/onosproject/segmentrouting/grouphandler/DefaultGroupHandler.java
@@ -250,9 +250,9 @@
     /**
      * Checks all groups in the src-device of link for neighbor sets that include
      * the dst-device of link, and edits the hash groups according to link up
-     * or down. Should only be called by the master instance of the src-switch
-     * of link. Typically used when there are no route-path changes due to the
-     * link up or down, as the ECMPspg does not change.
+     * or down. Should only be called by the instance leading the programming of
+     * the src-switch of link. Typically used when there are no route-path
+     * changes due to the link up or down, as the ECMPspg does not change.
      *
      * @param link the infrastructure link that has gone down or come up
      * @param linkDown true if link has gone down
@@ -461,9 +461,9 @@
     /**
      * Checks all the hash-groups in the target-switch meant for the destination
      * switch, and either adds or removes buckets to make the neighbor-set
-     * match the given next-hops. Typically called by the master instance of the
-     * destination switch, which may be different from the master instance of the
-     * target switch where hash-group changes are made.
+     * match the given next-hops. Typically called by the instance leading the programming
+     * of the destination switch, which may be different from the instance leading the
+     * programming of the target switch where hash-group changes are made.
      *
      * @param targetSw the switch in which the hash groups will be edited
      * @param nextHops the current next hops for the target switch to reach
@@ -685,7 +685,8 @@
 
     /**
      * Adds or removes a port that has been configured with a vlan to a broadcast group
-     * for bridging. Should only be called by the master instance for this device.
+     * for bridging. Should only be called by the instance leading the programming
+     * for this device.
      *
      * @param port the port on this device that needs to be added/removed to a bcast group
      * @param vlanId the vlan id corresponding to the broadcast domain/group
@@ -1718,22 +1719,13 @@
             this.nextId = null;
         }
 
-        BucketCorrector(Integer nextId) {
-            this.nextId = nextId;
-        }
-
         @Override
         public void run() {
-            if (!srManager.mastershipService.isLocalMaster(deviceId)) {
-                return;
-            }
             DefaultRoutingHandler rh = srManager.getRoutingHandler();
-            if (rh == null) {
+            if (rh == null || !rh.isRoutingStable() || !rh.shouldProgram(deviceId)) {
                 return;
             }
-            if (!rh.isRoutingStable()) {
-                return;
-            }
+
             rh.acquireRoutingLock();
             try {
                 log.trace("running bucket corrector for dev: {}", deviceId);
diff --git a/impl/src/main/java/org/onosproject/segmentrouting/phasedrecovery/api/PhasedRecoveryService.java b/impl/src/main/java/org/onosproject/segmentrouting/phasedrecovery/api/PhasedRecoveryService.java
index 705ecb7..6a30ef7 100644
--- a/impl/src/main/java/org/onosproject/segmentrouting/phasedrecovery/api/PhasedRecoveryService.java
+++ b/impl/src/main/java/org/onosproject/segmentrouting/phasedrecovery/api/PhasedRecoveryService.java
@@ -56,7 +56,8 @@
     boolean isEnabled();
 
     /**
-     * Initializes a device. Only the master of the device is allowed to do this.
+     * Initializes a device. Only the instance leading the programming
+     * of the device is allowed to do this.
      *
      * @param deviceId device ID
      * @return true if the device is initialized successfully and the caller should proceed,
@@ -65,7 +66,8 @@
     boolean init(DeviceId deviceId);
 
     /**
-     * Resets a device. Only the master of the device is allowed to do this.
+     * Resets a device. Only the instance leading the programming
+     * of the device is allowed to do this.
      *
      * @param deviceId device ID
      * @return true if the device is reset successfully.
@@ -89,7 +91,8 @@
     Phase getPhase(DeviceId deviceId);
 
     /**
-     * Sets given device with given recovery phase. Only the master of the device is allowed to do this.
+     * Sets given device with given recovery phase. Only the instance leading the programming
+     * of the device is allowed to do this.
      *
      * @param deviceId device ID
      * @param newPhase recovery phase
diff --git a/impl/src/main/java/org/onosproject/segmentrouting/phasedrecovery/impl/PhasedRecoveryManager.java b/impl/src/main/java/org/onosproject/segmentrouting/phasedrecovery/impl/PhasedRecoveryManager.java
index 8c62a2f..9544b57 100644
--- a/impl/src/main/java/org/onosproject/segmentrouting/phasedrecovery/impl/PhasedRecoveryManager.java
+++ b/impl/src/main/java/org/onosproject/segmentrouting/phasedrecovery/impl/PhasedRecoveryManager.java
@@ -22,7 +22,6 @@
 import org.onosproject.cfg.ComponentConfigService;
 import org.onosproject.core.ApplicationId;
 import org.onosproject.core.CoreService;
-import org.onosproject.mastership.MastershipService;
 import org.onosproject.net.DeviceId;
 import org.onosproject.net.Port;
 import org.onosproject.net.PortNumber;
@@ -90,9 +89,6 @@
     private DeviceAdminService deviceAdminService;
 
     @Reference(cardinality = ReferenceCardinality.MANDATORY)
-    private MastershipService mastershipService;
-
-    @Reference(cardinality = ReferenceCardinality.MANDATORY)
     private StorageService storageService;
 
     @Reference(cardinality = ReferenceCardinality.OPTIONAL)
@@ -157,8 +153,9 @@
             log.info("SegmentRoutingService is not ready");
             return false;
         }
-        if (!mastershipService.isLocalMaster(deviceId)) {
-            log.info("Not master of {}", deviceId);
+
+        if (!srService.shouldProgram(deviceId)) {
+            log.info("Skip init not leading the phase recovery of {}", deviceId);
             return false;
         }
 
@@ -195,8 +192,11 @@
             log.info("SegmentRoutingService is not ready");
             return false;
         }
-        // FIXME Skip mastership checking since master will not be available when a device goes offline
-        //       Improve this when persistent mastership is introduced
+
+        if (!srService.shouldProgram(deviceId)) {
+            log.info("Skip reset not leading the phase recovery of {}", deviceId);
+            return false;
+        }
 
         Phase result = Optional.ofNullable(phasedRecoveryStore.remove(deviceId))
                 .map(Versioned::value).orElse(null);
@@ -222,8 +222,9 @@
             log.info("SegmentRoutingService is not ready");
             return null;
         }
-        if (!mastershipService.isLocalMaster(deviceId)) {
-            log.info("Not master of {}", deviceId);
+
+        if (!srService.shouldProgram(deviceId)) {
+            log.info("Skip setPhase not leading the phase recovery of {}", deviceId);
             return null;
         }
 
@@ -407,4 +408,6 @@
             }
         }
     }
+
+    // FIXME We should handle cluster events to resume the phase recovery
 }
diff --git a/impl/src/main/java/org/onosproject/segmentrouting/xconnect/impl/XconnectManager.java b/impl/src/main/java/org/onosproject/segmentrouting/xconnect/impl/XconnectManager.java
index fecba5a..a20192d 100644
--- a/impl/src/main/java/org/onosproject/segmentrouting/xconnect/impl/XconnectManager.java
+++ b/impl/src/main/java/org/onosproject/segmentrouting/xconnect/impl/XconnectManager.java
@@ -27,9 +27,6 @@
 import org.onlab.packet.MacAddress;
 import org.onlab.packet.VlanId;
 import org.onlab.util.KryoNamespace;
-import org.onosproject.cluster.ClusterService;
-import org.onosproject.cluster.LeadershipService;
-import org.onosproject.cluster.NodeId;
 import org.onosproject.codec.CodecService;
 import org.onosproject.core.ApplicationId;
 import org.onosproject.core.CoreService;
@@ -37,7 +34,6 @@
 import org.onosproject.portloadbalancer.api.PortLoadBalancerId;
 import org.onosproject.portloadbalancer.api.PortLoadBalancerListener;
 import org.onosproject.portloadbalancer.api.PortLoadBalancerService;
-import org.onosproject.mastership.MastershipService;
 import org.onosproject.net.ConnectPoint;
 import org.onosproject.net.DeviceId;
 import org.onosproject.net.Host;
@@ -135,15 +131,6 @@
     @Reference(cardinality = ReferenceCardinality.MANDATORY)
     public FlowObjectiveService flowObjectiveService;
 
-    @Reference(cardinality = ReferenceCardinality.MANDATORY)
-    private LeadershipService leadershipService;
-
-    @Reference(cardinality = ReferenceCardinality.MANDATORY)
-    private ClusterService clusterService;
-
-    @Reference(cardinality = ReferenceCardinality.MANDATORY)
-    public MastershipService mastershipService;
-
     @Reference(cardinality = ReferenceCardinality.OPTIONAL)
     public SegmentRoutingService srService;
 
@@ -398,8 +385,8 @@
             deviceEventExecutor.execute(() -> {
                 DeviceId deviceId = event.subject().id();
                 // Just skip if we are not the leader
-                if (!isLocalLeader(deviceId)) {
-                    log.debug("Not the leader of {}. Skip event {}", deviceId, event);
+                if (!srService.shouldProgram(deviceId)) {
+                    log.debug("Not leading the programming of {}. Skip event {}", deviceId, event);
                     return;
                 }
                 // Populate or revoke according to the device availability
@@ -536,7 +523,7 @@
      * @param endpoints a set of endpoints to be cross-connected
      */
     private void populateXConnect(XconnectKey key, Set<XconnectEndpoint> endpoints) {
-        if (!isLocalLeader(key.deviceId())) {
+        if (!srService.shouldProgram(key.deviceId())) {
             log.debug("Abort populating XConnect {}: {}", key, ERROR_NOT_LEADER);
             return;
         }
@@ -649,7 +636,7 @@
      * @param endpoints XConnect endpoints
      */
     private void revokeXConnect(XconnectKey key, Set<XconnectEndpoint> endpoints) {
-        if (!isLocalLeader(key.deviceId())) {
+        if (!srService.shouldProgram(key.deviceId())) {
             log.debug("Abort revoking XConnect {}: {}", key, ERROR_NOT_LEADER);
             return;
         }
@@ -792,7 +779,7 @@
      */
     private void updateXConnect(XconnectKey key, Set<XconnectEndpoint> prevEndpoints,
                                 Set<XconnectEndpoint> endpoints) {
-        if (!isLocalLeader(key.deviceId())) {
+        if (!srService.shouldProgram(key.deviceId())) {
             log.debug("Abort updating XConnect {}: {}", key, ERROR_NOT_LEADER);
             return;
         }
@@ -965,7 +952,7 @@
     private void updateL2Flooding(DeviceId deviceId, PortNumber port, VlanId vlanId, boolean install) {
         XconnectKey key = new XconnectKey(deviceId, vlanId);
         // Ensure leadership on device
-        if (!isLocalLeader(deviceId)) {
+        if (!srService.shouldProgram(deviceId)) {
             log.debug("Abort updating L2Flood {}: {}", key, ERROR_NOT_LEADER);
             return;
         }
@@ -1260,22 +1247,6 @@
         return ports.stream().anyMatch(p -> !p.equals(pairPort));
     }
 
-    // Custom-built function, when the device is not available we need a fallback mechanism
-    private boolean isLocalLeader(DeviceId deviceId) {
-        if (!mastershipService.isLocalMaster(deviceId)) {
-            // When the device is available we just check the mastership
-            if (deviceService.isAvailable(deviceId)) {
-                return false;
-            }
-            // Fallback with Leadership service - device id is used as topic
-            NodeId leader = leadershipService.runForLeadership(
-                    deviceId.toString()).leaderNodeId();
-            // Verify if this node is the leader
-            return clusterService.getLocalNode().id().equals(leader);
-        }
-        return true;
-    }
-
     private Set<PortNumber> getPhysicalPorts(DeviceId deviceId, XconnectEndpoint endpoint) {
         if (endpoint.type() == XconnectEndpoint.Type.PORT) {
             PortNumber port = ((XconnectPortEndpoint) endpoint).port();
diff --git a/impl/src/test/java/org/onosproject/segmentrouting/DefaultRoutingHandlerTest.java b/impl/src/test/java/org/onosproject/segmentrouting/DefaultRoutingHandlerTest.java
index 059b9ca..10c20bd 100644
--- a/impl/src/test/java/org/onosproject/segmentrouting/DefaultRoutingHandlerTest.java
+++ b/impl/src/test/java/org/onosproject/segmentrouting/DefaultRoutingHandlerTest.java
@@ -15,20 +15,22 @@
  */
 package org.onosproject.segmentrouting;
 
-import com.google.common.collect.Sets;
 import org.junit.Before;
 import org.junit.Test;
 import org.onlab.packet.IpAddress;
 import org.onosproject.cluster.ClusterService;
 import org.onosproject.cluster.DefaultControllerNode;
+import org.onosproject.cluster.Leader;
+import org.onosproject.cluster.Leadership;
+import org.onosproject.cluster.LeadershipService;
 import org.onosproject.cluster.NodeId;
-import org.onosproject.mastership.MastershipService;
 import org.onosproject.net.DeviceId;
 import org.onosproject.net.device.DeviceService;
 import org.onosproject.store.service.StorageService;
 import org.onosproject.store.service.TestConsistentMap;
 import org.onosproject.store.service.TestConsistentMultimap;
 
+import java.util.List;
 import java.util.Optional;
 
 import static org.easymock.EasyMock.createMock;
@@ -36,15 +38,21 @@
 import static org.easymock.EasyMock.replay;
 import static org.easymock.EasyMock.reset;
 import static org.junit.Assert.*;
+import static org.onosproject.segmentrouting.DefaultRoutingHandler.HASH_FUNCTION;
 
 public class DefaultRoutingHandlerTest {
     private SegmentRoutingManager srManager;
     private DefaultRoutingHandler dfh;
+    private MockWorkPartitionService mockWps;
 
     private static final DeviceId DEV1A = DeviceId.deviceId("of:1a");
     private static final DeviceId DEV1B = DeviceId.deviceId("of:1b");
     private static final DeviceId DEV2 = DeviceId.deviceId("of:2");
 
+    private static final EdgePair EDGE_PAIR_1 = new EdgePair(DEV1A, DEV1B);
+    private static final EdgePair EDGE_PAIR_2 = new EdgePair(DEV1B, DEV1A);
+    private static final EdgePair EDGE_PAIR_3 = new EdgePair(DEV2, DeviceId.NONE);
+
     private static final NodeId NODE1 = NodeId.nodeId("192.168.1.1");
     private static final NodeId NODE2 = NodeId.nodeId("192.168.1.2");
     private static final NodeId NODE3 = NodeId.nodeId("192.168.1.3");
@@ -52,35 +60,50 @@
     private static final IpAddress IP2 = IpAddress.valueOf("192.168.1.2");
     private static final IpAddress IP3 = IpAddress.valueOf("192.168.1.3");
 
+    /* This is generated by manually applying the hash function.
+       It depends on the number of partitions defined in the MockWorkPartitionService */
+    private static final String DEV1A_PARTITION_ID = String.valueOf(Math.abs(HASH_FUNCTION.apply(
+            EDGE_PAIR_1).intValue()) % MockWorkPartitionService.NUM_PARTITIONS);
+    private static final String DEV1B_PARTITION_ID = String.valueOf(Math.abs(HASH_FUNCTION.apply(
+            EDGE_PAIR_2).intValue()) % MockWorkPartitionService.NUM_PARTITIONS);
+    private static final String DEV2_PARTITION_ID = String.valueOf(Math.abs(HASH_FUNCTION.apply(
+            EDGE_PAIR_3).intValue()) % MockWorkPartitionService.NUM_PARTITIONS);
+
     @Before
     public void setUp() {
         srManager = createMock(SegmentRoutingManager.class);
         srManager.storageService = createMock(StorageService.class);
-        expect(srManager.storageService.consistentMapBuilder()).andReturn(new TestConsistentMap.Builder<>()).anyTimes();
+        expect(srManager.storageService.consistentMapBuilder()).andReturn(
+                new TestConsistentMap.Builder<>()).anyTimes();
         expect(srManager.storageService.consistentMultimapBuilder()).andReturn(
                 new TestConsistentMultimap.Builder<>()).anyTimes();
         replay(srManager.storageService);
         srManager.routingRulePopulator = createMock(RoutingRulePopulator.class);
         srManager.deviceService = createMock(DeviceService.class);
         srManager.deviceConfiguration = createMock(DeviceConfiguration.class);
-        srManager.mastershipService = createMock(MastershipService.class);
+        mockWps = new MockWorkPartitionService();
+        mockWps.leadershipService = createMock(LeadershipService.class);
+        srManager.workPartitionService = mockWps;
         srManager.clusterService = createMock(ClusterService.class);
         dfh = new DefaultRoutingHandler(srManager);
     }
 
-    private void clearCache() {
-        dfh.invalidateShouldProgramCache(DEV1A);
-        dfh.invalidateShouldProgramCache(DEV1B);
-        dfh.invalidateShouldProgramCache(DEV2);
+    private void clearShouldProgram() {
+        dfh.invalidateShouldProgram(DEV1A);
+        dfh.invalidateShouldProgram(DEV1B);
+        dfh.invalidateShouldProgram(DEV2);
     }
 
-    // Node 1 is the master of switch 1A, 1B, and 2
+    // Node 1 is the leader of switch 1A, 1B, and 2
     @Test
     public void testShouldHandleRoutingCase1() {
-        expect(srManager.mastershipService.getMasterFor(DEV1A)).andReturn(NODE1).anyTimes();
-        expect(srManager.mastershipService.getMasterFor(DEV1B)).andReturn(NODE1).anyTimes();
-        expect(srManager.mastershipService.getMasterFor(DEV2)).andReturn(NODE1).anyTimes();
-        replay(srManager.mastershipService);
+        expect(mockWps.leadershipService.getLeadership(DEV1A_PARTITION_ID)).andReturn(new Leadership(
+                DEV1A_PARTITION_ID, new Leader(NODE1, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        expect(mockWps.leadershipService.getLeadership(DEV1B_PARTITION_ID)).andReturn(new Leadership(
+                DEV1B_PARTITION_ID, new Leader(NODE1, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        expect(mockWps.leadershipService.getLeadership(DEV2_PARTITION_ID)).andReturn(new Leadership(
+                DEV2_PARTITION_ID, new Leader(NODE1, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        replay(mockWps.leadershipService);
 
         expect(srManager.getPairDeviceId(DEV1A)).andReturn(Optional.of(DEV1B)).anyTimes();
         expect(srManager.getPairDeviceId(DEV1B)).andReturn(Optional.of(DEV1A)).anyTimes();
@@ -90,39 +113,64 @@
         // Node 1 should program every device
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE1, IP1)).anyTimes();
         replay(srManager.clusterService);
+
+        // shouldProgram is initially empty
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
+        assertNull(dfh.shouldProgram.get(DEV2));
         assertTrue(dfh.shouldProgram(DEV1A));
         assertTrue(dfh.shouldProgram(DEV1B));
         assertTrue(dfh.shouldProgram(DEV2));
+        assertEquals(NODE1, dfh.shouldProgram.get(DEV1A));
+        assertEquals(NODE1, dfh.shouldProgram.get(DEV1B));
+        assertEquals(NODE1, dfh.shouldProgram.get(DEV2));
 
         reset(srManager.clusterService);
-        clearCache();
+        clearShouldProgram();
 
         // Node 2 should program no device
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE2, IP2)).anyTimes();
         replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
+        assertNull(dfh.shouldProgram.get(DEV2));
         assertFalse(dfh.shouldProgram(DEV1A));
         assertFalse(dfh.shouldProgram(DEV1B));
         assertFalse(dfh.shouldProgram(DEV2));
+        assertNotEquals(NODE2, dfh.shouldProgram.get(DEV1A));
+        assertNotEquals(NODE2, dfh.shouldProgram.get(DEV1B));
+        assertNotEquals(NODE2, dfh.shouldProgram.get(DEV2));
 
         reset(srManager.clusterService);
-        clearCache();
+        clearShouldProgram();
 
         // Node 3 should program no device
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE3, IP3)).anyTimes();
         replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
+        assertNull(dfh.shouldProgram.get(DEV2));
         assertFalse(dfh.shouldProgram(DEV1A));
         assertFalse(dfh.shouldProgram(DEV1B));
         assertFalse(dfh.shouldProgram(DEV2));
+        assertNotEquals(NODE3, dfh.shouldProgram.get(DEV1A));
+        assertNotEquals(NODE3, dfh.shouldProgram.get(DEV1B));
+        assertNotEquals(NODE3, dfh.shouldProgram.get(DEV2));
     }
 
-    // Node 1 is the master of switch 1A, 1B
-    // Node 2 is the master of switch 2
+    /*
+     * Node 1 is the leader of switch 1A, 1B
+     * Node 2 is the leader of switch 2
+     */
     @Test
     public void testShouldHandleRoutingCase2() {
-        expect(srManager.mastershipService.getMasterFor(DEV1A)).andReturn(NODE1).anyTimes();
-        expect(srManager.mastershipService.getMasterFor(DEV1B)).andReturn(NODE1).anyTimes();
-        expect(srManager.mastershipService.getMasterFor(DEV2)).andReturn(NODE2).anyTimes();
-        replay(srManager.mastershipService);
+        expect(mockWps.leadershipService.getLeadership(DEV1A_PARTITION_ID)).andReturn(new Leadership(
+                DEV1A_PARTITION_ID, new Leader(NODE1, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        expect(mockWps.leadershipService.getLeadership(DEV1B_PARTITION_ID)).andReturn(new Leadership(
+                DEV1B_PARTITION_ID, new Leader(NODE1, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        expect(mockWps.leadershipService.getLeadership(DEV2_PARTITION_ID)).andReturn(new Leadership(
+                DEV2_PARTITION_ID, new Leader(NODE2, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        replay(mockWps.leadershipService);
 
         expect(srManager.getPairDeviceId(DEV1A)).andReturn(Optional.of(DEV1B)).anyTimes();
         expect(srManager.getPairDeviceId(DEV1B)).andReturn(Optional.of(DEV1A)).anyTimes();
@@ -132,40 +180,62 @@
         // Node 1 should program 1A, 1B
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE1, IP1)).anyTimes();
         replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
+        assertNull(dfh.shouldProgram.get(DEV2));
         assertTrue(dfh.shouldProgram(DEV1A));
         assertTrue(dfh.shouldProgram(DEV1B));
         assertFalse(dfh.shouldProgram(DEV2));
+        assertEquals(NODE1, dfh.shouldProgram.get(DEV1A));
+        assertEquals(NODE1, dfh.shouldProgram.get(DEV1B));
+        assertNotEquals(NODE1, dfh.shouldProgram.get(DEV2));
 
         reset(srManager.clusterService);
-        clearCache();
+        clearShouldProgram();
 
         // Node 2 should program 2
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE2, IP2)).anyTimes();
         replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
+        assertNull(dfh.shouldProgram.get(DEV2));
         assertFalse(dfh.shouldProgram(DEV1A));
         assertFalse(dfh.shouldProgram(DEV1B));
         assertTrue(dfh.shouldProgram(DEV2));
+        assertNotEquals(NODE2, dfh.shouldProgram.get(DEV1A));
+        assertNotEquals(NODE2, dfh.shouldProgram.get(DEV1B));
+        assertEquals(NODE2, dfh.shouldProgram.get(DEV2));
 
         reset(srManager.clusterService);
-        clearCache();
+        clearShouldProgram();
 
         // Node 3 should program no device
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE3, IP3)).anyTimes();
         replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
+        assertNull(dfh.shouldProgram.get(DEV2));
         assertFalse(dfh.shouldProgram(DEV1A));
         assertFalse(dfh.shouldProgram(DEV1B));
         assertFalse(dfh.shouldProgram(DEV2));
+        assertNotEquals(NODE3, dfh.shouldProgram.get(DEV1A));
+        assertNotEquals(NODE3, dfh.shouldProgram.get(DEV1B));
+        assertNotEquals(NODE3, dfh.shouldProgram.get(DEV2));
     }
 
-    // Node 1 is the master of switch 1A
-    // Node 2 is the master of switch 1B
-    // Node 3 is the master of switch 2
+    /*
+     * Node 1 is the leader of switch 1A, 1B
+     * Node 3 is the leader of switch 2
+     */
     @Test
     public void testShouldHandleRoutingCase3() {
-        expect(srManager.mastershipService.getMasterFor(DEV1A)).andReturn(NODE1).anyTimes();
-        expect(srManager.mastershipService.getMasterFor(DEV1B)).andReturn(NODE2).anyTimes();
-        expect(srManager.mastershipService.getMasterFor(DEV2)).andReturn(NODE3).anyTimes();
-        replay(srManager.mastershipService);
+        expect(mockWps.leadershipService.getLeadership(DEV1A_PARTITION_ID)).andReturn(new Leadership(
+                DEV1A_PARTITION_ID, new Leader(NODE1, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        expect(mockWps.leadershipService.getLeadership(DEV1B_PARTITION_ID)).andReturn(new Leadership(
+                DEV1B_PARTITION_ID, new Leader(NODE1, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        expect(mockWps.leadershipService.getLeadership(DEV2_PARTITION_ID)).andReturn(new Leadership(
+                DEV2_PARTITION_ID, new Leader(NODE3, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        replay(mockWps.leadershipService);
 
         expect(srManager.getPairDeviceId(DEV1A)).andReturn(Optional.of(DEV1B)).anyTimes();
         expect(srManager.getPairDeviceId(DEV1B)).andReturn(Optional.of(DEV1A)).anyTimes();
@@ -175,39 +245,62 @@
         // Node 1 should program 1A, 1B
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE1, IP1)).anyTimes();
         replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
+        assertNull(dfh.shouldProgram.get(DEV2));
         assertTrue(dfh.shouldProgram(DEV1A));
         assertTrue(dfh.shouldProgram(DEV1B));
         assertFalse(dfh.shouldProgram(DEV2));
+        assertEquals(NODE1, dfh.shouldProgram.get(DEV1A));
+        assertEquals(NODE1, dfh.shouldProgram.get(DEV1B));
+        assertNotEquals(NODE1, dfh.shouldProgram.get(DEV2));
 
         reset(srManager.clusterService);
-        clearCache();
+        clearShouldProgram();
 
         // Node 2 should program no device
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE2, IP2)).anyTimes();
         replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
+        assertNull(dfh.shouldProgram.get(DEV2));
         assertFalse(dfh.shouldProgram(DEV1A));
         assertFalse(dfh.shouldProgram(DEV1B));
         assertFalse(dfh.shouldProgram(DEV2));
+        assertNotEquals(NODE2, dfh.shouldProgram.get(DEV1A));
+        assertNotEquals(NODE2, dfh.shouldProgram.get(DEV1B));
+        assertNotEquals(NODE2, dfh.shouldProgram.get(DEV2));
 
         reset(srManager.clusterService);
-        clearCache();
+        clearShouldProgram();
 
         // Node 3 should program 2
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE3, IP3)).anyTimes();
         replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
+        assertNull(dfh.shouldProgram.get(DEV2));
         assertFalse(dfh.shouldProgram(DEV1A));
         assertFalse(dfh.shouldProgram(DEV1B));
         assertTrue(dfh.shouldProgram(DEV2));
+        assertNotEquals(NODE3, dfh.shouldProgram.get(DEV1A));
+        assertNotEquals(NODE3, dfh.shouldProgram.get(DEV1B));
+        assertEquals(NODE3, dfh.shouldProgram.get(DEV2));
     }
 
-    // Node 3 is the master of switch 1A, 1B, 2
-    // Later on, node 1 becomes the master of 1A; Node 2 becomes the master of 1B.
+    /*
+     * Node 2 is the leader of switch 1A, 1B and Node 3 is the leader of 2.
+     * Later on, node 1 becomes the leader of 1A, 1B
+     */
     @Test
     public void testShouldHandleRoutingCase4() {
-        expect(srManager.mastershipService.getMasterFor(DEV1A)).andReturn(NODE3).anyTimes();
-        expect(srManager.mastershipService.getMasterFor(DEV1B)).andReturn(NODE3).anyTimes();
-        expect(srManager.mastershipService.getMasterFor(DEV2)).andReturn(NODE3).anyTimes();
-        replay(srManager.mastershipService);
+        expect(mockWps.leadershipService.getLeadership(DEV1A_PARTITION_ID)).andReturn(new Leadership(
+                DEV1A_PARTITION_ID, new Leader(NODE2, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        expect(mockWps.leadershipService.getLeadership(DEV1B_PARTITION_ID)).andReturn(new Leadership(
+                DEV1B_PARTITION_ID, new Leader(NODE2, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        expect(mockWps.leadershipService.getLeadership(DEV2_PARTITION_ID)).andReturn(new Leadership(
+                DEV2_PARTITION_ID, new Leader(NODE3, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        replay(mockWps.leadershipService);
 
         expect(srManager.getPairDeviceId(DEV1A)).andReturn(Optional.of(DEV1B)).anyTimes();
         expect(srManager.getPairDeviceId(DEV1B)).andReturn(Optional.of(DEV1A)).anyTimes();
@@ -217,75 +310,119 @@
         // Node 1 should program no device
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE1, IP1)).anyTimes();
         replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
+        assertNull(dfh.shouldProgram.get(DEV2));
         assertFalse(dfh.shouldProgram(DEV1A));
         assertFalse(dfh.shouldProgram(DEV1B));
         assertFalse(dfh.shouldProgram(DEV2));
+        assertNotEquals(NODE1, dfh.shouldProgram.get(DEV1A));
+        assertNotEquals(NODE1, dfh.shouldProgram.get(DEV1B));
+        assertNotEquals(NODE1, dfh.shouldProgram.get(DEV2));
 
         reset(srManager.clusterService);
-        clearCache();
+        clearShouldProgram();
 
-        // Node 2 should program no device
+        // Node 2 should program 1A and 1B
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE2, IP2)).anyTimes();
         replay(srManager.clusterService);
-        assertFalse(dfh.shouldProgram(DEV1A));
-        assertFalse(dfh.shouldProgram(DEV1B));
-        assertFalse(dfh.shouldProgram(DEV2));
-
-        reset(srManager.clusterService);
-        clearCache();
-
-        // Node 3 should program 1A, 1B and 2
-        expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE3, IP3)).anyTimes();
-        replay(srManager.clusterService);
-        assertTrue(dfh.shouldProgram(DEV1A));
-        assertTrue(dfh.shouldProgram(DEV1B));
-        assertTrue(dfh.shouldProgram(DEV2));
-
-        // Mastership of switch 1A moves to Node 1
-        reset(srManager.mastershipService);
-        expect(srManager.mastershipService.getMasterFor(DEV1A)).andReturn(NODE1).anyTimes();
-        expect(srManager.mastershipService.getMasterFor(DEV1B)).andReturn(NODE2).anyTimes();
-        expect(srManager.mastershipService.getMasterFor(DEV2)).andReturn(NODE3).anyTimes();
-        replay(srManager.mastershipService);
-
-        reset(srManager.clusterService);
-        clearCache();
-
-        // Node 1 should program 1A, 1B
-        expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE1, IP1)).anyTimes();
-        replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
+        assertNull(dfh.shouldProgram.get(DEV2));
         assertTrue(dfh.shouldProgram(DEV1A));
         assertTrue(dfh.shouldProgram(DEV1B));
         assertFalse(dfh.shouldProgram(DEV2));
+        assertEquals(NODE2, dfh.shouldProgram.get(DEV1A));
+        assertEquals(NODE2, dfh.shouldProgram.get(DEV1B));
+        assertNotEquals(NODE2, dfh.shouldProgram.get(DEV2));
 
         reset(srManager.clusterService);
-        clearCache();
-
-        // Node 2 should program no device
-        expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE2, IP2)).anyTimes();
-        replay(srManager.clusterService);
-        assertFalse(dfh.shouldProgram(DEV1A));
-        assertFalse(dfh.shouldProgram(DEV1B));
-        assertFalse(dfh.shouldProgram(DEV2));
-
-        reset(srManager.clusterService);
-        clearCache();
+        clearShouldProgram();
 
         // Node 3 should program 2
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE3, IP3)).anyTimes();
         replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
+        assertNull(dfh.shouldProgram.get(DEV2));
         assertFalse(dfh.shouldProgram(DEV1A));
         assertFalse(dfh.shouldProgram(DEV1B));
         assertTrue(dfh.shouldProgram(DEV2));
+        assertNotEquals(NODE3, dfh.shouldProgram.get(DEV1A));
+        assertNotEquals(NODE3, dfh.shouldProgram.get(DEV1B));
+        assertEquals(NODE3, dfh.shouldProgram.get(DEV2));
+
+        // Partition of switch 1A moves to Node 1. This can happen for a cluster event
+        reset(mockWps.leadershipService);
+        expect(mockWps.leadershipService.getLeadership(DEV1A_PARTITION_ID)).andReturn(new Leadership(
+                DEV1A_PARTITION_ID, new Leader(NODE1, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        expect(mockWps.leadershipService.getLeadership(DEV1B_PARTITION_ID)).andReturn(new Leadership(
+                DEV1B_PARTITION_ID, new Leader(NODE1, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        expect(mockWps.leadershipService.getLeadership(DEV2_PARTITION_ID)).andReturn(new Leadership(
+                DEV2_PARTITION_ID, new Leader(NODE3, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        replay(mockWps.leadershipService);
+
+        reset(srManager.clusterService);
+        clearShouldProgram();
+
+        // Node 1 should program 1A, 1B
+        expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE1, IP1)).anyTimes();
+        replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
+        assertNull(dfh.shouldProgram.get(DEV2));
+        assertTrue(dfh.shouldProgram(DEV1A));
+        assertTrue(dfh.shouldProgram(DEV1B));
+        assertFalse(dfh.shouldProgram(DEV2));
+        assertEquals(NODE1, dfh.shouldProgram.get(DEV1A));
+        assertEquals(NODE1, dfh.shouldProgram.get(DEV1B));
+        assertNotEquals(NODE1, dfh.shouldProgram.get(DEV2));
+
+        reset(srManager.clusterService);
+        clearShouldProgram();
+
+        // Node 2 should program no device
+        expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE2, IP2)).anyTimes();
+        replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
+        assertNull(dfh.shouldProgram.get(DEV2));
+        assertFalse(dfh.shouldProgram(DEV1A));
+        assertFalse(dfh.shouldProgram(DEV1B));
+        assertFalse(dfh.shouldProgram(DEV2));
+        assertNotEquals(NODE2, dfh.shouldProgram.get(DEV1A));
+        assertNotEquals(NODE2, dfh.shouldProgram.get(DEV1B));
+        assertNotEquals(NODE2, dfh.shouldProgram.get(DEV2));
+
+        reset(srManager.clusterService);
+        clearShouldProgram();
+
+        // Node 3 should program 2
+        expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE3, IP3)).anyTimes();
+        replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
+        assertNull(dfh.shouldProgram.get(DEV2));
+        assertFalse(dfh.shouldProgram(DEV1A));
+        assertFalse(dfh.shouldProgram(DEV1B));
+        assertTrue(dfh.shouldProgram(DEV2));
+        assertNotEquals(NODE3, dfh.shouldProgram.get(DEV1A));
+        assertNotEquals(NODE3, dfh.shouldProgram.get(DEV1B));
+        assertEquals(NODE3, dfh.shouldProgram.get(DEV2));
     }
 
-    // Node 1 is the master of 1A. 1B has no master
-    // Node 2 becomes the master of 1B later
+    /*
+     * Node 1 is the leader of 1A, 1B. Node 2 becomes the leader of 1A, 1B later
+     * shouldP is not purged in time. This can easily happen if we dont get in
+     * time cluster/mastership events. shouldProgram absorbs this negative scenario.
+     */
     @Test
     public void testShouldHandleRoutingCase5() {
-        expect(srManager.mastershipService.getMasterFor(DEV1A)).andReturn(NODE1).anyTimes();
-        expect(srManager.mastershipService.getMasterFor(DEV1B)).andReturn(null).anyTimes();
-        replay(srManager.mastershipService);
+        expect(mockWps.leadershipService.getLeadership(DEV1A_PARTITION_ID)).andReturn(new Leadership(
+                DEV1A_PARTITION_ID, new Leader(NODE1, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        expect(mockWps.leadershipService.getLeadership(DEV1B_PARTITION_ID)).andReturn(new Leadership(
+                DEV1B_PARTITION_ID, new Leader(NODE1, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        replay(mockWps.leadershipService);
 
         expect(srManager.getPairDeviceId(DEV1A)).andReturn(Optional.of(DEV1B)).anyTimes();
         expect(srManager.getPairDeviceId(DEV1B)).andReturn(Optional.of(DEV1A)).anyTimes();
@@ -294,49 +431,65 @@
         // Node 1 should program both 1A and 1B
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE1, IP1)).anyTimes();
         replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
         assertTrue(dfh.shouldProgram(DEV1A));
         assertTrue(dfh.shouldProgram(DEV1B));
+        assertEquals(NODE1, dfh.shouldProgram.get(DEV1A));
+        assertEquals(NODE1, dfh.shouldProgram.get(DEV1B));
 
         reset(srManager.clusterService);
-        clearCache();
+        clearShouldProgram();
 
         // Node 2 should program no device
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE2, IP2)).anyTimes();
         replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
         assertFalse(dfh.shouldProgram(DEV1A));
         assertFalse(dfh.shouldProgram(DEV1B));
+        assertNotEquals(NODE2, dfh.shouldProgram.get(DEV1A));
+        assertNotEquals(NODE2, dfh.shouldProgram.get(DEV1B));
 
-        // Mastership of switch 1B moves to Node 2
-        reset(srManager.mastershipService);
-        expect(srManager.mastershipService.getMasterFor(DEV1A)).andReturn(NODE1).anyTimes();
-        expect(srManager.mastershipService.getMasterFor(DEV1B)).andReturn(NODE2).anyTimes();
-        replay(srManager.mastershipService);
+        // Leadership moves to Node 2
+        reset(mockWps.leadershipService);
+        expect(mockWps.leadershipService.getLeadership(DEV1A_PARTITION_ID)).andReturn(new Leadership(
+                DEV1A_PARTITION_ID, new Leader(NODE2, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        expect(mockWps.leadershipService.getLeadership(DEV1B_PARTITION_ID)).andReturn(new Leadership(
+                DEV1B_PARTITION_ID, new Leader(NODE2, 0, 0), List.of(NODE2, NODE3))).anyTimes();
+        replay(mockWps.leadershipService);
 
         reset(srManager.clusterService);
-        clearCache();
 
         // Node 1 should program 1A, 1B
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE1, IP1)).anyTimes();
         replay(srManager.clusterService);
+        assertNotNull(dfh.shouldProgram.get(DEV1A));
+        assertNotNull(dfh.shouldProgram.get(DEV1B));
         assertTrue(dfh.shouldProgram(DEV1A));
         assertTrue(dfh.shouldProgram(DEV1B));
+        assertEquals(NODE1, dfh.shouldProgram.get(DEV1A));
+        assertEquals(NODE1, dfh.shouldProgram.get(DEV1B));
 
         reset(srManager.clusterService);
-        clearCache();
 
         // Node 2 should program no device
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE2, IP2)).anyTimes();
         replay(srManager.clusterService);
+        assertNotNull(dfh.shouldProgram.get(DEV1A));
+        assertNotNull(dfh.shouldProgram.get(DEV1B));
         assertFalse(dfh.shouldProgram(DEV1A));
         assertFalse(dfh.shouldProgram(DEV1B));
+        assertEquals(NODE1, dfh.shouldProgram.get(DEV1A));
+        assertEquals(NODE1, dfh.shouldProgram.get(DEV1B));
     }
 
-    // Neither 1A or 1B has master
-    @Test
+    // There is no leadership for 1A, 1B. Super-damaged cluster.
+    @Test(expected = NullPointerException.class)
     public void testShouldHandleRoutingCase6() {
-        expect(srManager.mastershipService.getMasterFor(DEV1A)).andReturn(null).anyTimes();
-        expect(srManager.mastershipService.getMasterFor(DEV1B)).andReturn(null).anyTimes();
-        replay(srManager.mastershipService);
+        expect(mockWps.leadershipService.getLeadership(DEV1A_PARTITION_ID)).andReturn(null).anyTimes();
+        expect(mockWps.leadershipService.getLeadership(DEV1B_PARTITION_ID)).andReturn(null).anyTimes();
+        replay(mockWps.leadershipService);
 
         expect(srManager.getPairDeviceId(DEV1A)).andReturn(Optional.of(DEV1B)).anyTimes();
         expect(srManager.getPairDeviceId(DEV1B)).andReturn(Optional.of(DEV1A)).anyTimes();
@@ -345,18 +498,27 @@
         // Node 1 should program no device
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE1, IP1)).anyTimes();
         replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
         assertFalse(dfh.shouldProgram(DEV1A));
         assertFalse(dfh.shouldProgram(DEV1B));
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
 
         reset(srManager.clusterService);
-        clearCache();
+        clearShouldProgram();
 
         // Node 2 should program no device
         expect(srManager.clusterService.getLocalNode()).andReturn(new DefaultControllerNode(NODE2, IP2)).anyTimes();
         replay(srManager.clusterService);
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
         assertFalse(dfh.shouldProgram(DEV1A));
         assertFalse(dfh.shouldProgram(DEV1B));
+        assertNull(dfh.shouldProgram.get(DEV1A));
+        assertNull(dfh.shouldProgram.get(DEV1B));
 
-        assertFalse(dfh.shouldProgram.containsKey(Sets.newHashSet(DEV1A, DEV1B)));
+        assertFalse(dfh.shouldProgram.containsKey(DEV1A));
+        assertFalse(dfh.shouldProgram.containsKey(DEV1B));
     }
 }
\ No newline at end of file
diff --git a/impl/src/test/java/org/onosproject/segmentrouting/HostHandlerTest.java b/impl/src/test/java/org/onosproject/segmentrouting/HostHandlerTest.java
index e9cde67..a4c6fdc 100644
--- a/impl/src/test/java/org/onosproject/segmentrouting/HostHandlerTest.java
+++ b/impl/src/test/java/org/onosproject/segmentrouting/HostHandlerTest.java
@@ -88,8 +88,10 @@
     // Host Mac, VLAN
     private static final ProviderId PROVIDER_ID = ProviderId.NONE;
     private static final MacAddress HOST_MAC = MacAddress.valueOf("00:00:00:00:00:01");
+    private static final MacAddress HOST_5_MAC = MacAddress.valueOf("00:00:00:00:00:05");
     private static final VlanId HOST_VLAN_UNTAGGED = VlanId.NONE;
     private static final HostId HOST_ID_UNTAGGED = HostId.hostId(HOST_MAC, HOST_VLAN_UNTAGGED);
+    private static final HostId HOST_5_ID_UNTAGGED = HostId.hostId(HOST_5_MAC, HOST_VLAN_UNTAGGED);
     private static final VlanId HOST_VLAN_TAGGED = VlanId.vlanId((short) 20);
     private static final HostId HOST_ID_TAGGED = HostId.hostId(HOST_MAC, HOST_VLAN_TAGGED);
     // Host IP
@@ -99,6 +101,7 @@
     private static final IpAddress HOST_IP13 = IpAddress.valueOf("10.0.1.3");
     private static final IpAddress HOST_IP14 = IpAddress.valueOf("10.0.1.4");
     private static final IpAddress HOST_IP33 = IpAddress.valueOf("10.0.3.3");
+    private static final IpAddress HOST_IP51 = IpAddress.valueOf("10.0.5.1");
     // Device
     private static final DeviceId DEV1 = DeviceId.deviceId("of:0000000000000001");
     private static final DeviceId DEV2 = DeviceId.deviceId("of:0000000000000002");
@@ -135,7 +138,7 @@
     private static final HostLocation HOST_LOC42 = new HostLocation(CP42, 0);
     private static final ConnectPoint CP39 = new ConnectPoint(DEV3, P9);
     private static final ConnectPoint CP49 = new ConnectPoint(DEV4, P9);
-    // Conenct Point for mastership test
+    // Connect Point for leadership test and move to invalid locations
     private static final ConnectPoint CP51 = new ConnectPoint(DEV5, P1);
     private static final HostLocation HOST_LOC51 = new HostLocation(CP51, 0);
     private static final ConnectPoint CP61 = new ConnectPoint(DEV6, P1);
@@ -199,11 +202,14 @@
     private static final Host HOST1 = new DefaultHost(PROVIDER_ID, HOST_ID_UNTAGGED, HOST_MAC,
             HOST_VLAN_UNTAGGED, Sets.newHashSet(HOST_LOC11, HOST_LOC21), Sets.newHashSet(HOST_IP11),
             false);
+    private static final Host HOST5 = new DefaultHost(PROVIDER_ID, HOST_5_ID_UNTAGGED, HOST_5_MAC,
+            HOST_VLAN_UNTAGGED, Sets.newHashSet(HOST_LOC51), Sets.newHashSet(HOST_IP51),
+            false);
 
     // A set of hosts
-    private static final Set<Host> HOSTS = Sets.newHashSet(HOST1);
-    // A set of devices of which we have mastership
-    private static final Set<DeviceId> LOCAL_DEVICES = Sets.newHashSet(DEV1, DEV2, DEV3, DEV4);
+    private static final Set<Host> HOSTS = Sets.newHashSet(HOST1, HOST5);
+    // A set of devices of which we have leadership
+    private static final Set<DeviceId> LED_DEVICES = Sets.newHashSet(DEV1, DEV2, DEV3, DEV4);
     // A set of interfaces
     private static final Set<Interface> INTERFACES = Sets.newHashSet(INTF11, INTF12, INTF13, INTF21,
             INTF22, INTF31, INTF32, INTF33, INTF39, INTF41, INTF42, INTF49);
@@ -233,7 +239,8 @@
         // Initialize Segment Routing Manager
         SegmentRoutingManager srManager = new MockSegmentRoutingManager(NEXT_TABLE, Maps.newHashMap());
         srManager.storageService = createMock(StorageService.class);
-        expect(srManager.storageService.consistentMapBuilder()).andReturn(new TestConsistentMap.Builder<>()).anyTimes();
+        expect(srManager.storageService.consistentMapBuilder()).andReturn(
+                new TestConsistentMap.Builder<>()).anyTimes();
         expect(srManager.storageService.consistentMultimapBuilder()).andReturn(
                 new TestConsistentMultimap.Builder<>()).anyTimes();
         replay(srManager.storageService);
@@ -241,9 +248,9 @@
         srManager.deviceConfiguration = new DeviceConfiguration(srManager);
         srManager.flowObjectiveService = new MockFlowObjectiveService(BRIDGING_TABLE, NEXT_TABLE);
         srManager.routingRulePopulator = new MockRoutingRulePopulator(srManager, ROUTING_TABLE);
-        srManager.defaultRoutingHandler = new MockDefaultRoutingHandler(srManager, SUBNET_TABLE, ROUTING_TABLE);
+        srManager.defaultRoutingHandler = new MockDefaultRoutingHandler(srManager, SUBNET_TABLE,
+                ROUTING_TABLE, LED_DEVICES);
         srManager.interfaceService = new MockInterfaceService(INTERFACES);
-        srManager.mastershipService = new MockMastershipService(LOCAL_DEVICES);
         srManager.hostService = new MockHostService(HOSTS);
         srManager.cfgService = mockNetworkConfigRegistry;
         mockLocationProbingService = new MockHostProbingService();
@@ -1016,4 +1023,15 @@
         assertEquals(Sets.newHashSet(HOST_LOC11, HOST_LOC12), hostHandler.effectiveLocations(regularHost));
         assertEquals(Sets.newHashSet(HOST_LOC21, HOST_LOC22), hostHandler.effectiveLocations(auxHost));
     }
+
+    @Test
+    public void initOfNonLedDevices() {
+        hostHandler.init(DEV5);
+        assertEquals(0, ROUTING_TABLE.size());
+        assertEquals(0, BRIDGING_TABLE.size());
+
+        hostHandler.init(DEV6);
+        assertEquals(0, ROUTING_TABLE.size());
+        assertEquals(0, BRIDGING_TABLE.size());
+    }
 }
diff --git a/impl/src/test/java/org/onosproject/segmentrouting/MockDefaultRoutingHandler.java b/impl/src/test/java/org/onosproject/segmentrouting/MockDefaultRoutingHandler.java
index 0002948..d82908c 100644
--- a/impl/src/test/java/org/onosproject/segmentrouting/MockDefaultRoutingHandler.java
+++ b/impl/src/test/java/org/onosproject/segmentrouting/MockDefaultRoutingHandler.java
@@ -29,13 +29,16 @@
 public class MockDefaultRoutingHandler extends DefaultRoutingHandler {
     private Map<ConnectPoint, Set<IpPrefix>> subnetTable;
     private Map<MockRoutingTableKey, MockRoutingTableValue> routingTable;
+    private Set<DeviceId> ledDevices;
 
     MockDefaultRoutingHandler(SegmentRoutingManager srManager,
                               Map<ConnectPoint, Set<IpPrefix>> subnetTable,
-                              Map<MockRoutingTableKey, MockRoutingTableValue> routingTable) {
+                              Map<MockRoutingTableKey, MockRoutingTableValue> routingTable,
+                              Set<DeviceId> ledDevices) {
         super(srManager);
         this.subnetTable = subnetTable;
         this.routingTable = routingTable;
+        this.ledDevices = ledDevices;
     }
 
     @Override
@@ -65,7 +68,7 @@
     }
 
     @Override
-    protected boolean shouldProgram(DeviceId deviceId) {
-        return true;
+    public boolean shouldProgram(DeviceId deviceId) {
+        return ledDevices.contains(deviceId);
     }
 }
\ No newline at end of file
diff --git a/impl/src/test/java/org/onosproject/segmentrouting/MockWorkPartitionService.java b/impl/src/test/java/org/onosproject/segmentrouting/MockWorkPartitionService.java
new file mode 100644
index 0000000..b2d48a6
--- /dev/null
+++ b/impl/src/test/java/org/onosproject/segmentrouting/MockWorkPartitionService.java
@@ -0,0 +1,38 @@
+/*
+ * Copyright 2017-present Open Networking Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onosproject.segmentrouting;
+
+import org.onosproject.cluster.LeadershipService;
+import org.onosproject.cluster.NodeId;
+import org.onosproject.cluster.PartitionId;
+import org.onosproject.net.intent.WorkPartitionServiceAdapter;
+
+import java.util.function.Function;
+
+public class MockWorkPartitionService extends WorkPartitionServiceAdapter {
+
+    LeadershipService leadershipService;
+    static final int NUM_PARTITIONS = 14;
+
+    @Override
+    public <K> NodeId getLeader(K id, Function<K, Long> hasher) {
+        int partition = Math.abs(hasher.apply(id).intValue()) % NUM_PARTITIONS;
+        PartitionId partitionId = new PartitionId(partition);
+        return leadershipService.getLeadership(partitionId.toString()).leaderNodeId();
+    }
+
+}
diff --git a/impl/src/test/java/org/onosproject/segmentrouting/RouteHandlerTest.java b/impl/src/test/java/org/onosproject/segmentrouting/RouteHandlerTest.java
index e09aaa7..2ab4d01 100644
--- a/impl/src/test/java/org/onosproject/segmentrouting/RouteHandlerTest.java
+++ b/impl/src/test/java/org/onosproject/segmentrouting/RouteHandlerTest.java
@@ -137,8 +137,8 @@
     private static final Set<Host> HOSTS = Sets.newHashSet(H1, H2, H3D, H4);
     private static final Set<Host> HOSTS_ONE_FAIL = Sets.newHashSet(H1, H2, H3S);
     private static final Set<Host> HOSTS_BOTH_FAIL = Sets.newHashSet(H1, H2);
-    // A set of devices of which we have mastership
-    private static final Set<DeviceId> LOCAL_DEVICES = Sets.newHashSet(CP1.deviceId(), CP2.deviceId());
+    // A set of devices of which we have leadership
+    private static final Set<DeviceId> LED_DEVICES = Sets.newHashSet(CP1.deviceId(), CP2.deviceId());
     // A set of interfaces
     private static final InterfaceIpAddress IF_IP1 =
             new InterfaceIpAddress(IpAddress.valueOf("10.0.1.254"), IpPrefix.valueOf("10.0.1.254/24"));
@@ -180,7 +180,8 @@
         // Initialize Segment Routing Manager
         srManager = new MockSegmentRoutingManager(NEXT_TABLE, ROUTER_MACS);
         srManager.storageService = createMock(StorageService.class);
-        expect(srManager.storageService.consistentMapBuilder()).andReturn(new TestConsistentMap.Builder<>()).anyTimes();
+        expect(srManager.storageService.consistentMapBuilder()).andReturn(
+                new TestConsistentMap.Builder<>()).anyTimes();
         expect(srManager.storageService.consistentMultimapBuilder()).andReturn(
                 new TestConsistentMultimap.Builder<>()).anyTimes();
         replay(srManager.storageService);
@@ -188,9 +189,9 @@
         srManager.deviceConfiguration = createMock(DeviceConfiguration.class);
         srManager.flowObjectiveService = new MockFlowObjectiveService(BRIDGING_TABLE, NEXT_TABLE);
         srManager.routingRulePopulator = new MockRoutingRulePopulator(srManager, ROUTING_TABLE);
-        srManager.defaultRoutingHandler = new MockDefaultRoutingHandler(srManager, SUBNET_TABLE, ROUTING_TABLE);
+        srManager.defaultRoutingHandler = new MockDefaultRoutingHandler(srManager, SUBNET_TABLE, ROUTING_TABLE,
+                LED_DEVICES);
         srManager.interfaceService = new MockInterfaceService(INTERFACES);
-        srManager.mastershipService = new MockMastershipService(LOCAL_DEVICES);
         hostService = new MockHostService(HOSTS);
         srManager.hostService = hostService;
         srManager.cfgService = mockNetworkConfigRegistry;
@@ -845,19 +846,17 @@
         expectLastCall().once();
         replay(srManager.deviceConfiguration);
 
+        // We don't lead of:0000000000000004 where RR4 next hop is attached
         re = new RouteEvent(RouteEvent.Type.ALTERNATIVE_ROUTES_CHANGED, RR1, null,
                 Sets.newHashSet(RR2, RR4), Sets.newHashSet(RR1, RR2, RR4));
         routeHandler.processAlternativeRoutesChanged(re);
 
-        assertEquals(2, ROUTING_TABLE.size());
+        assertEquals(1, ROUTING_TABLE.size());
         rtv1 = ROUTING_TABLE.get(new MockRoutingTableKey(CP2.deviceId(), P1));
         assertEquals(M2, rtv1.macAddress);
         assertEquals(V2, rtv1.vlanId);
         assertEquals(CP2.port(), rtv1.portNumber);
-        rtv2 = ROUTING_TABLE.get(new MockRoutingTableKey(CP4.deviceId(), P1));
-        assertEquals(M4, rtv2.macAddress);
-        assertEquals(V4, rtv2.vlanId);
-        assertEquals(CP4.port(), rtv2.portNumber);
+        assertNull(ROUTING_TABLE.get(new MockRoutingTableKey(CP4.deviceId(), P1)));
 
         assertEquals(2, SUBNET_TABLE.size());
         assertTrue(SUBNET_TABLE.get(CP2).contains(P1));
@@ -865,4 +864,19 @@
 
         verify(srManager.deviceConfiguration);
     }
+
+    @Test
+    public void initOfNonLedDevices() {
+        // We dont lead CP4
+        ROUTE_STORE.put(P1, Sets.newHashSet(RR4));
+
+        routeHandler.init(CP4.deviceId());
+
+        // No routes programmed in the devices
+        assertEquals(0, ROUTING_TABLE.size());
+        assertNull(ROUTING_TABLE.get(new MockRoutingTableKey(CP4.deviceId(), P1)));
+
+        // But we still store the subnets
+        assertEquals(1, SUBNET_TABLE.size());
+    }
 }