You are viewing a plain text version of this content. The canonical link for it is here.
Posted to pr@cassandra.apache.org by "belliottsmith (via GitHub)" <gi...@apache.org> on 2023/02/07 23:25:21 UTC

[GitHub] [cassandra-accord] belliottsmith commented on a diff in pull request #33: Immutable state

belliottsmith commented on code in PR #33:
URL: https://github.com/apache/cassandra-accord/pull/33#discussion_r1096110519


##########
accord-core/src/main/java/accord/local/AsyncCommandStores.java:
##########
@@ -1,92 +0,0 @@
-/*

Review Comment:
   Why erase these classes?



##########
accord-core/src/main/java/accord/local/StateUpdate.java:
##########
@@ -0,0 +1,95 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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 accord.local;
+
+public class StateUpdate<V, U extends StateUpdate<V, U>>

Review Comment:
   unused?



##########
accord-core/src/main/java/accord/local/ImmutableState.java:
##########
@@ -0,0 +1,202 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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 accord.local;
+
+/**
+ * Since metadata instances are immutable, there can be several copies floating around in memory, all but one
+ * of which is stale. This can lead to difficult to diagnose bugs, especially when an implementation side cache
+ * is involved.
+ * The ImmutableState base class defines the various lifecycle stage and helps restrict what the user does with it,
+ * with the goal or throwing an exception as soon as an illegal usage occurs, instead of after.
+ *
+ * An up to date instances can have one of 2 statuses, DORMANT or ACTIVE. An instance is only ACTIVE in the time
+ * between when the safe store for it's current operation is created, and closed, and is otherwise marked DORMANT.
+ * While DORMANT, it cannot be read from or updated. This is to help detect leaked instances being read from or
+ * updated when they shouldn't be.
+ *
+ * Once an update has created a superseding instance, the original instance is marked SUPERSEDED. It can then be
+ * marked CLEANING_UP, during which time its fields can be read to assist in determining what has been updated.
+ * From CLEANING_UP, an instance can be marked INVALIDATED to indicate that any access is illegal. An instance
+ * marked SUPERSEDED can also go directly to INVALIDATED, in the case of intermediate updates.
+ */
+public abstract class ImmutableState

Review Comment:
   It seems like most of this stuff is to debug, primarily during development, but also is potentially easily forgotten to add to subclasses. I wonder if this would be better as something partially added with byte-weaving, or aspect-oriented programming when debugging is enabled? We could automatically add the checks to each sub-method, and also byte-weave in the state field, so we have no runtime cost while also making sure to capture every method, and also avoid polluting the extending classes.



##########
accord-core/src/main/java/accord/local/Commands.java:
##########
@@ -0,0 +1,1073 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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 accord.local;
+
+import accord.api.ProgressLog.ProgressShard;
+import accord.api.Result;
+import accord.api.RoutingKey;
+import accord.local.Command.WaitingOn;
+import accord.primitives.*;
+import accord.utils.Invariants;
+import accord.utils.async.AsyncChain;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import javax.annotation.Nonnull;
+import javax.annotation.Nullable;
+
+import java.util.Arrays;
+import java.util.Map;
+import java.util.function.Consumer;
+import java.util.function.Function;
+
+import static accord.api.ProgressLog.ProgressShard.*;
+import static accord.api.ProgressLog.ProgressShard.Local;
+import static accord.local.Commands.EnsureAction.*;
+import static accord.local.Status.*;
+import static accord.local.Status.Known.ExecuteAtOnly;
+import static accord.primitives.Route.isFullRoute;
+
+public class Commands
+{
+    private static final Logger logger = LoggerFactory.getLogger(Commands.class);
+
+    private Commands()
+    {
+    }
+
+    private static Ranges covers(@Nullable PartialTxn txn)
+    {
+        return txn == null ? null : txn.covering();
+    }
+
+    private static Ranges covers(@Nullable PartialDeps deps)
+    {
+        return deps == null ? null : deps.covering;
+    }
+
+    private static boolean hasQuery(PartialTxn txn)
+    {
+        return txn != null && txn.query() != null;
+    }
+
+    /**
+     * true iff this commandStore owns the given key on the given epoch
+     */
+    public static boolean owns(SafeCommandStore safeStore, long epoch, RoutingKey someKey)
+    {
+        return safeStore.ranges().at(epoch).contains(someKey);
+    }
+
+    public static RoutingKey noProgressKey()
+    {
+        return NO_PROGRESS_KEY;
+    }
+
+    public enum AcceptOutcome {Success, Redundant, RejectedBallot}
+
+    public static AcceptOutcome preaccept(SafeCommandStore safeStore, TxnId txnId, PartialTxn partialTxn, Route<?> route, @Nullable RoutingKey progressKey)
+    {
+        return preacceptOrRecover(safeStore, txnId, partialTxn, route, progressKey, Ballot.ZERO);
+    }
+
+    public static AcceptOutcome recover(SafeCommandStore safeStore, TxnId txnId, PartialTxn partialTxn, Route<?> route, @Nullable RoutingKey progressKey, Ballot ballot)
+    {
+        return preacceptOrRecover(safeStore, txnId, partialTxn, route, progressKey, ballot);
+    }
+
+    private static AcceptOutcome preacceptOrRecover(SafeCommandStore safeStore, TxnId txnId, PartialTxn partialTxn, Route<?> route, @Nullable RoutingKey progressKey, Ballot ballot)
+    {
+        Command command = safeStore.command(txnId);
+
+        int compareBallots = command.promised().compareTo(ballot);
+        if (compareBallots > 0)
+        {
+            logger.trace("{}: skipping preaccept - higher ballot witnessed ({})", txnId, command.promised());
+            return AcceptOutcome.RejectedBallot;
+        }
+
+        if (command.known().definition.isKnown())
+        {
+            Invariants.checkState(command.status() == Invalidated || command.executeAt() != null);
+            logger.trace("{}: skipping preaccept - already known ({})", txnId, command.status());
+            // in case of Ballot.ZERO, we must either have a competing recovery coordinator or have late delivery of the
+            // preaccept; in the former case we should abandon coordination, and in the latter we have already completed
+            return ballot.equals(Ballot.ZERO) ? AcceptOutcome.Redundant : AcceptOutcome.Success;
+        }
+
+        Ranges coordinateRanges = coordinateRanges(safeStore, command);
+        Invariants.checkState(!coordinateRanges.isEmpty());
+        Command.Update update = safeStore.beginUpdate(command);
+        ProgressShard shard = progressShard(safeStore, update, route, progressKey, coordinateRanges);
+        if (!validate(update, Ranges.EMPTY, coordinateRanges, shard, route, Set, partialTxn, Set, null, Ignore))
+            throw new IllegalStateException();
+
+        // FIXME: this should go into a consumer method
+        set(safeStore, update, Ranges.EMPTY, coordinateRanges, shard, route, partialTxn, Set, null, Ignore);
+        if (command.executeAt() == null)
+        {
+            // unlike in the Accord paper, we partition shards within a node, so that to ensure a total order we must either:
+            //  - use a global logical clock to issue new timestamps; or
+            //  - assign each shard _and_ process a unique id, and use both as components of the timestamp
+            // if we are performing recovery (i.e. non-zero ballot), do not permit a fast path decision as we want to
+            // invalidate any transactions that were not completed by their initial coordinator
+            Timestamp executeAt = ballot.equals(Ballot.ZERO)
+                    ? safeStore.preaccept(txnId, partialTxn.keys())
+                    : safeStore.time().uniqueNow(txnId);
+            command = update.preaccept(executeAt, ballot);
+            safeStore.progressLog().preaccepted(safeStore, txnId, shard);
+        }
+        else
+        {
+            // TODO (expected, ?): in the case that we are pre-committed but had not been preaccepted/accepted, should we inform progressLog?
+            command = update.markDefined(ballot);
+        }
+
+        safeStore.notifyListeners(command);
+        return AcceptOutcome.Success;
+    }
+
+    public static boolean preacceptInvalidate(SafeCommandStore safeStore, TxnId txnId, Ballot ballot)
+    {
+        Command command = safeStore.command(txnId);
+        if (command.promised().compareTo(ballot) > 0)
+        {
+            logger.trace("{}: skipping preacceptInvalidate - witnessed higher ballot ({})", command.txnId(), command.promised());
+            return false;
+        }
+        safeStore.beginUpdate(command).updatePromised(ballot);
+        return true;
+    }
+
+    public static AcceptOutcome accept(SafeCommandStore safeStore, TxnId txnId, Ballot ballot, PartialRoute<?> route, Seekables<?, ?> keys, @Nullable RoutingKey progressKey, Timestamp executeAt, PartialDeps partialDeps)
+    {
+        Command command = safeStore.command(txnId);
+        if (command.promised().compareTo(ballot) > 0)
+        {
+            logger.trace("{}: skipping accept - witnessed higher ballot ({} > {})", txnId, command.promised(), ballot);
+            return AcceptOutcome.RejectedBallot;
+        }
+
+        if (command.hasBeen(PreCommitted))
+        {
+            logger.trace("{}: skipping accept - already committed ({})", txnId, command.status());
+            return AcceptOutcome.Redundant;
+        }
+
+        Ranges coordinateRanges = coordinateRanges(safeStore, command);
+        Ranges acceptRanges = txnId.epoch() == executeAt.epoch() ? coordinateRanges : safeStore.ranges().between(txnId.epoch(), executeAt.epoch());
+        Invariants.checkState(!acceptRanges.isEmpty());
+
+        Command.Update update = safeStore.beginUpdate(command);
+        ProgressShard shard = progressShard(safeStore, update, route, progressKey, coordinateRanges);
+
+        if (!validate(update, coordinateRanges, Ranges.EMPTY, shard, route, Ignore, null, Ignore, partialDeps, Set))
+        {
+            throw new AssertionError("Invalid response from validate function");
+        }
+
+        // TODO (desired, clarity/efficiency): we don't need to set the route here, and perhaps we don't even need to
+        //  distributed partialDeps at all, since all we gain is not waiting for these transactions to commit during
+        //  recovery. We probably don't want to directly persist a Route in any other circumstances, either, to ease persistence.
+        set(safeStore, update, coordinateRanges, acceptRanges, shard, route, null, Ignore, partialDeps, Set);
+
+        // set only registers by transaction keys, which we mightn't already have received
+        if (!command.known().isDefinitionKnown())
+            update.registerWith(keys, acceptRanges);
+
+        command = update.accept(executeAt, ballot);
+        safeStore.progressLog().accepted(safeStore, txnId, shard);
+        safeStore.notifyListeners(command);
+
+        return AcceptOutcome.Success;
+    }
+
+    public static AcceptOutcome acceptInvalidate(SafeCommandStore safeStore, TxnId txnId, Ballot ballot)
+    {
+        Command command = safeStore.command(txnId);
+        if (command.promised().compareTo(ballot) > 0)
+        {
+            logger.trace("{}: skipping accept invalidated - witnessed higher ballot ({} > {})", command.txnId(), command.promised(), ballot);
+            return AcceptOutcome.RejectedBallot;
+        }
+
+        if (command.hasBeen(PreCommitted))
+        {
+            logger.trace("{}: skipping accept invalidated - already committed ({})", command.txnId(), command.status());
+            return AcceptOutcome.Redundant;
+        }
+
+        Command.Update update = safeStore.beginUpdate(command);
+        logger.trace("{}: accepted invalidated", update.txnId());
+
+        command = update.acceptInvalidated(ballot);
+        safeStore.notifyListeners(command);
+        return AcceptOutcome.Success;
+    }
+
+    public enum CommitOutcome {Success, Redundant, Insufficient;}
+
+
+    // relies on mutual exclusion for each key
+    public static CommitOutcome commit(SafeCommandStore safeStore, TxnId txnId, Route<?> route, @Nullable RoutingKey progressKey, @Nullable PartialTxn partialTxn, Timestamp executeAt, PartialDeps partialDeps)
+    {
+        Command command = safeStore.command(txnId);
+
+        if (command.hasBeen(PreCommitted))
+        {
+            logger.trace("{}: skipping commit - already committed ({})", txnId, command.status());
+            if (!executeAt.equals(command.executeAt()) || command.status() == Invalidated)
+                safeStore.agent().onInconsistentTimestamp(command, (command.status() == Invalidated ? Timestamp.NONE : command.executeAt()), executeAt);
+
+            if (command.hasBeen(Committed))
+                return CommitOutcome.Redundant;
+        }
+
+        Ranges coordinateRanges = coordinateRanges(safeStore, command);
+        // TODO (expected, consider): consider ranges between coordinateRanges and executeRanges? Perhaps don't need them
+        Ranges executeRanges = executeRanges(safeStore, executeAt);
+
+        Command.Update update = safeStore.beginUpdate(command);
+        ProgressShard shard = progressShard(safeStore, update, route, progressKey, coordinateRanges);
+
+        if (!validate(update, coordinateRanges, executeRanges, shard, route, Check, partialTxn, Add, partialDeps, Set))
+        {
+            update.updateAttributes();
+            return CommitOutcome.Insufficient;
+        }
+
+        // FIXME: split up set
+        set(safeStore, update, coordinateRanges, executeRanges, shard, route, partialTxn, Add, partialDeps, Set);
+
+        logger.trace("{}: committed with executeAt: {}, deps: {}", txnId, executeAt, partialDeps);
+        WaitingOn waitingOn = populateWaitingOn(safeStore, txnId, executeAt, partialDeps);
+        command = update.commit(executeAt, waitingOn);
+
+        safeStore.progressLog().committed(safeStore, txnId, shard);
+
+        // TODO (expected, safety): introduce intermediate status to avoid reentry when notifying listeners (which might notify us)
+        maybeExecute(safeStore, command, shard, true, true);
+        return CommitOutcome.Success;
+    }
+
+    // relies on mutual exclusion for each key
+    public static void precommit(SafeCommandStore safeStore, TxnId txnId, Timestamp executeAt)
+    {
+        Command command = safeStore.command(txnId);
+        if (command.hasBeen(PreCommitted))
+        {
+            logger.trace("{}: skipping precommit - already committed ({})", txnId, command.status());
+            if (executeAt.equals(command.executeAt()) && command.status() != Invalidated)
+                return;
+
+            safeStore.agent().onInconsistentTimestamp(command, (command.status() == Invalidated ? Timestamp.NONE : command.executeAt()), executeAt);
+        }
+
+        Command.Update update = safeStore.beginUpdate(command);
+        command = update.precommit(executeAt);
+        safeStore.notifyListeners(command);
+        logger.trace("{}: precommitted with executeAt: {}", txnId, executeAt);
+    }
+
+    protected static WaitingOn populateWaitingOn(SafeCommandStore safeStore, TxnId txnId, Timestamp executeAt, PartialDeps partialDeps)
+    {
+        Ranges ranges = safeStore.ranges().since(executeAt.epoch());
+        if (ranges == null)
+            return WaitingOn.EMPTY;
+
+        WaitingOn.Update update = new WaitingOn.Update();
+        partialDeps.forEach(ranges, depId -> {
+            Command command = safeStore.ifLoaded(depId);
+            if (command == null)
+            {
+                update.addWaitingOnCommit(depId);
+                safeStore.addAndInvokeListener(depId, txnId);
+            }
+            else
+            {
+                switch (command.status())
+                {
+                    default:
+                        throw new IllegalStateException();
+                    case NotWitnessed:
+                    case PreAccepted:
+                    case Accepted:
+                    case AcceptedInvalidate:
+                        // we don't know when these dependencies will execute, and cannot execute until we do
+
+                        Command.addListener(safeStore, command, Command.listener(txnId));
+                        update.addWaitingOnCommit(command.txnId());
+                        break;
+                    case Committed:
+                        // TODO (desired, efficiency): split into ReadyToRead and ReadyToWrite;
+                        //                             the distributed read can be performed as soon as those keys are ready,
+                        //                             and in parallel with any other reads. the client can even ACK immediately after;
+                        //                             only the write needs to be postponed until other in-progress reads complete
+                    case ReadyToExecute:
+                    case PreApplied:
+                    case Applied:
+                        command = Command.addListener(safeStore, command, Command.listener(txnId));
+                        insertPredecessor(txnId, executeAt, update, command);
+                    case Invalidated:
+                        break;
+                }
+            }
+        });
+        return update.build();
+    }
+
+    // TODO (expected, ?): commitInvalidate may need to update cfks _if_ possible
+    public static void commitInvalidate(SafeCommandStore safeStore, TxnId txnId)
+    {
+        Command command = safeStore.command(txnId);
+        if (command.hasBeen(PreCommitted))
+        {
+            logger.trace("{}: skipping commit invalidated - already committed ({})", txnId, command.status());
+            if (!command.hasBeen(Invalidated))
+                safeStore.agent().onInconsistentTimestamp(command, Timestamp.NONE, command.executeAt());
+
+            return;
+        }
+
+        ProgressShard shard = progressShard(safeStore, command);
+        safeStore.progressLog().invalidated(safeStore, txnId, shard);
+
+        Command.Update update = safeStore.beginUpdate(command);
+        if (command.partialDeps() == null)
+            update.partialDeps(PartialDeps.NONE);
+        command = update.commitInvalidated(txnId);
+        logger.trace("{}: committed invalidated", txnId);
+
+        safeStore.notifyListeners(command);
+    }
+
+    public enum ApplyOutcome {Success, Redundant, Insufficient}
+
+
+    public static ApplyOutcome apply(SafeCommandStore safeStore, TxnId txnId, long untilEpoch, Route<?> route, Timestamp executeAt, @Nullable PartialDeps partialDeps, Writes writes, Result result)
+    {
+        Command command = safeStore.command(txnId);
+        if (command.hasBeen(PreApplied) && executeAt.equals(command.executeAt()))
+        {
+            logger.trace("{}: skipping apply - already executed ({})", txnId, command.status());
+            return ApplyOutcome.Redundant;
+        }
+        else if (command.hasBeen(PreCommitted) && !executeAt.equals(command.executeAt()))
+        {
+            safeStore.agent().onInconsistentTimestamp(command, command.executeAt(), executeAt);
+        }
+
+        Ranges coordinateRanges = coordinateRanges(safeStore, command);
+        Ranges executeRanges = executeRanges(safeStore, executeAt);
+        if (untilEpoch < safeStore.latestEpoch())
+        {
+            Ranges expectedRanges = safeStore.ranges().between(executeAt.epoch(), untilEpoch);
+            Invariants.checkState(expectedRanges.containsAll(executeRanges));
+        }
+
+        Command.Update update = safeStore.beginUpdate(command);
+        ProgressShard shard = progressShard(safeStore, update, route, coordinateRanges);
+
+        if (!validate(update, coordinateRanges, executeRanges, shard, route, Check, null, Check, partialDeps, command.hasBeen(Committed) ? Add : TrySet))
+        {
+            update.updateAttributes();
+            return ApplyOutcome.Insufficient; // TODO (expected, consider): this should probably be an assertion failure if !TrySet
+        }
+
+        WaitingOn waitingOn = !command.hasBeen(Committed) ? populateWaitingOn(safeStore, txnId, executeAt, partialDeps) : command.asCommitted().waitingOn();
+        set(safeStore, update, coordinateRanges, executeRanges, shard, route, null, Check, partialDeps, command.hasBeen(Committed) ? Add : TrySet);
+
+        command = update.preapplied(executeAt, waitingOn, writes, result);
+        logger.trace("{}: apply, status set to Executed with executeAt: {}, deps: {}", txnId, executeAt, partialDeps);
+
+        maybeExecute(safeStore, command, shard, true, true);
+        safeStore.progressLog().executed(safeStore, txnId, shard);
+
+        return ApplyOutcome.Success;
+    }
+
+    public static void listenerUpdate(SafeCommandStore safeStore, Command listener, Command command)
+    {
+        logger.trace("{}: updating as listener in response to change on {} with status {} ({})",
+                     listener.txnId(), command.txnId(), command.status(), command);
+        switch (command.status())
+        {
+            default:
+                throw new IllegalStateException();
+            case NotWitnessed:
+            case PreAccepted:
+            case Accepted:
+            case AcceptedInvalidate:
+                break;
+
+            case Committed:
+            case ReadyToExecute:
+            case PreApplied:
+            case Applied:
+            case Invalidated:
+                updatePredecessorAndMaybeExecute(safeStore, listener.asCommitted(), command, false);
+                break;
+        }
+    }
+
+    protected static void postApply(SafeCommandStore safeStore, TxnId txnId)
+    {
+        Command command = safeStore.command(txnId);
+        logger.trace("{} applied, setting status to Applied and notifying listeners", command.txnId());
+        command = safeStore.beginUpdate(command).applied();
+        safeStore.notifyListeners(command);
+    }
+
+    private static Function<SafeCommandStore, Void> callPostApply(TxnId txnId)
+    {
+        return safeStore -> {
+            postApply(safeStore, txnId);
+            return null;
+        };
+    }
+
+    protected static AsyncChain<Void> applyChain(SafeCommandStore safeStore, Command.Executed command)
+    {
+        // important: we can't include a reference to *this* in the lambda, since the C* implementation may evict
+        // the command instance from memory between now and the write completing (and post apply being called)
+        CommandStore unsafeStore = safeStore.commandStore();
+        TxnId txnId = command.txnId();
+        PreLoadContext context = command.contextForSelf();
+        return command.writes().apply(safeStore).flatMap(unused -> unsafeStore.submit(context, callPostApply(txnId)));
+    }
+
+    private static void apply(SafeCommandStore safeStore, Command.Executed command)
+    {
+        applyChain(safeStore, command).begin(safeStore.agent());
+    }
+
+    // TODO (expected, API consistency): maybe split into maybeExecute and maybeApply?
+    private static boolean maybeExecute(SafeCommandStore safeStore, Command command, ProgressShard shard, boolean alwaysNotifyListeners, boolean notifyWaitingOn)

Review Comment:
   maybe accept `Committed`?



##########
accord-core/src/main/java/accord/local/SafeCommandStore.java:
##########
@@ -47,11 +48,27 @@
     Command ifLoaded(TxnId txnId);
     Command command(TxnId txnId);
 
+    CommandsForKey ifLoaded(RoutableKey key);

Review Comment:
   Should we be exposing `CommandsForKey` here and elsewhere? We had gone to some lengths to relegate `CommandsForKey` to an implementation detail, to ensure we can treat key and range transactions consistently (and, also, because it can then more easily be dismantled into dedicated cache structures).
   
   Looking at the patch more generally, it seems `CommandsForKey` has been promoted to a very central concept from an entirely hidden one, and I don't think this is necessary, and is probably counterproductive for both consistency with range transactions and for optimising the behaviour currently encoded by `CommandsForKey`.



##########
accord-core/src/main/java/accord/local/Command.java:
##########
@@ -18,1178 +18,1435 @@
 
 package accord.local;
 
-import accord.api.*;
-import accord.local.Status.Durability;
-import accord.local.Status.Known;
+import accord.api.Data;
+import accord.api.Result;
+import accord.api.RoutingKey;
+import accord.impl.CommandsForKey;
+import accord.impl.CommandsForKeys;
 import accord.primitives.*;
-import accord.primitives.Writes;
 import accord.utils.Invariants;
-import org.apache.cassandra.utils.concurrent.Future;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
-import java.util.function.Function;
-
-import static accord.local.Status.*;
-import static accord.local.Status.Known.*;
-import static accord.local.Status.Known.Done;
-import static accord.local.Status.Known.ExecuteAtOnly;
-import static accord.primitives.Route.isFullRoute;
-import static accord.utils.Utils.listOf;
-
-import javax.annotation.Nonnull;
+import accord.utils.Utils;
+import accord.utils.async.AsyncChain;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSortedMap;
+import com.google.common.collect.ImmutableSortedSet;
+
 import javax.annotation.Nullable;
+import java.util.*;
 
-import accord.api.ProgressLog.ProgressShard;
-import accord.primitives.Ranges;
-import accord.primitives.Ballot;
-import accord.primitives.PartialDeps;
-import accord.primitives.PartialTxn;
-import accord.primitives.Route;
-import accord.primitives.Timestamp;
-import accord.primitives.TxnId;
-import accord.api.Result;
-import accord.api.RoutingKey;
+import static accord.local.Status.Durability.Local;
+import static accord.local.Status.Durability.NotDurable;
+import static accord.local.Status.Known.DefinitionOnly;
+import static accord.utils.Utils.*;
+import static java.lang.String.format;
 
-import static accord.api.ProgressLog.ProgressShard.Home;
-import static accord.api.ProgressLog.ProgressShard.Local;
-import static accord.api.ProgressLog.ProgressShard.No;
-import static accord.api.ProgressLog.ProgressShard.Unsure;
-import static accord.local.Command.EnsureAction.Add;
-import static accord.local.Command.EnsureAction.Check;
-import static accord.local.Command.EnsureAction.Ignore;
-import static accord.local.Command.EnsureAction.Set;
-import static accord.local.Command.EnsureAction.TrySet;
-
-public abstract class Command implements CommandListener, BiConsumer<SafeCommandStore, CommandListener>, PreLoadContext
+public abstract class Command extends ImmutableState
 {
-    private static final Logger logger = LoggerFactory.getLogger(Command.class);
+    // sentinel value to indicate a command requested in a preexecute context was not found
+    // should not escape the safe command store
+    public static final Command EMPTY = new Command()
+    {
+        @Override public Route<?> route() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public RoutingKey progressKey() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public RoutingKey homeKey() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public TxnId txnId() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Ballot promised() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Status.Durability durability() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public ImmutableSet<CommandListener> listeners() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public SaveStatus saveStatus() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Timestamp executeAt() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Ballot accepted() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public PartialTxn partialTxn() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Nullable
+        @Override public PartialDeps partialDeps() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
 
-    public abstract TxnId txnId();
+        @Override
+        public String toString()
+        {
+            return "Command(EMPTY)";
+        }
+    };
 
-    // TODO (desirable, API consistency): should any of these calls be replaced by corresponding known() registers?
-    public boolean hasBeen(Status status)
+    static
     {
-        return status().hasBeen(status);
+        EMPTY.markInvalidated();
     }
 
-    public boolean has(Known known)
+    static PreLoadContext contextForCommand(Command command)
     {
-        return known.isSatisfiedBy(saveStatus().known);
+        Invariants.checkState(command.hasBeen(Status.PreAccepted) && command.partialTxn() != null);
+        return command instanceof PreLoadContext ? (PreLoadContext) command : PreLoadContext.contextFor(command.txnId(), command.partialTxn().keys());
     }
 
-    public boolean has(Definition definition)
+    private static Status.Durability durability(Status.Durability durability, SaveStatus status)
     {
-        return known().definition.compareTo(definition) >= 0;
+        if (status.compareTo(SaveStatus.PreApplied) >= 0 && durability == NotDurable)
+            return Local; // not necessary anywhere, but helps for logical consistency
+        return durability;
     }
 
-    public boolean has(Outcome outcome)
+    public interface CommonAttributes
     {
-        return known().outcome.compareTo(outcome) >= 0;
+        TxnId txnId();
+        Status.Durability durability();
+        RoutingKey homeKey();
+        RoutingKey progressKey();
+        Route<?> route();
+        PartialTxn partialTxn();
+        PartialDeps partialDeps();
+        ImmutableSet<CommandListener> listeners();
     }
 
-    public boolean is(Status status)
+    public static class SerializerSupport
     {
-        return status() == status;
-    }
-
-    /**
-     * homeKey is a global value that defines the home shard - the one tasked with ensuring the transaction is finished.
-     * progressKey is a local value that defines the local shard responsible for ensuring progress on the transaction.
-     * This will be homeKey if it is owned by the node, and some other key otherwise. If not the home shard, the progress
-     * shard has much weaker responsibilities, only ensuring that the home shard has durably witnessed the txnId.
-     *
-     * TODO (expected, efficiency): we probably do not want to save this on its own, as we probably want to
-     *  minimize IO interactions and discrete registers, so will likely reference commit log entries directly
-     *  At which point we may impose a requirement that only a Route can be saved, not a homeKey on its own.
-     *  Once this restriction is imposed, we no longer need to pass around Routable.Domain with TxnId.
-     */
-    public abstract RoutingKey homeKey();
-    protected abstract void setHomeKey(RoutingKey key);
-
-    public abstract RoutingKey progressKey();
-    protected abstract void setProgressKey(RoutingKey key);
-
-    /**
-     * If this is the home shard, we require that this is a Route for all states &gt; NotWitnessed;
-     * otherwise for the local progress shard this is ordinarily a PartialRoute, and for other shards this is not set,
-     * so that there is only one copy per node that can be consulted to construct the full set of involved keys.
-     *
-     * If hasBeen(Committed) this must contain the keys for both txnId.epoch and executeAt.epoch
-     */
-    public abstract @Nullable Route<?> route();
-    protected abstract void setRoute(Route<?> route);
-
-    public abstract PartialTxn partialTxn();
-    protected abstract void setPartialTxn(PartialTxn txn);
-
-    public abstract Ballot promised();
-    protected abstract void setPromised(Ballot ballot);
-
-    public abstract Ballot accepted();
-    protected abstract void setAccepted(Ballot ballot);
-
-    public abstract Timestamp executeAt();
-    protected abstract void setExecuteAt(Timestamp timestamp);
-
-    /**
-     * While !hasBeen(Committed), used only as a register for Accept state, used by Recovery
-     * If hasBeen(Committed), represents the full deps owned by this range for execution at both txnId.epoch
-     * AND executeAt.epoch so that it may be used for Recovery (which contacts only txnId.epoch topology),
-     * but also for execution.
-     */
-    public abstract PartialDeps partialDeps();
-    protected abstract void setPartialDeps(PartialDeps deps);
-
-    public abstract Writes writes();
-    protected abstract void setWrites(Writes writes);
-
-    public abstract Result result();
-    protected abstract void setResult(Result result);
-
-    public abstract SaveStatus saveStatus();
-    protected abstract void setSaveStatus(SaveStatus status);
-
-    public Status status() { return saveStatus().status; }
-    protected void setStatus(Status status) { setSaveStatus(SaveStatus.get(status, known())); }
-
-    public Known known() { return saveStatus().known; }
-
-    public abstract Durability durability();
-    public abstract void setDurability(Durability v);
+        public static Command.Listener listener(TxnId txnId)
+        {
+            return new Command.Listener(txnId);
+        }
 
-    public abstract Command addListener(CommandListener listener);
-    public abstract void removeListener(CommandListener listener);
-    protected abstract void notifyListeners(SafeCommandStore safeStore);
+        public static NotWitnessed notWitnessed(CommonAttributes attributes, Ballot promised)
+        {
+            return NotWitnessed.Factory.create(attributes, promised);
+        }
 
-    protected abstract void addWaitingOnCommit(TxnId txnId);
-    protected abstract void removeWaitingOnCommit(TxnId txnId);
-    protected abstract TxnId firstWaitingOnCommit();
+        public static Preaccepted preaccepted(CommonAttributes common, Timestamp executeAt, Ballot promised)
+        {
+            return Preaccepted.Factory.create(common, executeAt, promised);
+        }
 
-    protected abstract void addWaitingOnApplyIfAbsent(TxnId txnId, Timestamp executeAt);
-    protected abstract TxnId firstWaitingOnApply(@Nullable TxnId ifExecutesBefore);
+        public static Accepted accepted(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted)
+        {
+            return Accepted.Factory.create(common, status, executeAt, promised, accepted);
+        }
 
-    protected abstract void removeWaitingOn(TxnId txnId, Timestamp executeAt);
-    protected abstract boolean isWaitingOnDependency();
+        public static Committed committed(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply)
+        {
+            return Committed.Factory.create(common, status, executeAt, promised, accepted, waitingOnCommit, waitingOnApply);
+        }
 
-    public boolean hasBeenWitnessed()
-    {
-        return partialTxn() != null;
+        public static Executed executed(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply, Writes writes, Result result)
+        {
+            return Executed.Factory.create(common, status, executeAt, promised, accepted, waitingOnCommit, waitingOnApply, writes, result);
+        }
     }
 
-    @Override
-    public Iterable<TxnId> txnIds()
+    private static SaveStatus validateCommandClass(SaveStatus status, Class<?> expected, Class<?> actual)
     {
-        return Collections.singleton(txnId());
+        if (actual != expected)
+        {
+            throw new IllegalStateException(format("Cannot instantiate %s for status %s. %s expected",
+                                                   actual.getSimpleName(), status, expected.getSimpleName()));
+        }
+        return status;
     }
 
-    @Override
-    public Seekables<?, ?> keys()
+    private static SaveStatus validateCommandClass(SaveStatus status, Class<?> klass)
     {
-        // TODO (expected, consider): when do we need this, and will it always be sufficient?
-        return partialTxn().keys();
+        switch (status)
+        {
+            case NotWitnessed:
+                return validateCommandClass(status, NotWitnessed.class, klass);
+            case PreAccepted:
+                return validateCommandClass(status, Preaccepted.class, klass);
+            case AcceptedInvalidate:
+            case AcceptedInvalidateWithDefinition:
+            case Accepted:
+            case AcceptedWithDefinition:
+                return validateCommandClass(status, Accepted.class, klass);
+            case Committed:
+            case ReadyToExecute:
+                return validateCommandClass(status, Committed.class, klass);
+            case PreApplied:
+            case Applied:
+            case Invalidated:
+                return validateCommandClass(status, Executed.class, klass);
+            default:
+                throw new IllegalStateException("Unhandled status " + status);
+        }
     }
 
-    public void setDurability(SafeCommandStore safeStore, Durability durability, RoutingKey homeKey, @Nullable Timestamp executeAt)
+    public static Command addListener(SafeCommandStore safeStore, Command command, CommandListener listener)
     {
-        updateHomeKey(safeStore, homeKey);
-        if (executeAt != null && hasBeen(PreCommitted) && !this.executeAt().equals(executeAt))
-            safeStore.agent().onInconsistentTimestamp(this, this.executeAt(), executeAt);
-        setDurability(durability);
+        return safeStore.beginUpdate(command).addListener(listener).updateAttributes();
     }
 
-    public enum AcceptOutcome
+    public static Command removeListener(SafeCommandStore safeStore, Command command, CommandListener listener)
     {
-        Success, Redundant, RejectedBallot
+        return safeStore.beginUpdate(command).removeListener(listener).updateAttributes();
     }
 
-    public AcceptOutcome preaccept(SafeCommandStore safeStore, PartialTxn partialTxn, Route<?> route, @Nullable RoutingKey progressKey)
+    public static Committed updateWaitingOn(SafeCommandStore safeStore, Committed command, WaitingOn.Update waitingOn)
     {
-        return preacceptOrRecover(safeStore, partialTxn, route, progressKey, Ballot.ZERO);
+        if (!waitingOn.hasChanges())
+            return command;
+
+        Update update = safeStore.beginUpdate(command);
+        Committed updated =  command instanceof Executed ?
+                Executed.Factory.update(command.asExecuted(), update, waitingOn.build()) :
+                Committed.Factory.update(command, update, waitingOn.build());
+        return update.complete(updated);
     }
 
-    public AcceptOutcome recover(SafeCommandStore safeStore, PartialTxn partialTxn, Route<?> route, @Nullable RoutingKey progressKey, Ballot ballot)
+    public static class Listener implements CommandListener
     {
-        return preacceptOrRecover(safeStore, partialTxn, route, progressKey, ballot);
-    }
+        protected final TxnId listenerId;
 
-    private AcceptOutcome preacceptOrRecover(SafeCommandStore safeStore, PartialTxn partialTxn, Route<?> route, @Nullable RoutingKey progressKey, Ballot ballot)
-    {
-        int compareBallots = promised().compareTo(ballot);
-        if (compareBallots > 0)
+        private Listener(TxnId listenerId)
         {
-            logger.trace("{}: skipping preaccept - higher ballot witnessed ({})", txnId(), promised());
-            return AcceptOutcome.RejectedBallot;
+            this.listenerId = listenerId;
         }
-        else if (compareBallots < 0)
+
+        @Override
+        public boolean equals(Object o)
         {
-            // save the new ballot as a promise
-            setPromised(ballot);
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+            Listener that = (Listener) o;
+            return listenerId.equals(that.listenerId);
         }
 
-        if (known().definition.isKnown())
+        @Override
+        public int hashCode()
         {
-            Invariants.checkState(status() == Invalidated || executeAt() != null);
-            logger.trace("{}: skipping preaccept - already known ({})", txnId(), status());
-            // in case of Ballot.ZERO, we must either have a competing recovery coordinator or have late delivery of the
-            // preaccept; in the former case we should abandon coordination, and in the latter we have already completed
-            return ballot.equals(Ballot.ZERO) ? AcceptOutcome.Redundant : AcceptOutcome.Success;
+            return Objects.hash(listenerId);
         }
 
-        Ranges coordinateRanges = coordinateRanges(safeStore);
-        Invariants.checkState(!coordinateRanges.isEmpty());
-        ProgressShard shard = progressShard(safeStore, route, progressKey, coordinateRanges);
-        if (!validate(Ranges.EMPTY, coordinateRanges, shard, route, Set, partialTxn, Set, null, Ignore))
-            throw new IllegalStateException();
-
-        if (executeAt() == null)
+        @Override
+        public String toString()
         {
-            TxnId txnId = txnId();
-            // unlike in the Accord paper, we partition shards within a node, so that to ensure a total order we must either:
-            //  - use a global logical clock to issue new timestamps; or
-            //  - assign each shard _and_ process a unique id, and use both as components of the timestamp
-            // if we are performing recovery (i.e. non-zero ballot), do not permit a fast path decision as we want to
-            // invalidate any transactions that were not completed by their initial coordinator
-            if (ballot.equals(Ballot.ZERO)) setExecuteAt(safeStore.preaccept(txnId, partialTxn.keys()));
-            else setExecuteAt(safeStore.time().uniqueNow(txnId));
+            return "ListenerProxy{" + listenerId + '}';
+        }
 
-            if (status() == NotWitnessed)
-                setStatus(PreAccepted);
-            safeStore.progressLog().preaccepted(this, shard);
+        public TxnId txnId()
+        {
+            return listenerId;
         }
-        else
+
+        @Override
+        public void onChange(SafeCommandStore safeStore, TxnId txnId)
         {
-            // TODO (expected, ?): in the case that we are pre-committed but had not been preaccepted/accepted, should we inform progressLog?
-            setSaveStatus(SaveStatus.enrich(saveStatus(), DefinitionOnly));
+            Commands.listenerUpdate(safeStore, safeStore.command(listenerId), safeStore.command(txnId));
         }
-        set(safeStore, Ranges.EMPTY, coordinateRanges, shard, route, partialTxn, Set, null, Ignore);
 
-        notifyListeners(safeStore);
-        return AcceptOutcome.Success;
+        @Override
+        public PreLoadContext listenerPreLoadContext(TxnId caller)
+        {
+            return PreLoadContext.contextFor(Utils.listOf(listenerId, caller), Keys.EMPTY);
+        }
     }
 
-    public boolean preacceptInvalidate(Ballot ballot)
+    public static CommandListener listener(TxnId txnId)
     {
-        if (promised().compareTo(ballot) > 0)
-        {
-            logger.trace("{}: skipping preacceptInvalidate - witnessed higher ballot ({})", txnId(), promised());
-            return false;
-        }
-        setPromised(ballot);
-        return true;
+        return new Listener(txnId);
     }
 
-    public AcceptOutcome accept(SafeCommandStore safeStore, Ballot ballot, PartialRoute<?> route, Seekables<?, ?> keys, @Nullable RoutingKey progressKey, Timestamp executeAt, PartialDeps partialDeps)
+    private abstract static class AbstractCommand extends Command
     {
-        if (this.promised().compareTo(ballot) > 0)
+        private final TxnId txnId;
+        private final SaveStatus status;
+        private final Status.Durability durability;
+        private final RoutingKey homeKey;

Review Comment:
   We probably don't need this except for when `NotWitnessed` - and perhaps `NotWitnessed` should not extend this class? Perhaps `Empty` and `NotWitnessed` could share a common ancestor?



##########
accord-core/src/main/java/accord/local/Command.java:
##########
@@ -18,1178 +18,1435 @@
 
 package accord.local;
 
-import accord.api.*;
-import accord.local.Status.Durability;
-import accord.local.Status.Known;
+import accord.api.Data;
+import accord.api.Result;
+import accord.api.RoutingKey;
+import accord.impl.CommandsForKey;
+import accord.impl.CommandsForKeys;
 import accord.primitives.*;
-import accord.primitives.Writes;
 import accord.utils.Invariants;
-import org.apache.cassandra.utils.concurrent.Future;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
-import java.util.function.Function;
-
-import static accord.local.Status.*;
-import static accord.local.Status.Known.*;
-import static accord.local.Status.Known.Done;
-import static accord.local.Status.Known.ExecuteAtOnly;
-import static accord.primitives.Route.isFullRoute;
-import static accord.utils.Utils.listOf;
-
-import javax.annotation.Nonnull;
+import accord.utils.Utils;
+import accord.utils.async.AsyncChain;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSortedMap;
+import com.google.common.collect.ImmutableSortedSet;
+
 import javax.annotation.Nullable;
+import java.util.*;
 
-import accord.api.ProgressLog.ProgressShard;
-import accord.primitives.Ranges;
-import accord.primitives.Ballot;
-import accord.primitives.PartialDeps;
-import accord.primitives.PartialTxn;
-import accord.primitives.Route;
-import accord.primitives.Timestamp;
-import accord.primitives.TxnId;
-import accord.api.Result;
-import accord.api.RoutingKey;
+import static accord.local.Status.Durability.Local;
+import static accord.local.Status.Durability.NotDurable;
+import static accord.local.Status.Known.DefinitionOnly;
+import static accord.utils.Utils.*;
+import static java.lang.String.format;
 
-import static accord.api.ProgressLog.ProgressShard.Home;
-import static accord.api.ProgressLog.ProgressShard.Local;
-import static accord.api.ProgressLog.ProgressShard.No;
-import static accord.api.ProgressLog.ProgressShard.Unsure;
-import static accord.local.Command.EnsureAction.Add;
-import static accord.local.Command.EnsureAction.Check;
-import static accord.local.Command.EnsureAction.Ignore;
-import static accord.local.Command.EnsureAction.Set;
-import static accord.local.Command.EnsureAction.TrySet;
-
-public abstract class Command implements CommandListener, BiConsumer<SafeCommandStore, CommandListener>, PreLoadContext
+public abstract class Command extends ImmutableState
 {
-    private static final Logger logger = LoggerFactory.getLogger(Command.class);
+    // sentinel value to indicate a command requested in a preexecute context was not found
+    // should not escape the safe command store
+    public static final Command EMPTY = new Command()
+    {
+        @Override public Route<?> route() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public RoutingKey progressKey() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public RoutingKey homeKey() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public TxnId txnId() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Ballot promised() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Status.Durability durability() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public ImmutableSet<CommandListener> listeners() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public SaveStatus saveStatus() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Timestamp executeAt() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Ballot accepted() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public PartialTxn partialTxn() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Nullable
+        @Override public PartialDeps partialDeps() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
 
-    public abstract TxnId txnId();
+        @Override
+        public String toString()
+        {
+            return "Command(EMPTY)";
+        }
+    };
 
-    // TODO (desirable, API consistency): should any of these calls be replaced by corresponding known() registers?
-    public boolean hasBeen(Status status)
+    static
     {
-        return status().hasBeen(status);
+        EMPTY.markInvalidated();
     }
 
-    public boolean has(Known known)
+    static PreLoadContext contextForCommand(Command command)
     {
-        return known.isSatisfiedBy(saveStatus().known);
+        Invariants.checkState(command.hasBeen(Status.PreAccepted) && command.partialTxn() != null);
+        return command instanceof PreLoadContext ? (PreLoadContext) command : PreLoadContext.contextFor(command.txnId(), command.partialTxn().keys());
     }
 
-    public boolean has(Definition definition)
+    private static Status.Durability durability(Status.Durability durability, SaveStatus status)
     {
-        return known().definition.compareTo(definition) >= 0;
+        if (status.compareTo(SaveStatus.PreApplied) >= 0 && durability == NotDurable)
+            return Local; // not necessary anywhere, but helps for logical consistency
+        return durability;
     }
 
-    public boolean has(Outcome outcome)
+    public interface CommonAttributes
     {
-        return known().outcome.compareTo(outcome) >= 0;
+        TxnId txnId();
+        Status.Durability durability();
+        RoutingKey homeKey();
+        RoutingKey progressKey();
+        Route<?> route();
+        PartialTxn partialTxn();
+        PartialDeps partialDeps();
+        ImmutableSet<CommandListener> listeners();
     }
 
-    public boolean is(Status status)
+    public static class SerializerSupport
     {
-        return status() == status;
-    }
-
-    /**
-     * homeKey is a global value that defines the home shard - the one tasked with ensuring the transaction is finished.
-     * progressKey is a local value that defines the local shard responsible for ensuring progress on the transaction.
-     * This will be homeKey if it is owned by the node, and some other key otherwise. If not the home shard, the progress
-     * shard has much weaker responsibilities, only ensuring that the home shard has durably witnessed the txnId.
-     *
-     * TODO (expected, efficiency): we probably do not want to save this on its own, as we probably want to
-     *  minimize IO interactions and discrete registers, so will likely reference commit log entries directly
-     *  At which point we may impose a requirement that only a Route can be saved, not a homeKey on its own.
-     *  Once this restriction is imposed, we no longer need to pass around Routable.Domain with TxnId.
-     */
-    public abstract RoutingKey homeKey();
-    protected abstract void setHomeKey(RoutingKey key);
-
-    public abstract RoutingKey progressKey();
-    protected abstract void setProgressKey(RoutingKey key);
-
-    /**
-     * If this is the home shard, we require that this is a Route for all states &gt; NotWitnessed;
-     * otherwise for the local progress shard this is ordinarily a PartialRoute, and for other shards this is not set,
-     * so that there is only one copy per node that can be consulted to construct the full set of involved keys.
-     *
-     * If hasBeen(Committed) this must contain the keys for both txnId.epoch and executeAt.epoch
-     */
-    public abstract @Nullable Route<?> route();
-    protected abstract void setRoute(Route<?> route);
-
-    public abstract PartialTxn partialTxn();
-    protected abstract void setPartialTxn(PartialTxn txn);
-
-    public abstract Ballot promised();
-    protected abstract void setPromised(Ballot ballot);
-
-    public abstract Ballot accepted();
-    protected abstract void setAccepted(Ballot ballot);
-
-    public abstract Timestamp executeAt();
-    protected abstract void setExecuteAt(Timestamp timestamp);
-
-    /**
-     * While !hasBeen(Committed), used only as a register for Accept state, used by Recovery
-     * If hasBeen(Committed), represents the full deps owned by this range for execution at both txnId.epoch
-     * AND executeAt.epoch so that it may be used for Recovery (which contacts only txnId.epoch topology),
-     * but also for execution.
-     */
-    public abstract PartialDeps partialDeps();
-    protected abstract void setPartialDeps(PartialDeps deps);
-
-    public abstract Writes writes();
-    protected abstract void setWrites(Writes writes);
-
-    public abstract Result result();
-    protected abstract void setResult(Result result);
-
-    public abstract SaveStatus saveStatus();
-    protected abstract void setSaveStatus(SaveStatus status);
-
-    public Status status() { return saveStatus().status; }
-    protected void setStatus(Status status) { setSaveStatus(SaveStatus.get(status, known())); }
-
-    public Known known() { return saveStatus().known; }
-
-    public abstract Durability durability();
-    public abstract void setDurability(Durability v);
+        public static Command.Listener listener(TxnId txnId)
+        {
+            return new Command.Listener(txnId);
+        }
 
-    public abstract Command addListener(CommandListener listener);
-    public abstract void removeListener(CommandListener listener);
-    protected abstract void notifyListeners(SafeCommandStore safeStore);
+        public static NotWitnessed notWitnessed(CommonAttributes attributes, Ballot promised)
+        {
+            return NotWitnessed.Factory.create(attributes, promised);
+        }
 
-    protected abstract void addWaitingOnCommit(TxnId txnId);
-    protected abstract void removeWaitingOnCommit(TxnId txnId);
-    protected abstract TxnId firstWaitingOnCommit();
+        public static Preaccepted preaccepted(CommonAttributes common, Timestamp executeAt, Ballot promised)
+        {
+            return Preaccepted.Factory.create(common, executeAt, promised);
+        }
 
-    protected abstract void addWaitingOnApplyIfAbsent(TxnId txnId, Timestamp executeAt);
-    protected abstract TxnId firstWaitingOnApply(@Nullable TxnId ifExecutesBefore);
+        public static Accepted accepted(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted)
+        {
+            return Accepted.Factory.create(common, status, executeAt, promised, accepted);
+        }
 
-    protected abstract void removeWaitingOn(TxnId txnId, Timestamp executeAt);
-    protected abstract boolean isWaitingOnDependency();
+        public static Committed committed(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply)
+        {
+            return Committed.Factory.create(common, status, executeAt, promised, accepted, waitingOnCommit, waitingOnApply);
+        }
 
-    public boolean hasBeenWitnessed()
-    {
-        return partialTxn() != null;
+        public static Executed executed(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply, Writes writes, Result result)
+        {
+            return Executed.Factory.create(common, status, executeAt, promised, accepted, waitingOnCommit, waitingOnApply, writes, result);
+        }
     }
 
-    @Override
-    public Iterable<TxnId> txnIds()
+    private static SaveStatus validateCommandClass(SaveStatus status, Class<?> expected, Class<?> actual)
     {
-        return Collections.singleton(txnId());
+        if (actual != expected)
+        {
+            throw new IllegalStateException(format("Cannot instantiate %s for status %s. %s expected",
+                                                   actual.getSimpleName(), status, expected.getSimpleName()));
+        }
+        return status;
     }
 
-    @Override
-    public Seekables<?, ?> keys()
+    private static SaveStatus validateCommandClass(SaveStatus status, Class<?> klass)
     {
-        // TODO (expected, consider): when do we need this, and will it always be sufficient?
-        return partialTxn().keys();
+        switch (status)
+        {
+            case NotWitnessed:
+                return validateCommandClass(status, NotWitnessed.class, klass);
+            case PreAccepted:
+                return validateCommandClass(status, Preaccepted.class, klass);
+            case AcceptedInvalidate:
+            case AcceptedInvalidateWithDefinition:
+            case Accepted:
+            case AcceptedWithDefinition:
+                return validateCommandClass(status, Accepted.class, klass);
+            case Committed:
+            case ReadyToExecute:
+                return validateCommandClass(status, Committed.class, klass);
+            case PreApplied:
+            case Applied:
+            case Invalidated:
+                return validateCommandClass(status, Executed.class, klass);
+            default:
+                throw new IllegalStateException("Unhandled status " + status);
+        }
     }
 
-    public void setDurability(SafeCommandStore safeStore, Durability durability, RoutingKey homeKey, @Nullable Timestamp executeAt)
+    public static Command addListener(SafeCommandStore safeStore, Command command, CommandListener listener)

Review Comment:
   Can't help but feel that for add/remove listener and `updateWaitingOn` the balance of cost:benefit isn't necessarily in favour of immutability. We could be selective in our level of immutability, to make the lifecycle a bit easier to manage. But perhaps we can look at this later, once we have deterministic processing and can simply evict the cache directly to memtable (so we won't expect to have more than one live copy, and the immutability is just about clarity).



##########
accord-core/src/main/java/accord/messages/Accept.java:
##########
@@ -240,16 +242,15 @@ public void process()
         @Override
         public AcceptReply apply(SafeCommandStore safeStore)
         {
-            Command command = safeStore.command(txnId);
-            switch (command.acceptInvalidate(safeStore, ballot))
+            switch (Commands.acceptInvalidate(safeStore, txnId, ballot))

Review Comment:
   Maybe with the new style it's better to just return the new `Command` and check if it has our ballot accepted? We could have a helper method to check for redundancy.



##########
accord-core/src/main/java/accord/local/Command.java:
##########
@@ -18,1178 +18,1435 @@
 
 package accord.local;
 
-import accord.api.*;
-import accord.local.Status.Durability;
-import accord.local.Status.Known;
+import accord.api.Data;
+import accord.api.Result;
+import accord.api.RoutingKey;
+import accord.impl.CommandsForKey;
+import accord.impl.CommandsForKeys;
 import accord.primitives.*;
-import accord.primitives.Writes;
 import accord.utils.Invariants;
-import org.apache.cassandra.utils.concurrent.Future;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
-import java.util.function.Function;
-
-import static accord.local.Status.*;
-import static accord.local.Status.Known.*;
-import static accord.local.Status.Known.Done;
-import static accord.local.Status.Known.ExecuteAtOnly;
-import static accord.primitives.Route.isFullRoute;
-import static accord.utils.Utils.listOf;
-
-import javax.annotation.Nonnull;
+import accord.utils.Utils;
+import accord.utils.async.AsyncChain;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSortedMap;
+import com.google.common.collect.ImmutableSortedSet;
+
 import javax.annotation.Nullable;
+import java.util.*;
 
-import accord.api.ProgressLog.ProgressShard;
-import accord.primitives.Ranges;
-import accord.primitives.Ballot;
-import accord.primitives.PartialDeps;
-import accord.primitives.PartialTxn;
-import accord.primitives.Route;
-import accord.primitives.Timestamp;
-import accord.primitives.TxnId;
-import accord.api.Result;
-import accord.api.RoutingKey;
+import static accord.local.Status.Durability.Local;
+import static accord.local.Status.Durability.NotDurable;
+import static accord.local.Status.Known.DefinitionOnly;
+import static accord.utils.Utils.*;
+import static java.lang.String.format;
 
-import static accord.api.ProgressLog.ProgressShard.Home;
-import static accord.api.ProgressLog.ProgressShard.Local;
-import static accord.api.ProgressLog.ProgressShard.No;
-import static accord.api.ProgressLog.ProgressShard.Unsure;
-import static accord.local.Command.EnsureAction.Add;
-import static accord.local.Command.EnsureAction.Check;
-import static accord.local.Command.EnsureAction.Ignore;
-import static accord.local.Command.EnsureAction.Set;
-import static accord.local.Command.EnsureAction.TrySet;
-
-public abstract class Command implements CommandListener, BiConsumer<SafeCommandStore, CommandListener>, PreLoadContext
+public abstract class Command extends ImmutableState
 {
-    private static final Logger logger = LoggerFactory.getLogger(Command.class);
+    // sentinel value to indicate a command requested in a preexecute context was not found
+    // should not escape the safe command store
+    public static final Command EMPTY = new Command()
+    {
+        @Override public Route<?> route() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public RoutingKey progressKey() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public RoutingKey homeKey() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public TxnId txnId() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Ballot promised() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Status.Durability durability() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public ImmutableSet<CommandListener> listeners() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public SaveStatus saveStatus() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Timestamp executeAt() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Ballot accepted() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public PartialTxn partialTxn() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Nullable
+        @Override public PartialDeps partialDeps() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
 
-    public abstract TxnId txnId();
+        @Override
+        public String toString()
+        {
+            return "Command(EMPTY)";
+        }
+    };
 
-    // TODO (desirable, API consistency): should any of these calls be replaced by corresponding known() registers?
-    public boolean hasBeen(Status status)
+    static
     {
-        return status().hasBeen(status);
+        EMPTY.markInvalidated();
     }
 
-    public boolean has(Known known)
+    static PreLoadContext contextForCommand(Command command)
     {
-        return known.isSatisfiedBy(saveStatus().known);
+        Invariants.checkState(command.hasBeen(Status.PreAccepted) && command.partialTxn() != null);
+        return command instanceof PreLoadContext ? (PreLoadContext) command : PreLoadContext.contextFor(command.txnId(), command.partialTxn().keys());
     }
 
-    public boolean has(Definition definition)
+    private static Status.Durability durability(Status.Durability durability, SaveStatus status)
     {
-        return known().definition.compareTo(definition) >= 0;
+        if (status.compareTo(SaveStatus.PreApplied) >= 0 && durability == NotDurable)
+            return Local; // not necessary anywhere, but helps for logical consistency
+        return durability;
     }
 
-    public boolean has(Outcome outcome)
+    public interface CommonAttributes
     {
-        return known().outcome.compareTo(outcome) >= 0;
+        TxnId txnId();
+        Status.Durability durability();
+        RoutingKey homeKey();
+        RoutingKey progressKey();
+        Route<?> route();
+        PartialTxn partialTxn();
+        PartialDeps partialDeps();
+        ImmutableSet<CommandListener> listeners();
     }
 
-    public boolean is(Status status)
+    public static class SerializerSupport
     {
-        return status() == status;
-    }
-
-    /**
-     * homeKey is a global value that defines the home shard - the one tasked with ensuring the transaction is finished.
-     * progressKey is a local value that defines the local shard responsible for ensuring progress on the transaction.
-     * This will be homeKey if it is owned by the node, and some other key otherwise. If not the home shard, the progress
-     * shard has much weaker responsibilities, only ensuring that the home shard has durably witnessed the txnId.
-     *
-     * TODO (expected, efficiency): we probably do not want to save this on its own, as we probably want to
-     *  minimize IO interactions and discrete registers, so will likely reference commit log entries directly
-     *  At which point we may impose a requirement that only a Route can be saved, not a homeKey on its own.
-     *  Once this restriction is imposed, we no longer need to pass around Routable.Domain with TxnId.
-     */
-    public abstract RoutingKey homeKey();
-    protected abstract void setHomeKey(RoutingKey key);
-
-    public abstract RoutingKey progressKey();
-    protected abstract void setProgressKey(RoutingKey key);
-
-    /**
-     * If this is the home shard, we require that this is a Route for all states &gt; NotWitnessed;
-     * otherwise for the local progress shard this is ordinarily a PartialRoute, and for other shards this is not set,
-     * so that there is only one copy per node that can be consulted to construct the full set of involved keys.
-     *
-     * If hasBeen(Committed) this must contain the keys for both txnId.epoch and executeAt.epoch
-     */
-    public abstract @Nullable Route<?> route();
-    protected abstract void setRoute(Route<?> route);
-
-    public abstract PartialTxn partialTxn();
-    protected abstract void setPartialTxn(PartialTxn txn);
-
-    public abstract Ballot promised();
-    protected abstract void setPromised(Ballot ballot);
-
-    public abstract Ballot accepted();
-    protected abstract void setAccepted(Ballot ballot);
-
-    public abstract Timestamp executeAt();
-    protected abstract void setExecuteAt(Timestamp timestamp);
-
-    /**
-     * While !hasBeen(Committed), used only as a register for Accept state, used by Recovery
-     * If hasBeen(Committed), represents the full deps owned by this range for execution at both txnId.epoch
-     * AND executeAt.epoch so that it may be used for Recovery (which contacts only txnId.epoch topology),
-     * but also for execution.
-     */
-    public abstract PartialDeps partialDeps();
-    protected abstract void setPartialDeps(PartialDeps deps);
-
-    public abstract Writes writes();
-    protected abstract void setWrites(Writes writes);
-
-    public abstract Result result();
-    protected abstract void setResult(Result result);
-
-    public abstract SaveStatus saveStatus();
-    protected abstract void setSaveStatus(SaveStatus status);
-
-    public Status status() { return saveStatus().status; }
-    protected void setStatus(Status status) { setSaveStatus(SaveStatus.get(status, known())); }
-
-    public Known known() { return saveStatus().known; }
-
-    public abstract Durability durability();
-    public abstract void setDurability(Durability v);
+        public static Command.Listener listener(TxnId txnId)
+        {
+            return new Command.Listener(txnId);
+        }
 
-    public abstract Command addListener(CommandListener listener);
-    public abstract void removeListener(CommandListener listener);
-    protected abstract void notifyListeners(SafeCommandStore safeStore);
+        public static NotWitnessed notWitnessed(CommonAttributes attributes, Ballot promised)
+        {
+            return NotWitnessed.Factory.create(attributes, promised);
+        }
 
-    protected abstract void addWaitingOnCommit(TxnId txnId);
-    protected abstract void removeWaitingOnCommit(TxnId txnId);
-    protected abstract TxnId firstWaitingOnCommit();
+        public static Preaccepted preaccepted(CommonAttributes common, Timestamp executeAt, Ballot promised)
+        {
+            return Preaccepted.Factory.create(common, executeAt, promised);
+        }
 
-    protected abstract void addWaitingOnApplyIfAbsent(TxnId txnId, Timestamp executeAt);
-    protected abstract TxnId firstWaitingOnApply(@Nullable TxnId ifExecutesBefore);
+        public static Accepted accepted(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted)
+        {
+            return Accepted.Factory.create(common, status, executeAt, promised, accepted);
+        }
 
-    protected abstract void removeWaitingOn(TxnId txnId, Timestamp executeAt);
-    protected abstract boolean isWaitingOnDependency();
+        public static Committed committed(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply)
+        {
+            return Committed.Factory.create(common, status, executeAt, promised, accepted, waitingOnCommit, waitingOnApply);
+        }
 
-    public boolean hasBeenWitnessed()
-    {
-        return partialTxn() != null;
+        public static Executed executed(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply, Writes writes, Result result)
+        {
+            return Executed.Factory.create(common, status, executeAt, promised, accepted, waitingOnCommit, waitingOnApply, writes, result);
+        }
     }
 
-    @Override
-    public Iterable<TxnId> txnIds()
+    private static SaveStatus validateCommandClass(SaveStatus status, Class<?> expected, Class<?> actual)
     {
-        return Collections.singleton(txnId());
+        if (actual != expected)
+        {
+            throw new IllegalStateException(format("Cannot instantiate %s for status %s. %s expected",
+                                                   actual.getSimpleName(), status, expected.getSimpleName()));
+        }
+        return status;
     }
 
-    @Override
-    public Seekables<?, ?> keys()
+    private static SaveStatus validateCommandClass(SaveStatus status, Class<?> klass)
     {
-        // TODO (expected, consider): when do we need this, and will it always be sufficient?
-        return partialTxn().keys();
+        switch (status)
+        {
+            case NotWitnessed:
+                return validateCommandClass(status, NotWitnessed.class, klass);
+            case PreAccepted:
+                return validateCommandClass(status, Preaccepted.class, klass);
+            case AcceptedInvalidate:
+            case AcceptedInvalidateWithDefinition:
+            case Accepted:
+            case AcceptedWithDefinition:
+                return validateCommandClass(status, Accepted.class, klass);
+            case Committed:
+            case ReadyToExecute:
+                return validateCommandClass(status, Committed.class, klass);
+            case PreApplied:
+            case Applied:
+            case Invalidated:
+                return validateCommandClass(status, Executed.class, klass);
+            default:
+                throw new IllegalStateException("Unhandled status " + status);
+        }
     }
 
-    public void setDurability(SafeCommandStore safeStore, Durability durability, RoutingKey homeKey, @Nullable Timestamp executeAt)
+    public static Command addListener(SafeCommandStore safeStore, Command command, CommandListener listener)
     {
-        updateHomeKey(safeStore, homeKey);
-        if (executeAt != null && hasBeen(PreCommitted) && !this.executeAt().equals(executeAt))
-            safeStore.agent().onInconsistentTimestamp(this, this.executeAt(), executeAt);
-        setDurability(durability);
+        return safeStore.beginUpdate(command).addListener(listener).updateAttributes();
     }
 
-    public enum AcceptOutcome
+    public static Command removeListener(SafeCommandStore safeStore, Command command, CommandListener listener)
     {
-        Success, Redundant, RejectedBallot
+        return safeStore.beginUpdate(command).removeListener(listener).updateAttributes();
     }
 
-    public AcceptOutcome preaccept(SafeCommandStore safeStore, PartialTxn partialTxn, Route<?> route, @Nullable RoutingKey progressKey)
+    public static Committed updateWaitingOn(SafeCommandStore safeStore, Committed command, WaitingOn.Update waitingOn)
     {
-        return preacceptOrRecover(safeStore, partialTxn, route, progressKey, Ballot.ZERO);
+        if (!waitingOn.hasChanges())
+            return command;
+
+        Update update = safeStore.beginUpdate(command);
+        Committed updated =  command instanceof Executed ?
+                Executed.Factory.update(command.asExecuted(), update, waitingOn.build()) :
+                Committed.Factory.update(command, update, waitingOn.build());
+        return update.complete(updated);
     }
 
-    public AcceptOutcome recover(SafeCommandStore safeStore, PartialTxn partialTxn, Route<?> route, @Nullable RoutingKey progressKey, Ballot ballot)
+    public static class Listener implements CommandListener
     {
-        return preacceptOrRecover(safeStore, partialTxn, route, progressKey, ballot);
-    }
+        protected final TxnId listenerId;
 
-    private AcceptOutcome preacceptOrRecover(SafeCommandStore safeStore, PartialTxn partialTxn, Route<?> route, @Nullable RoutingKey progressKey, Ballot ballot)
-    {
-        int compareBallots = promised().compareTo(ballot);
-        if (compareBallots > 0)
+        private Listener(TxnId listenerId)
         {
-            logger.trace("{}: skipping preaccept - higher ballot witnessed ({})", txnId(), promised());
-            return AcceptOutcome.RejectedBallot;
+            this.listenerId = listenerId;
         }
-        else if (compareBallots < 0)
+
+        @Override
+        public boolean equals(Object o)
         {
-            // save the new ballot as a promise
-            setPromised(ballot);
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+            Listener that = (Listener) o;
+            return listenerId.equals(that.listenerId);
         }
 
-        if (known().definition.isKnown())
+        @Override
+        public int hashCode()
         {
-            Invariants.checkState(status() == Invalidated || executeAt() != null);
-            logger.trace("{}: skipping preaccept - already known ({})", txnId(), status());
-            // in case of Ballot.ZERO, we must either have a competing recovery coordinator or have late delivery of the
-            // preaccept; in the former case we should abandon coordination, and in the latter we have already completed
-            return ballot.equals(Ballot.ZERO) ? AcceptOutcome.Redundant : AcceptOutcome.Success;
+            return Objects.hash(listenerId);
         }
 
-        Ranges coordinateRanges = coordinateRanges(safeStore);
-        Invariants.checkState(!coordinateRanges.isEmpty());
-        ProgressShard shard = progressShard(safeStore, route, progressKey, coordinateRanges);
-        if (!validate(Ranges.EMPTY, coordinateRanges, shard, route, Set, partialTxn, Set, null, Ignore))
-            throw new IllegalStateException();
-
-        if (executeAt() == null)
+        @Override
+        public String toString()
         {
-            TxnId txnId = txnId();
-            // unlike in the Accord paper, we partition shards within a node, so that to ensure a total order we must either:
-            //  - use a global logical clock to issue new timestamps; or
-            //  - assign each shard _and_ process a unique id, and use both as components of the timestamp
-            // if we are performing recovery (i.e. non-zero ballot), do not permit a fast path decision as we want to
-            // invalidate any transactions that were not completed by their initial coordinator
-            if (ballot.equals(Ballot.ZERO)) setExecuteAt(safeStore.preaccept(txnId, partialTxn.keys()));
-            else setExecuteAt(safeStore.time().uniqueNow(txnId));
+            return "ListenerProxy{" + listenerId + '}';
+        }
 
-            if (status() == NotWitnessed)
-                setStatus(PreAccepted);
-            safeStore.progressLog().preaccepted(this, shard);
+        public TxnId txnId()
+        {
+            return listenerId;
         }
-        else
+
+        @Override
+        public void onChange(SafeCommandStore safeStore, TxnId txnId)
         {
-            // TODO (expected, ?): in the case that we are pre-committed but had not been preaccepted/accepted, should we inform progressLog?
-            setSaveStatus(SaveStatus.enrich(saveStatus(), DefinitionOnly));
+            Commands.listenerUpdate(safeStore, safeStore.command(listenerId), safeStore.command(txnId));
         }
-        set(safeStore, Ranges.EMPTY, coordinateRanges, shard, route, partialTxn, Set, null, Ignore);
 
-        notifyListeners(safeStore);
-        return AcceptOutcome.Success;
+        @Override
+        public PreLoadContext listenerPreLoadContext(TxnId caller)
+        {
+            return PreLoadContext.contextFor(Utils.listOf(listenerId, caller), Keys.EMPTY);
+        }
     }
 
-    public boolean preacceptInvalidate(Ballot ballot)
+    public static CommandListener listener(TxnId txnId)
     {
-        if (promised().compareTo(ballot) > 0)
-        {
-            logger.trace("{}: skipping preacceptInvalidate - witnessed higher ballot ({})", txnId(), promised());
-            return false;
-        }
-        setPromised(ballot);
-        return true;
+        return new Listener(txnId);
     }
 
-    public AcceptOutcome accept(SafeCommandStore safeStore, Ballot ballot, PartialRoute<?> route, Seekables<?, ?> keys, @Nullable RoutingKey progressKey, Timestamp executeAt, PartialDeps partialDeps)
+    private abstract static class AbstractCommand extends Command
     {
-        if (this.promised().compareTo(ballot) > 0)
+        private final TxnId txnId;
+        private final SaveStatus status;
+        private final Status.Durability durability;
+        private final RoutingKey homeKey;
+        private final RoutingKey progressKey;
+        private final Route<?> route;
+        private final Ballot promised;
+        private final ImmutableSet<CommandListener> listeners;
+
+        private AbstractCommand(TxnId txnId, SaveStatus status, Status.Durability durability, RoutingKey homeKey, RoutingKey progressKey, Route<?> route, Ballot promised, ImmutableSet<CommandListener> listeners)
         {
-            logger.trace("{}: skipping accept - witnessed higher ballot ({} > {})", txnId(), promised(), ballot);
-            return AcceptOutcome.RejectedBallot;
+            this.txnId = txnId;
+            this.status = validateCommandClass(status, getClass());
+            this.durability = durability;
+            this.homeKey = homeKey;
+            this.progressKey = progressKey;
+            this.route = route;
+            this.promised = promised;
+            this.listeners = listeners;
         }
 
-        if (hasBeen(PreCommitted))
+        private AbstractCommand(CommonAttributes common, SaveStatus status, Ballot promised)
         {
-            logger.trace("{}: skipping accept - already committed ({})", txnId(), status());
-            return AcceptOutcome.Redundant;
+            this.txnId = common.txnId();
+            this.status = validateCommandClass(status, getClass());
+            this.durability = common.durability();
+            this.homeKey = common.homeKey();
+            this.progressKey = common.progressKey();
+            this.route = common.route();
+            this.promised = promised;
+            this.listeners = common.listeners();
         }
 
-        TxnId txnId = txnId();
-        Ranges coordinateRanges = coordinateRanges(safeStore);
-        Ranges acceptRanges = txnId.epoch() == executeAt.epoch() ? coordinateRanges : safeStore.ranges().between(txnId.epoch(), executeAt.epoch());
-        Invariants.checkState(!acceptRanges.isEmpty());
-        ProgressShard shard = progressShard(safeStore, route, progressKey, coordinateRanges);
-
-        if (!validate(coordinateRanges, Ranges.EMPTY, shard, route, Ignore, null, Ignore, partialDeps, Set))
-            throw new AssertionError("Invalid response from validate function");
-
-        setExecuteAt(executeAt);
-        setPromised(ballot);
-        setAccepted(ballot);
-
-        // TODO (desired, clarity/efficiency): we don't need to set the route here, and perhaps we don't even need to
-        //  distributed partialDeps at all, since all we gain is not waiting for these transactions to commit during
-        //  recovery. We probably don't want to directly persist a Route in any other circumstances, either, to ease persistence.
-        set(safeStore, coordinateRanges, acceptRanges, shard, route, null, Ignore, partialDeps, Set);
+        @Override
+        public boolean equals(Object o)
+        {
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+            Command command = (Command) o;
+            return txnId.equals(command.txnId())
+                    && status == command.saveStatus()
+                    && durability == command.durability()
+                    && Objects.equals(homeKey, command.homeKey())
+                    && Objects.equals(progressKey, command.progressKey())
+                    && Objects.equals(route, command.route())
+                    && Objects.equals(promised, command.promised())
+                    && listeners.equals(command.listeners());
+        }
 
-        // set only registers by transaction keys, which we mightn't already have received
-        if (!known().isDefinitionKnown())
-            safeStore.register(keys, acceptRanges, this);
+        @Override
+        public String toString()
+        {
+            return "Command@" + System.identityHashCode(this) + '{' + txnId + ':' + status + '}';
+        }
 
-        setStatus(Accepted);
-        safeStore.progressLog().accepted(this, shard);
-        notifyListeners(safeStore);
+        @Override
+        public int hashCode()
+        {
+            int hash = 1;
+            hash = 31 * hash + txnId.hashCode();
+            hash = 31 * hash + status.hashCode();
+            hash = 31 * hash + Objects.hashCode(durability);
+            hash = 31 * hash + Objects.hashCode(homeKey);
+            hash = 31 * hash + Objects.hashCode(progressKey);
+            hash = 31 * hash + Objects.hashCode(route);
+            hash = 31 * hash + Objects.hashCode(promised);
+            hash = 31 * hash + Objects.hashCode(listeners);
+            return hash;
+        }
 
-        return AcceptOutcome.Success;
-    }
+        @Override
+        public TxnId txnId()
+        {
+            return txnId;
+        }
 
-    public AcceptOutcome acceptInvalidate(SafeCommandStore safeStore, Ballot ballot)
-    {
-        if (this.promised().compareTo(ballot) > 0)
+        @Override
+        public final RoutingKey homeKey()
         {
-            logger.trace("{}: skipping accept invalidated - witnessed higher ballot ({} > {})", txnId(), promised(), ballot);
-            return AcceptOutcome.RejectedBallot;
+            checkCanReadFrom();
+            return homeKey;
         }
 
-        if (hasBeen(PreCommitted))
+        @Override
+        public final RoutingKey progressKey()
         {
-            logger.trace("{}: skipping accept invalidated - already committed ({})", txnId(), status());
-            return AcceptOutcome.Redundant;
+            checkCanReadFrom();
+            return progressKey;
         }
 
-        setPromised(ballot);
-        setAccepted(ballot);
-        setStatus(AcceptedInvalidate);
-        setPartialDeps(null);
-        logger.trace("{}: accepted invalidated", txnId());
+        @Override
+        public final Route<?> route()
+        {
+            checkCanReadFrom();
+            return route;
+        }
 
-        notifyListeners(safeStore);
-        return AcceptOutcome.Success;
-    }
+        @Override
+        public Ballot promised()
+        {
+            checkCanReadFrom();
+            return promised;
+        }
 
-    public enum CommitOutcome { Success, Redundant, Insufficient }
+        @Override
+        public Status.Durability durability()
+        {
+            checkCanReadFrom();
+            return Command.durability(durability, saveStatus());
+        }
 
-    // relies on mutual exclusion for each key
-    public CommitOutcome commit(SafeCommandStore safeStore, Route<?> route, @Nullable RoutingKey progressKey, @Nullable PartialTxn partialTxn, Timestamp executeAt, PartialDeps partialDeps)
-    {
-        if (hasBeen(PreCommitted))
+        @Override
+        public ImmutableSet<CommandListener> listeners()
         {
-            logger.trace("{}: skipping commit - already committed ({})", txnId(), status());
-            if (!executeAt.equals(executeAt()) || status() == Invalidated)
-                safeStore.agent().onInconsistentTimestamp(this, (status() == Invalidated ? Timestamp.NONE : this.executeAt()), executeAt);
+            checkCanReadFrom();
+            if (listeners == null)
+                return ImmutableSet.of();
+            return listeners;
+        }
 
-            if (hasBeen(Committed))
-                return CommitOutcome.Redundant;
+        @Override
+        public final SaveStatus saveStatus()
+        {
+            checkCanReadFrom();
+            return status;
         }
+    }
+
+    /**
+     * If this is the home shard, we require that this is a Route for all states &gt; NotWitnessed;
+     * otherwise for the local progress shard this is ordinarily a PartialRoute, and for other shards this is not set,
+     * so that there is only one copy per node that can be consulted to construct the full set of involved keys.
+     *
+     * If hasBeen(Committed) this must contain the keys for both txnId.epoch and executeAt.epoch
+     */
+    public abstract Route<?> route();
+    public abstract RoutingKey progressKey();
 
-        Ranges coordinateRanges = coordinateRanges(safeStore);
-        // TODO (expected, consider): consider ranges between coordinateRanges and executeRanges? Perhaps don't need them
-        Ranges executeRanges = executeRanges(safeStore, executeAt);
-        ProgressShard shard = progressShard(safeStore, route, progressKey, coordinateRanges);
+    /**
+     * homeKey is a global value that defines the home shard - the one tasked with ensuring the transaction is finished.
+     * progressKey is a local value that defines the local shard responsible for ensuring progress on the transaction.
+     * This will be homeKey if it is owned by the node, and some other key otherwise. If not the home shard, the progress
+     * shard has much weaker responsibilities, only ensuring that the home shard has durably witnessed the txnId.
+     *
+     * TODO (expected, efficiency): we probably do not want to save this on its own, as we probably want to
+     *  minimize IO interactions and discrete registers, so will likely reference commit log entries directly
+     *  At which point we may impose a requirement that only a Route can be saved, not a homeKey on its own.
+     *  Once this restriction is imposed, we no longer need to pass around Routable.Domain with TxnId.
+     */
+    public abstract RoutingKey homeKey();
+    public abstract TxnId txnId();
+    public abstract Ballot promised();
+    public abstract Status.Durability durability();
+    public abstract ImmutableSet<CommandListener> listeners();
+    public abstract SaveStatus saveStatus();
 
-        if (!validate(coordinateRanges, executeRanges, shard, route, Check, partialTxn, Add, partialDeps, Set))
-            return CommitOutcome.Insufficient;
+    private static boolean isSameClass(Command command, Class<? extends Command> klass)
+    {
+        return command.getClass() == klass;
+    }
 
-        setExecuteAt(executeAt);
-        set(safeStore, coordinateRanges, executeRanges, shard, route, partialTxn, Add, partialDeps, Set);
+    private static void checkNewBallot(Ballot current, Ballot next, String name)
+    {
+        if (next.compareTo(current) < 0)
+            throw new IllegalArgumentException(String.format("Cannot update %s ballot from %s to %s. New ballot is less than current", name, current, next));
+    }
 
-        setStatus(Committed);
-        logger.trace("{}: committed with executeAt: {}, deps: {}", txnId(), executeAt, partialDeps);
-        populateWaitingOn(safeStore);
+    private static void checkPromised(Command command, Ballot ballot)
+    {
+        checkNewBallot(command.promised(), ballot, "promised");
+    }
 
-        safeStore.progressLog().committed(this, shard);
+    private static void checkAccepted(Command command, Ballot ballot)
+    {
+        checkNewBallot(command.accepted(), ballot, "accepted");
+    }
 
-        // TODO (expected, safety): introduce intermediate status to avoid reentry when notifying listeners (which might notify us)
-        maybeExecute(safeStore, shard, true, true);
-        return CommitOutcome.Success;
+    private static void checkSameClass(Command command, Class<? extends Command> klass, String errorMsg)
+    {
+        if (!isSameClass(command, klass))
+            throw new IllegalArgumentException(errorMsg + format(" expected %s got %s", klass.getSimpleName(), command.getClass().getSimpleName()));
     }
 
-    // relies on mutual exclusion for each key
-    public void precommit(SafeCommandStore safeStore, Timestamp executeAt)
+    // TODO (low priority, progress): callers should try to consult the local progress shard (if any) to obtain the full set of keys owned locally
+    public final Route<?> someRoute()
     {
-        if (hasBeen(PreCommitted))
-        {
-            logger.trace("{}: skipping precommit - already committed ({})", txnId(), status());
-            if (executeAt.equals(executeAt()) && status() != Invalidated)
-                return;
+        checkCanReadFrom();
+        if (route() != null)
+            return route();
 
-            safeStore.agent().onInconsistentTimestamp(this, (status() == Invalidated ? Timestamp.NONE : this.executeAt()), executeAt);
-        }
+        if (homeKey() != null)
+            return PartialRoute.empty(txnId().domain(), homeKey());
 
-        setExecuteAt(executeAt);
-        setStatus(PreCommitted);
-        notifyListeners(safeStore);
-        logger.trace("{}: precommitted with executeAt: {}", txnId(), executeAt);
+        return null;
     }
 
-    protected void populateWaitingOn(SafeCommandStore safeStore)
+    public Unseekables<?, ?> maxUnseekables()
     {
-        Ranges ranges = safeStore.ranges().since(executeAt().epoch());
-        if (ranges != null)
-        {
-            partialDeps().forEach(ranges, txnId -> {
-                Command command = safeStore.ifLoaded(txnId);
-                if (command == null)
-                {
-                    addWaitingOnCommit(txnId);
-                    safeStore.addAndInvokeListener(txnId, this);
-                }
-                else
-                {
-                    switch (command.status())
-                    {
-                        default:
-                            throw new IllegalStateException();
-                        case NotWitnessed:
-                        case PreAccepted:
-                        case Accepted:
-                        case AcceptedInvalidate:
-                            // we don't know when these dependencies will execute, and cannot execute until we do
-                            command.addListener(this);
-                            addWaitingOnCommit(command.txnId());
-                            break;
-                        case PreCommitted:
-                        case Committed:
-                            // TODO (desired, efficiency): split into ReadyToRead and ReadyToWrite;
-                            //                             the distributed read can be performed as soon as those keys are ready,
-                            //                             and in parallel with any other reads. the client can even ACK immediately after;
-                            //                             only the write needs to be postponed until other in-progress reads complete
-                        case ReadyToExecute:
-                        case PreApplied:
-                        case Applied:
-                            command.addListener(this);
-                            insertPredecessor(command);
-                        case Invalidated:
-                            break;
-                    }
-                }
-            });
-        }
+        Route<?> route = someRoute();
+        if (route == null)
+            return null;
+
+        return route.toMaximalUnseekables();
     }
 
-    // TODO (expected, ?): commitInvalidate may need to update cfks _if_ possible
-    public void commitInvalidate(SafeCommandStore safeStore)
+    public PreLoadContext contextForSelf()
     {
-        if (hasBeen(PreCommitted))
-        {
-            logger.trace("{}: skipping commit invalidated - already committed ({})", txnId(), status());
-            if (!hasBeen(Invalidated))
-                safeStore.agent().onInconsistentTimestamp(this, Timestamp.NONE, executeAt());
-
-            return;
-        }
+        checkCanReadFrom();
+        return contextForCommand(this);
+    }
 
-        ProgressShard shard = progressShard(safeStore);
-        safeStore.progressLog().invalidated(this, shard);
-        setExecuteAt(txnId());
-        if (partialDeps() == null)
-            setPartialDeps(PartialDeps.NONE);
-        setStatus(Invalidated);
-        logger.trace("{}: committed invalidated", txnId());
+    public abstract Timestamp executeAt();
+    public abstract Ballot accepted();
+    public abstract PartialTxn partialTxn();
+    public abstract @Nullable PartialDeps partialDeps();
 
-        notifyListeners(safeStore);
+    public final Status status()
+    {
+        checkCanReadFrom();
+        return saveStatus().status;
     }
 
-    public enum ApplyOutcome { Success, Redundant, Insufficient }
+    public final Status.Known known()
+    {
+        checkCanReadFrom();
+        return saveStatus().known;
+    }
 
-    public ApplyOutcome apply(SafeCommandStore safeStore, long untilEpoch, Route<?> route, Timestamp executeAt, @Nullable PartialDeps partialDeps, Writes writes, Result result)
+    public boolean hasBeenWitnessed()
     {
-        if (hasBeen(PreApplied) && executeAt.equals(this.executeAt()))
-        {
-            logger.trace("{}: skipping apply - already executed ({})", txnId(), status());
-            return ApplyOutcome.Redundant;
-        }
-        else if (hasBeen(PreCommitted) && !executeAt.equals(this.executeAt()))
-        {
-            safeStore.agent().onInconsistentTimestamp(this, this.executeAt(), executeAt);
-        }
+        checkCanReadFrom();
+        return partialTxn() != null;
+    }
 
-        Ranges coordinateRanges = coordinateRanges(safeStore);
-        Ranges executeRanges = executeRanges(safeStore, executeAt);
-        if (untilEpoch < safeStore.latestEpoch())
-        {
-            Ranges expectedRanges = safeStore.ranges().between(executeAt.epoch(), untilEpoch);
-            Invariants.checkState(expectedRanges.containsAll(executeRanges));
-        }
-        ProgressShard shard = progressShard(safeStore, route, coordinateRanges);
+    public final boolean hasBeen(Status status)
+    {
+        return status().compareTo(status) >= 0;
+    }
 
-        if (!validate(coordinateRanges, executeRanges, shard, route, Check, null, Check, partialDeps, hasBeen(Committed) ? Add : TrySet))
-            return ApplyOutcome.Insufficient; // TODO (expected, consider): this should probably be an assertion failure if !TrySet
+    public boolean has(Status.Known known)
+    {
+        return known.isSatisfiedBy(saveStatus().known);
+    }
 
-        setWrites(writes);
-        setResult(result);
-        setExecuteAt(executeAt);
-        set(safeStore, coordinateRanges, executeRanges, shard, route, null, Check, partialDeps, hasBeen(Committed) ? Add : TrySet);
+    public boolean has(Status.Definition definition)
+    {
+        return known().definition.compareTo(definition) >= 0;
+    }
 
-        if (!hasBeen(Committed))
-            populateWaitingOn(safeStore);
-        setStatus(PreApplied);
-        logger.trace("{}: apply, status set to Executed with executeAt: {}, deps: {}", txnId(), executeAt, partialDeps);
+    public boolean has(Status.Outcome outcome)
+    {
+        return known().outcome.compareTo(outcome) >= 0;
+    }
 
-        safeStore.progressLog().executed(this, shard);
+    public boolean is(Status status)
+    {
+        return status() == status;
+    }
 
-        maybeExecute(safeStore, shard, true, true);
-        return ApplyOutcome.Success;
+    public final CommandListener asListener()
+    {
+        return listener(txnId());
     }
 
-    @Override
-    public PreLoadContext listenerPreLoadContext(TxnId caller)
+    public final boolean isWitnessed()
     {
-        return PreLoadContext.contextFor(listOf(txnId(), caller));
+        checkCanReadFrom();
+        boolean result = status().hasBeen(Status.PreAccepted);
+        Invariants.checkState(result == (this instanceof Preaccepted));
+        return result;
     }
 
-    @Override
-    public void onChange(SafeCommandStore safeStore, Command command)
+    public final Preaccepted asWitnessed()
     {
-        logger.trace("{}: updating as listener in response to change on {} with status {} ({})",
-                     txnId(), command.txnId(), command.status(), command);
-        switch (command.status())
-        {
-            default:
-                throw new IllegalStateException();
-            case NotWitnessed:
-            case PreAccepted:
-            case Accepted:
-            case AcceptedInvalidate:
-                break;
+        checkCanReadFrom();
+        return (Preaccepted) this;
+    }
 
-            case PreCommitted:
-            case Committed:
-            case ReadyToExecute:
-            case PreApplied:
-            case Applied:
-            case Invalidated:
-                updatePredecessor(command);
-                maybeExecute(safeStore, progressShard(safeStore), false, true);
-                break;
-        }
+    public final boolean isAccepted()
+    {
+        checkCanReadFrom();
+        boolean result = status().hasBeen(Status.AcceptedInvalidate);
+        Invariants.checkState(result == (this instanceof Accepted));
+        return result;
     }
 
-    protected void postApply(SafeCommandStore safeStore)
+    public final Accepted asAccepted()
     {
-        logger.trace("{} applied, setting status to Applied and notifying listeners", txnId());
-        setStatus(Applied);
-        notifyListeners(safeStore);
+        checkCanReadFrom();
+        return (Accepted) this;
     }
 
-    private static Function<SafeCommandStore, Void> callPostApply(TxnId txnId)
+    public final boolean isCommitted()
     {
-        return safeStore -> {
-            safeStore.command(txnId).postApply(safeStore);
-            return null;
-        };
+        checkCanReadFrom();
+        boolean result = status().hasBeen(Status.Committed);
+        Invariants.checkState(result == (this instanceof Committed));
+        return result;
     }
 
-    protected Future<Void> apply(SafeCommandStore safeStore)
+    public final Committed asCommitted()
     {
-        // important: we can't include a reference to *this* in the lambda, since the C* implementation may evict
-        // the command instance from memory between now and the write completing (and post apply being called)
-        CommandStore unsafeStore = safeStore.commandStore();
-        return writes().apply(safeStore).flatMap(unused ->
-            unsafeStore.submit(this, callPostApply(txnId()))
-        );
+        checkCanReadFrom();
+        return (Committed) this;
     }
 
-    public Future<Data> read(SafeCommandStore safeStore)
+    public final boolean isExecuted()
     {
-        return partialTxn().read(safeStore, this);
+        checkCanReadFrom();
+        boolean result = status().hasBeen(Status.PreApplied);
+        Invariants.checkState(result == (this instanceof Executed));
+        return result;
     }
 
-    // TODO (expected, API consistency): maybe split into maybeExecute and maybeApply?
-    private boolean maybeExecute(SafeCommandStore safeStore, ProgressShard shard, boolean alwaysNotifyListeners, boolean notifyWaitingOn)
+    public final Executed asExecuted()
     {
-        if (logger.isTraceEnabled())
-            logger.trace("{}: Maybe executing with status {}. Will notify listeners on noop: {}", txnId(), status(), alwaysNotifyListeners);
+        checkCanReadFrom();
+        return (Executed) this;
+    }
 
-        if (status() != Committed && status() != PreApplied)
+    public static final class NotWitnessed extends AbstractCommand
+    {
+        NotWitnessed(TxnId txnId, SaveStatus status, Status.Durability durability, RoutingKey homeKey, RoutingKey progressKey, Route<?> route, Ballot promised, ImmutableSet<CommandListener> listeners)
         {
-            if (alwaysNotifyListeners)
-                notifyListeners(safeStore);
-            return false;
+            super(txnId, status, durability, homeKey, progressKey, route, promised, listeners);
         }
 
-        if (isWaitingOnDependency())
+        NotWitnessed(CommonAttributes common, SaveStatus status, Ballot promised)
         {
-            if (alwaysNotifyListeners)
-                notifyListeners(safeStore);
-
-            if (notifyWaitingOn)
-                new NotifyWaitingOn(this).accept(safeStore);
-            return false;
+            super(common, status, promised);
         }
 
-        switch (status())
+        public static NotWitnessed create(TxnId txnId)
         {
-            case Committed:
-                // TODO (desirable, efficiency): maintain distinct ReadyToRead and ReadyToWrite states
-                setStatus(ReadyToExecute);
-                logger.trace("{}: set to ReadyToExecute", txnId());
-                safeStore.progressLog().readyToExecute(this, shard);
-                notifyListeners(safeStore);
-                break;
+            return new NotWitnessed(txnId, SaveStatus.NotWitnessed, NotDurable, null, null, null, Ballot.ZERO, null);
+        }
 
-            case PreApplied:
-                Ranges executeRanges = executeRanges(safeStore, executeAt());
-                boolean intersects = writes().keys.intersects(executeRanges);
+        private static class Factory
+        {
+            public static NotWitnessed create(CommonAttributes common, Ballot promised)
+            {
+                return new NotWitnessed(common, SaveStatus.NotWitnessed, promised);
+            }
 
-                if (intersects)
-                {
-                    logger.trace("{}: applying", txnId());
-                    apply(safeStore);
-                }
-                else
-                {
-                    // TODO (desirable, performance): This could be performed immediately upon Committed
-                    //      but: if we later support transitive dependency elision this could be dangerous
-                    logger.trace("{}: applying no-op", txnId());
-                    setStatus(Applied);
-                    notifyListeners(safeStore);
-                }
+            public static NotWitnessed update(NotWitnessed command, CommonAttributes common, Ballot promised)
+            {
+                checkSameClass(command, NotWitnessed.class, "Cannot update");
+                command.checkCanReadFrom();
+                Invariants.checkArgument(command.txnId().equals(common.txnId()));
+                return new NotWitnessed(common, command.saveStatus(), promised);
+            }
         }
-        return true;
-    }
 
-    /**
-     * @param dependency is either committed or invalidated
-     * @return true iff {@code maybeExecute} might now have a different outcome
-     */
-    private boolean updatePredecessor(Command dependency)
-    {
-        Invariants.checkState(dependency.hasBeen(PreCommitted));
-        if (dependency.hasBeen(Invalidated))
+        @Override
+        public Timestamp executeAt()
         {
-            logger.trace("{}: {} is invalidated. Stop listening and removing from waiting on commit set.", txnId(), dependency.txnId());
-            dependency.removeListener(this);
-            removeWaitingOnCommit(dependency.txnId());
-            return true;
+            checkCanReadFrom();
+            return null;
         }
-        else if (dependency.executeAt().compareTo(executeAt()) > 0)
+
+        @Override
+        public Ballot promised()
         {
-            // dependency cannot be a predecessor if it executes later
-            logger.trace("{}: {} executes after us. Stop listening and removing from waiting on apply set.", txnId(), dependency.txnId());
-            removeWaitingOn(dependency.txnId(), dependency.executeAt());
-            dependency.removeListener(this);
-            return true;
+            checkCanReadFrom();
+            return Ballot.ZERO;
         }
-        else if (dependency.hasBeen(Applied))
+
+        @Override
+        public Ballot accepted()
         {
-            logger.trace("{}: {} has been applied. Stop listening and removing from waiting on apply set.", txnId(), dependency.txnId());
-            removeWaitingOn(dependency.txnId(), dependency.executeAt());
-            dependency.removeListener(this);
-            return true;
+            checkCanReadFrom();
+            return Ballot.ZERO;
         }
-        else if (isWaitingOnDependency())
+
+        @Override
+        public PartialTxn partialTxn()
         {
-            logger.trace("{}: adding {} to waiting on apply set.", txnId(), dependency.txnId());
-            addWaitingOnApplyIfAbsent(dependency.txnId(), dependency.executeAt());
-            removeWaitingOnCommit(dependency.txnId());
-            return false;
+            checkCanReadFrom();
+            return null;
         }
-        else
+
+        @Override
+        public @Nullable PartialDeps partialDeps()
         {
-            throw new IllegalStateException();
+            checkCanReadFrom();
+            return null;
         }
     }
 
-    private void insertPredecessor(Command dependency)
+    public static class Preaccepted extends AbstractCommand
     {
-        Invariants.checkState(dependency.hasBeen(PreCommitted));
-        if (dependency.hasBeen(Invalidated))
+        private final Timestamp executeAt;
+        private final PartialTxn partialTxn;
+        private final @Nullable PartialDeps partialDeps;
+
+        private Preaccepted(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised)
+        {
+            super(common, status, promised);
+            this.executeAt = executeAt;
+            this.partialTxn = common.partialTxn();
+            this.partialDeps = common.partialDeps();
+        }
+
+        @Override
+        public boolean equals(Object o)
+        {
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+            if (!super.equals(o)) return false;
+            Preaccepted that = (Preaccepted) o;
+            return executeAt.equals(that.executeAt)
+                    && Objects.equals(partialTxn, that.partialTxn)
+                    && Objects.equals(partialDeps, that.partialDeps);
+        }
+
+        @Override
+        public int hashCode()
         {
-            logger.trace("{}: {} is invalidated. Do not insert.", txnId(), dependency.txnId());
+            int hash = super.hashCode();
+            hash = 31 * hash + Objects.hashCode(executeAt);
+            hash = 31 * hash + Objects.hashCode(partialTxn);
+            hash = 31 * hash + Objects.hashCode(partialDeps);
+            return hash;
         }
-        else if (dependency.executeAt().compareTo(executeAt()) > 0)
+
+        private static class Factory
         {
-            // dependency cannot be a predecessor if it executes later
-            logger.trace("{}: {} executes after us. Do not insert.", txnId(), dependency.txnId());
+            public static Preaccepted create(CommonAttributes common, Timestamp executeAt, Ballot promised)
+            {
+                return new Preaccepted(common, SaveStatus.PreAccepted, executeAt, promised);
+            }
+
+            public static Preaccepted update(Preaccepted command, CommonAttributes common, Ballot promised)
+            {
+                checkPromised(command, promised);
+                checkSameClass(command, Preaccepted.class, "Cannot update");
+                Invariants.checkArgument(command.getClass() == Preaccepted.class);
+                command.checkCanReadFrom();
+                return create(common, command.executeAt(), promised);
+            }
         }
-        else if (dependency.hasBeen(Applied))
+
+        @Override
+        public Timestamp executeAt()
         {
-            logger.trace("{}: {} has been applied. Do not insert.", txnId(), dependency.txnId());
+            checkCanReadFrom();
+            return executeAt;
         }
-        else
+
+        @Override
+        public Ballot accepted()
         {
-            logger.trace("{}: adding {} to waiting on apply set.", txnId(), dependency.txnId());
-            addWaitingOnApplyIfAbsent(dependency.txnId(), dependency.executeAt());
+            checkCanReadFrom();
+            return Ballot.ZERO;
         }
-    }
 
-    void updatePredecessorAndMaybeExecute(SafeCommandStore safeStore, Command predecessor, boolean notifyWaitingOn)
-    {
-        if (hasBeen(Applied))
-            return;
+        @Override
+        public PartialTxn partialTxn()
+        {
+            checkCanReadFrom();
+            return partialTxn;
+        }
 
-        if (updatePredecessor(predecessor))
-            maybeExecute(safeStore, progressShard(safeStore), false, notifyWaitingOn);
+        @Override
+        public @Nullable PartialDeps partialDeps()
+        {
+            checkCanReadFrom();
+            return partialDeps;
+        }
     }
 
-    static class NotifyWaitingOn implements PreLoadContext, Consumer<SafeCommandStore>
+    public static class Accepted extends Preaccepted
     {
-        Known[] blockedUntil = new Known[4];
-        TxnId[] txnIds = new TxnId[4];
-        int depth;
+        private final Ballot accepted;
 
-        public NotifyWaitingOn(Command command)
+        private Accepted(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted)
+        {
+            super(common, status, executeAt, promised);
+            this.accepted = accepted;
+        }
+
+        @Override
+        public boolean equals(Object o)
         {
-            txnIds[0] = command.txnId();
-            blockedUntil[0] = Done;
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+            if (!super.equals(o)) return false;
+            Accepted that = (Accepted) o;
+            return Objects.equals(accepted, that.accepted);
         }
 
         @Override
-        public void accept(SafeCommandStore safeStore)
+        public int hashCode()
         {
-            Command prev = get(safeStore, depth - 1);
-            while (depth >= 0)
+            int hash = super.hashCode();
+            hash = 31 * hash + Objects.hashCode(accepted);
+            return hash;
+        }
+
+        private static class Factory
+        {
+            static Accepted create(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted)
             {
-                Command cur = safeStore.ifLoaded(txnIds[depth]);
-                Known until = blockedUntil[depth];
-                if (cur == null)
-                {
-                    // need to load; schedule execution for later
-                    safeStore.execute(this, this);
-                    return;
-                }
+                return new Accepted(common, status, executeAt, promised, accepted);
+            }
 
-                if (prev != null)
-                {
-                    if (cur.has(until) || (cur.hasBeen(PreCommitted) && cur.executeAt().compareTo(prev.executeAt()) > 0))
-                    {
-                        prev.updatePredecessorAndMaybeExecute(safeStore, cur, false);
-                        --depth;
-                        prev = get(safeStore, depth - 1);
-                        continue;
-                    }
-                }
-                else if (cur.has(until))
-                {
-                    // we're done; have already applied
-                    Invariants.checkState(depth == 0);
-                    break;
-                }
+            static Accepted update(Accepted command, CommonAttributes common, SaveStatus status, Ballot promised)
+            {
+                checkPromised(command, promised);
+                checkSameClass(command, Accepted.class, "Cannot update");
+                command.checkCanUpdate();
+                return new Accepted(common, status, command.executeAt(), promised, command.accepted());
+            }
 
-                TxnId directlyBlockedOnCommit = cur.firstWaitingOnCommit();
-                TxnId directlyBlockedOnApply = cur.firstWaitingOnApply(directlyBlockedOnCommit);
-                if (directlyBlockedOnApply != null)
-                {
-                    push(directlyBlockedOnApply, Done);
-                }
-                else if (directlyBlockedOnCommit != null)
-                {
-                    push(directlyBlockedOnCommit, ExecuteAtOnly);
-                }
-                else
-                {
-                    if (cur.hasBeen(Committed) && !cur.hasBeen(ReadyToExecute) && !cur.isWaitingOnDependency())
-                    {
-                        if (!cur.maybeExecute(safeStore, cur.progressShard(safeStore), false, false))
-                            throw new AssertionError("Is able to Apply, but has not done so");
-                        // loop and re-test the command's status; we may still want to notify blocking, esp. if not homeShard
-                        continue;
-                    }
-
-                    Unseekables<?, ?> someKeys = cur.maxUnseekables();
-                    if (someKeys == null && prev != null) someKeys = prev.partialDeps().someUnseekables(cur.txnId());
-                    Invariants.checkState(someKeys != null);
-                    logger.trace("{} blocked on {} until {}", txnIds[0], cur.txnId(), until);
-                    safeStore.progressLog().waiting(cur.txnId(), until, someKeys);
-                    return;
-                }
-                prev = cur;
+            static Accepted update(Accepted command, CommonAttributes common, Ballot promised)
+            {
+                return update(command, common, command.saveStatus(), promised);
             }
         }
 
-        private Command get(SafeCommandStore safeStore, int i)
+        @Override
+        public Ballot accepted()
         {
-            return i >= 0 ? safeStore.command(txnIds[i]) : null;
+            checkCanReadFrom();
+            return accepted;
         }
+    }
 
-        void push(TxnId by, Known until)
+    public static class Committed extends Accepted
+    {
+        private final ImmutableSortedSet<TxnId> waitingOnCommit;
+        private final ImmutableSortedMap<Timestamp, TxnId> waitingOnApply;
+
+        private Committed(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply)
         {
-            if (++depth == txnIds.length)
-            {
-                txnIds = Arrays.copyOf(txnIds, txnIds.length * 2);
-                blockedUntil = Arrays.copyOf(blockedUntil, txnIds.length);
-            }
-            txnIds[depth] = by;
-            blockedUntil[depth] = until;
+            super(common, status, executeAt, promised, accepted);
+            this.waitingOnCommit = waitingOnCommit;
+            this.waitingOnApply = waitingOnApply;
+        }
+
+        private Committed(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, WaitingOn waitingOn)
+        {
+            this(common, status, executeAt, promised, accepted, waitingOn.waitingOnCommit, waitingOn.waitingOnApply);
         }
 
         @Override
-        public Iterable<TxnId> txnIds()
+        public boolean equals(Object o)
         {
-            return Arrays.asList(txnIds).subList(0, depth + 1);
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+            if (!super.equals(o)) return false;
+            Committed committed = (Committed) o;
+            return Objects.equals(waitingOnCommit, committed.waitingOnCommit)
+                    && Objects.equals(waitingOnApply, committed.waitingOnApply);
         }
 
         @Override
-        public Seekables<?, ?> keys()
+        public int hashCode()
         {
-            return Keys.EMPTY;
+            int hash = super.hashCode();
+            hash = 31 * hash + Objects.hashCode(waitingOnCommit);
+            hash = 31 * hash + Objects.hashCode(waitingOnApply);
+            return hash;
         }
-    }
 
-    /**
-     * A key nominated to represent the "home" shard - only members of the home shard may be nominated to recover
-     * a transaction, to reduce the cluster-wide overhead of ensuring progress. A transaction that has only been
-     * witnessed at PreAccept may however trigger a process of ensuring the home shard is durably informed of
-     * the transaction.
-     *
-     * Note that for ProgressLog purposes the "home shard" is the shard as of txnId.epoch.
-     * For recovery purposes the "home shard" is as of txnId.epoch until Committed, and executeAt.epoch once Executed
-     */
-    public final void homeKey(RoutingKey homeKey)
-    {
-        RoutingKey current = homeKey();
-        if (current == null) setHomeKey(homeKey);
-        else if (!current.equals(homeKey)) throw new AssertionError();
-    }
+        private static class Factory
+        {
+            private static Committed update(Committed command, CommonAttributes common, Ballot promised, SaveStatus status, ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply)
+            {
+                checkPromised(command, promised);
+                checkSameClass(command, Committed.class, "Cannot update");
+                return new Committed(common, status, command.executeAt(), promised, command.accepted(), waitingOnCommit, waitingOnApply);
+            }
 
-    public void updateHomeKey(SafeCommandStore safeStore, RoutingKey homeKey)
-    {
-        if (homeKey() == null)
+            private static Committed update(Committed command, CommonAttributes common, Ballot promised)
+            {
+                return update(command, common, promised, command.saveStatus(), command.waitingOnCommit(), command.waitingOnApply());
+            }
+
+            private static Committed update(Committed command, CommonAttributes common, SaveStatus status)
+            {
+                return update(command, common, command.promised(), status, command.waitingOnCommit(), command.waitingOnApply());
+            }
+
+            private static Committed update(Committed command, CommonAttributes common, WaitingOn waitingOn)
+            {
+                return update(command, common, command.promised(), command.saveStatus(), waitingOn.waitingOnCommit, waitingOn.waitingOnApply);
+            }
+
+            public static Committed create(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply)
+            {
+                return new Committed(common, status, executeAt, promised, accepted, waitingOnCommit, waitingOnApply);
+            }
+
+            public static Committed create(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, WaitingOn waitingOn)
+            {
+                return new Committed(common, status, executeAt, promised, accepted, waitingOn.waitingOnCommit, waitingOn.waitingOnApply);
+            }
+        }
+
+        public AsyncChain<Data> read(SafeCommandStore safeStore)
         {
-            setHomeKey(homeKey);
-            // TODO (low priority, safety): if we're processed on a node that does not know the latest epoch,
-            //      do we guarantee the home key calculation is unchanged since the prior epoch?
-            if (progressKey() == null && owns(safeStore, txnId().epoch(), homeKey))
-                progressKey(homeKey);
+            checkCanReadFrom();
+            return partialTxn().read(safeStore, this);
         }
-        else if (!this.homeKey().equals(homeKey))
+
+        public WaitingOn waitingOn()
         {
-            throw new IllegalStateException();
+            return new WaitingOn(waitingOnCommit, waitingOnApply);
         }
-    }
 
-    private ProgressShard progressShard(SafeCommandStore safeStore, Route<?> route, @Nullable RoutingKey progressKey, Ranges coordinateRanges)
-    {
-        updateHomeKey(safeStore, route.homeKey());
+        public ImmutableSortedSet<TxnId> waitingOnCommit()
+        {
+            checkCanReadFrom();
+            return waitingOnCommit;
+        }
 
-        if (progressKey == null || progressKey == NO_PROGRESS_KEY)
+        public boolean isWaitingOnCommit()
         {
-            if (this.progressKey() == null)
-                setProgressKey(NO_PROGRESS_KEY);
+            checkCanReadFrom();
+            return waitingOnCommit != null && !waitingOnCommit.isEmpty();
+        }
 
-            return No;
+        public TxnId firstWaitingOnCommit()
+        {
+            checkCanReadFrom();
+            return isWaitingOnCommit() ? waitingOnCommit.first() : null;
         }
 
-        if (this.progressKey() == null) setProgressKey(progressKey);
-        else if (!this.progressKey().equals(progressKey)) throw new AssertionError();
+        public ImmutableSortedMap<Timestamp, TxnId> waitingOnApply()
+        {
+            checkCanReadFrom();
+            return waitingOnApply;
+        }
 
-        if (!coordinateRanges.contains(progressKey))
-            return No;
+        public boolean isWaitingOnApply()
+        {
+            checkCanReadFrom();
+            return waitingOnApply != null && !waitingOnApply.isEmpty();
+        }
 
-        return progressKey.equals(homeKey()) ? Home : Local;
-    }
+        public TxnId firstWaitingOnApply()
+        {
+            checkCanReadFrom();
+            return isWaitingOnApply() ? waitingOnApply.firstEntry().getValue() : null;
+        }
 
-    /**
-     * A key nominated to be the primary shard within this node for managing progress of the command.
-     * It is nominated only as of txnId.epoch, and may be null (indicating that this node does not monitor
-     * the progress of this command).
-     *
-     * Preferentially, this is homeKey on nodes that replicate it, and otherwise any key that is replicated, as of txnId.epoch
-     */
+        public boolean hasBeenWitnessed()
+        {
+            checkCanReadFrom();
+            return partialTxn() != null;
+        }
 
-    public final void progressKey(RoutingKey progressKey)
-    {
-        RoutingKey current = progressKey();
-        if (current == null) setProgressKey(progressKey);
-        else if (!current.equals(progressKey)) throw new AssertionError();
+        public boolean isWaitingOnDependency()
+        {
+            checkCanReadFrom();
+            return isWaitingOnCommit() || isWaitingOnApply();
+        }
     }
 
-    private ProgressShard progressShard(SafeCommandStore safeStore, Route<?> route, Ranges coordinateRanges)
+    public static class Executed extends Committed
     {
-        if (progressKey() == null)
-            return Unsure;
+        private final Writes writes;
+        private final Result result;
+
+        public Executed(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply, Writes writes, Result result)
+        {
+            super(common, status, executeAt, promised, accepted, waitingOnCommit, waitingOnApply);
+            this.writes = writes;
+            this.result = result;
+        }
+
+        public Executed(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, WaitingOn waitingOn, Writes writes, Result result)
+        {
+            super(common, status, executeAt, promised, accepted, waitingOn);
+            this.writes = writes;
+            this.result = result;
+        }
+
+        @Override
+        public boolean equals(Object o)
+        {
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+            if (!super.equals(o)) return false;
+            Executed executed = (Executed) o;
+            return Objects.equals(writes, executed.writes)
+                    && Objects.equals(result, executed.result);
+        }
+
+        @Override
+        public int hashCode()
+        {
+            // AILA, Mum
+            int hash = super.hashCode();
+            hash = 31 * hash + Objects.hashCode(writes);
+            hash = 31 * hash + Objects.hashCode(result);
+            return hash;
+        }
+
+        private static class Factory
+        {
+            public static Executed update(Executed command, CommonAttributes common, SaveStatus status, Ballot promised, ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply)
+            {
+                checkSameClass(command, Executed.class, "Cannot update");
+                command.checkCanUpdate();
+                return new Executed(common, status, command.executeAt(), promised, command.accepted(), waitingOnCommit, waitingOnApply, command.writes(), command.result());
+            }
+
+            public static Executed update(Executed command, CommonAttributes common, SaveStatus status)
+            {
+                return update(command, common, status, command.promised(), command.waitingOnCommit(), command.waitingOnApply());
+            }
+
+            public static Executed update(Executed command, CommonAttributes common, WaitingOn waitingOn)
+            {
+                return update(command, common, command.saveStatus(), command.promised(), waitingOn.waitingOnCommit, waitingOn.waitingOnApply);
+            }
 
-        return progressShard(safeStore, route, progressKey(), coordinateRanges);
+            public static Executed update(Executed command, CommonAttributes common, Ballot promised)
+            {
+                return update(command, common, command.saveStatus(), promised, command.waitingOnCommit(), command.waitingOnApply());
+            }
+
+            public static Executed create(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply, Writes writes, Result result)
+            {
+                return new Executed(common, status, executeAt, promised, accepted, waitingOnCommit, waitingOnApply, writes, result);
+            }
+
+            public static Executed create(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, WaitingOn waitingOn, Writes writes, Result result)
+            {
+                return new Executed(common, status, executeAt, promised, accepted, waitingOn.waitingOnCommit, waitingOn.waitingOnApply, writes, result);
+            }
+        }
+
+        public Writes writes()
+        {
+            checkCanReadFrom();
+            return writes;
+        }
+
+        public Result result()
+        {
+            checkCanReadFrom();
+            return result;
+        }
     }
 
-    private ProgressShard progressShard(SafeCommandStore safeStore)
+    public static class WaitingOn
     {
-        RoutingKey progressKey = progressKey();
-        if (progressKey == null)
-            return Unsure;
+        public static final WaitingOn EMPTY = new WaitingOn(ImmutableSortedSet.of(), ImmutableSortedMap.of());
+        public final ImmutableSortedSet<TxnId> waitingOnCommit;
+        public final ImmutableSortedMap<Timestamp, TxnId> waitingOnApply;
+
+        public WaitingOn(ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply)
+        {
+            this.waitingOnCommit = waitingOnCommit;
+            this.waitingOnApply = waitingOnApply;
+        }
+
+        public static class Update
+        {
+            private boolean hasChanges = false;
+            private NavigableSet<TxnId> waitingOnCommit;
+            private NavigableMap<Timestamp, TxnId> waitingOnApply;
+
+            public Update()
+            {
 
-        if (progressKey == NO_PROGRESS_KEY)
-            return No;
+            }
+
+            public Update(WaitingOn waitingOn)
+            {
+                this.waitingOnCommit = waitingOn.waitingOnCommit;
+                this.waitingOnApply = waitingOn.waitingOnApply;
+            }
 
-        Ranges coordinateRanges = safeStore.ranges().at(txnId().epoch());
-        if (!coordinateRanges.contains(progressKey))
-            return No;
+            public Update(Committed committed)
+            {
+                this.waitingOnCommit = committed.waitingOnCommit();
+                this.waitingOnApply = committed.waitingOnApply();
+            }
 
-        return progressKey.equals(homeKey()) ? Home : Local;
+            public boolean hasChanges()
+            {
+                return hasChanges;
+            }
+
+            public void addWaitingOnCommit(TxnId txnId)
+            {
+                waitingOnCommit = ensureSortedMutable(waitingOnCommit);
+                waitingOnCommit.add(txnId);
+                hasChanges = true;
+            }
+
+            public void removeWaitingOnCommit(TxnId txnId)
+            {
+                if (waitingOnApply == null)
+                    return;
+                waitingOnCommit = ensureSortedMutable(waitingOnCommit);
+                waitingOnCommit.remove(txnId);
+                hasChanges = true;
+            }
+
+            public void addWaitingOnApply(TxnId txnId, Timestamp executeAt)
+            {
+                waitingOnApply = ensureSortedMutable(waitingOnApply);
+                waitingOnApply.put(executeAt, txnId);
+                hasChanges = true;
+            }
+
+            public void removeWaitingOnApply(TxnId txnId, Timestamp executeAt)
+            {
+                if (waitingOnApply == null)
+                    return;
+                waitingOnApply = ensureSortedMutable(waitingOnApply);
+                waitingOnApply.remove(executeAt);
+                hasChanges = true;
+            }
+
+            public void removeWaitingOn(TxnId txnId, Timestamp executeAt)
+            {
+                removeWaitingOnCommit(txnId);
+                removeWaitingOnApply(txnId, executeAt);
+                hasChanges = true;
+            }
+
+            public WaitingOn build()
+            {
+                if ((waitingOnCommit == null || waitingOnCommit.isEmpty()) && (waitingOnApply == null || waitingOnApply.isEmpty()))
+                    return EMPTY;
+                return new WaitingOn(ensureSortedImmutable(waitingOnCommit), ensureSortedImmutable(waitingOnApply));
+            }
+        }
     }
 
-    private Ranges coordinateRanges(SafeCommandStore safeStore)
+    private static Command updateAttributes(Command command, CommonAttributes attributes, Ballot promised)
     {
-        return safeStore.ranges().at(txnId().epoch());
+        switch (command.saveStatus())
+        {
+            case NotWitnessed:
+                return NotWitnessed.Factory.update((NotWitnessed) command, attributes, promised);
+            case PreAccepted:
+                return Preaccepted.Factory.update((Preaccepted) command, attributes, promised);
+            case AcceptedInvalidate:
+            case AcceptedInvalidateWithDefinition:
+            case Accepted:
+            case AcceptedWithDefinition:
+                return Accepted.Factory.update((Accepted) command, attributes, promised);
+            case Committed:
+            case ReadyToExecute:
+                return Committed.Factory.update((Committed) command, attributes, promised);
+            case PreApplied:
+            case Applied:
+            case Invalidated:
+                return Executed.Factory.update((Executed) command, attributes, promised);
+            default:
+                throw new IllegalStateException("Unhandled status " + command.status());
+        }
     }
 
-    private Ranges executeRanges(SafeCommandStore safeStore, Timestamp executeAt)
+    private static Command updateAttributes(Command command, CommonAttributes attributes)
     {
-        return safeStore.ranges().since(executeAt.epoch());
+        return updateAttributes(command, attributes, command.promised());
     }
 
-    enum EnsureAction { Ignore, Check, Add, TrySet, Set }
-
-    /**
-     * Validate we have sufficient information for the route, partialTxn and partialDeps fields, and if so update them;
-     * otherwise return false (or throw an exception if an illegal state is encountered)
-     */
-    private boolean validate(Ranges existingRanges, Ranges additionalRanges, ProgressShard shard,
-                             Route<?> route, EnsureAction ensureRoute,
-                             @Nullable PartialTxn partialTxn, EnsureAction ensurePartialTxn,
-                             @Nullable PartialDeps partialDeps, EnsureAction ensurePartialDeps)
+    public static class Update implements CommonAttributes
     {
-        if (shard == Unsure)
-            return false;
+        private static class ToRegister<T>
+        {
+            private final T value;
+            private final Ranges slice;
+
+            public ToRegister(T value, Ranges slice)
+            {
+                this.value = value;
+                this.slice = slice;
+            }
+
+            @Override
+            public boolean equals(Object o)
+            {
+                if (this == o) return true;
+                if (o == null || getClass() != o.getClass()) return false;
+                ToRegister<?> that = (ToRegister<?>) o;
+                return value.equals(that.value) && slice.equals(that.slice);
+            }
+
+            @Override
+            public int hashCode()
+            {
+                int hash = 1;
+                hash = 31 * hash + value.hashCode();
+                hash = 31 * hash + slice.hashCode();
+                return hash;
+            }
+        }
+
+        private boolean completed = false;
+        public final SafeCommandStore safeStore;
+        private final Command command;
 
-        // first validate route
-        if (shard.isHome())
+        private RoutingKey homeKey;
+        private RoutingKey progressKey;
+        private Route<?> route;
+        private Status.Durability durability;
+
+        private PartialTxn partialTxn;
+        private @Nullable PartialDeps partialDeps;
+
+        private Set<ToRegister<Seekable>> singleRegistrations = new HashSet<>();
+        private Set<ToRegister<Seekables<?, ?>>> multiRegistrations = new HashSet<>();
+        private Set<CommandListener> listeners;
+
+        public Update(SafeCommandStore safeStore, Command command)
         {
-            switch (ensureRoute)
+            this.safeStore = safeStore;
+            command.checkCanUpdate();
+            this.command = command;
+            this.homeKey = command.homeKey();
+            this.progressKey = command.progressKey();
+            this.route = command.route();
+            this.durability = command.durability();
+            this.listeners = command.listeners();
+            if (command.isWitnessed())
             {
-                default: throw new AssertionError();
-                case Check:
-                    if (!isFullRoute(route()) && !isFullRoute(route))
-                        return false;
-                case Ignore:
-                    break;
-                case Add:
-                case Set:
-                    if (!isFullRoute(route))
-                        throw new IllegalArgumentException("Incomplete route (" + route + ") sent to home shard");
-                    break;
-                case TrySet:
-                    if (!isFullRoute(route))
-                        return false;
+                Preaccepted preaccepted = command.asWitnessed();
+                this.partialTxn = preaccepted.partialTxn();
+                this.partialDeps = preaccepted.partialDeps();
             }
         }
-        else
+
+        private void checkNotCompleted()
         {
-            // failing any of these tests is always an illegal state
-            if (!route.covers(existingRanges))
-                return false;
+            if (completed)
+                throw new IllegalStateException(this + " has been completed");
+        }
 
-            if (existingRanges != additionalRanges && !route.covers(additionalRanges))
-                throw new IllegalArgumentException("Incomplete route (" + route + ") provided; does not cover " + additionalRanges);
+        @Override
+        public TxnId txnId()
+        {
+            return command.txnId();
         }
 
-        // invalid to Add deps to Accepted or AcceptedInvalidate statuses, as Committed deps are not equivalent
-        // and we may erroneously believe we have covered a wider range than we have infact covered
-        if (ensurePartialDeps == Add)
-            Invariants.checkState(status() != Accepted && status() != AcceptedInvalidate);
+        public Status status()
+        {
+            return command.status();
+        }
 
-        // validate new partial txn
-        if (!validate(ensurePartialTxn, existingRanges, additionalRanges, covers(partialTxn()), covers(partialTxn), "txn", partialTxn))
-            return false;
+        @Override
+        public RoutingKey homeKey()
+        {
+            checkNotCompleted();
+            return homeKey;
+        }
 
-        if (partialTxn != null && txnId().rw() != partialTxn.kind())
-            throw new IllegalArgumentException("Transaction has different kind to its TxnId");
+        public Update homeKey(RoutingKey homeKey)
+        {
+            checkNotCompleted();
+            this.homeKey = homeKey;
+            return this;
+        }
 
-        if (shard.isHome() && ensurePartialTxn != Ignore)
+        @Override
+        public RoutingKey progressKey()
         {
-            if (!hasQuery(partialTxn()) && !hasQuery(partialTxn))
-                throw new IllegalStateException();
+            checkNotCompleted();
+            return progressKey;
         }
 
-        return validate(ensurePartialDeps, existingRanges, additionalRanges, covers(partialDeps()), covers(partialDeps), "deps", partialDeps);
-    }
+        /**
+         * A key nominated to be the primary shard within this node for managing progress of the command.
+         * It is nominated only as of txnId.epoch, and may be null (indicating that this node does not monitor
+         * the progress of this command).
+         *
+         * Preferentially, this is homeKey on nodes that replicate it, and otherwise any key that is replicated, as of txnId.epoch
+         */
+        public Update progressKey(RoutingKey progressKey)
+        {
+            checkNotCompleted();
+            RoutingKey current = command.progressKey();
+            Invariants.checkArgument(current == null || current.equals(progressKey));
+            this.progressKey = progressKey;
+            return this;
+        }
 
-    private void set(SafeCommandStore safeStore,
-                     Ranges existingRanges, Ranges additionalRanges, ProgressShard shard, Route<?> route,
-                     @Nullable PartialTxn partialTxn, EnsureAction ensurePartialTxn,
-                     @Nullable PartialDeps partialDeps, EnsureAction ensurePartialDeps)
-    {
-        Invariants.checkState(progressKey() != null);
-        Ranges allRanges = existingRanges.with(additionalRanges);
+        @Override
+        public Route<?> route()
+        {
+            checkNotCompleted();
+            return route;
+        }
 
-        if (shard.isProgress()) setRoute(Route.merge(route(), (Route)route));
-        else setRoute(route.slice(allRanges));
+        public Update route(Route<?> route)
+        {
+            checkNotCompleted();
+            this.route = route;
+            return this;
+        }
 
-        switch (ensurePartialTxn)
+        @Override
+        public Status.Durability durability()
         {
-            case Add:
-                if (partialTxn == null)
-                    break;
+            checkNotCompleted();
+            return Command.durability(durability, command.saveStatus());
+        }
 
-                if (partialTxn() != null)
-                {
-                    partialTxn = partialTxn.slice(allRanges, shard.isHome());
-                    Routables.foldlMissing((Seekables)partialTxn.keys(), partialTxn().keys(), (keyOrRange, p, v, i) -> {
-                        // TODO (expected, efficiency): we may register the same ranges more than once
-                        safeStore.register(keyOrRange, allRanges, this);
-                        return v;
-                    }, 0, 0, 1);
-                    this.setPartialTxn(partialTxn().with(partialTxn));
-                    break;
-                }
+        public Update durability(Status.Durability durability)
+        {
+            checkNotCompleted();
+            this.durability = durability;
+            return this;
+        }
 
-            case Set:
-            case TrySet:
-                setPartialTxn(partialTxn = partialTxn.slice(allRanges, shard.isHome()));
-                // TODO (expected, efficiency): we may register the same ranges more than once
-                // TODO (desirable, efficiency): no need to register on PreAccept if already Accepted
-                safeStore.register(partialTxn.keys(), allRanges, this);
-                break;
+        @Override
+        public ImmutableSet<CommandListener> listeners()
+        {
+            return ensureImmutable(listeners);
         }
 
-        switch (ensurePartialDeps)
+        public Update addListener(CommandListener listener)
         {
-            case Add:
-                if (partialDeps == null)
-                    break;
+            listeners = ensureMutable(listeners);
+            listeners.add(listener);
+            return this;
+        }
 
-                if (partialDeps() != null)
-                {
-                    setPartialDeps(partialDeps().with(partialDeps.slice(allRanges)));
-                    break;
-                }
+        public Update removeListener(CommandListener listener)
+        {
+            if (listener == null || listeners.isEmpty())
+                return this;
+            listeners = ensureMutable(listeners);
+            listeners.remove(listener);
+            return this;
+        }
 
-            case Set:
-            case TrySet:
-                setPartialDeps(partialDeps.slice(allRanges));
-                break;
+        @Override
+        public PartialTxn partialTxn()
+        {
+            checkNotCompleted();
+            return partialTxn;
         }
-    }
 
-    private static boolean validate(EnsureAction action, Ranges existingRanges, Ranges additionalRanges,
-                                    Ranges existing, Ranges adding, String kind, Object obj)
-    {
-        switch (action)
+        public Update partialTxn(PartialTxn partialTxn)
         {
-            default: throw new IllegalStateException();
-            case Ignore:
-                break;
+            checkNotCompleted();
+            this.partialTxn = partialTxn;
+            return this;
+        }
 
-            case TrySet:
-                if (adding != null)
-                {
-                    if (!adding.containsAll(existingRanges))
-                        return false;
+        @Override
+        public @Nullable PartialDeps partialDeps()
+        {
+            checkNotCompleted();
+            return partialDeps;
+        }
 
-                    if (additionalRanges != existingRanges && !adding.containsAll(additionalRanges))
-                        return false;
+        public Update partialDeps(@Nullable PartialDeps partialDeps)
+        {
+            checkNotCompleted();
+            this.partialDeps = partialDeps;
+            return this;
+        }
 
-                    break;
-                }
-            case Set:
-                // failing any of these tests is always an illegal state
-                Invariants.checkState(adding != null);
-                if (!adding.containsAll(existingRanges))
-                    throw new IllegalArgumentException("Incomplete " + kind + " (" + obj + ") provided; does not cover " + existingRanges);
-
-                if (additionalRanges != existingRanges && !adding.containsAll(additionalRanges))
-                    throw new IllegalArgumentException("Incomplete " + kind + " (" + obj + ") provided; does not cover " + additionalRanges);
-                break;
-
-            case Check:
-            case Add:
-                if (adding == null)
-                {
-                    if (existing == null)
-                        return false;
+        public Update registerWith(Seekables<?, ?> keysOrRanges, Ranges slice)
+        {
+            checkNotCompleted();
+            multiRegistrations.add(new ToRegister<>(keysOrRanges, slice));
+            return this;
+        }
 
-                    Invariants.checkState(existing.containsAll(existingRanges));
-                    if (existingRanges != additionalRanges && !existing.containsAll(additionalRanges))
-                    {
-                        if (action == Check)
-                            return false;
 
-                        throw new IllegalArgumentException("Missing additional " + kind + "; existing does not cover " + additionalRanges.difference(existingRanges));
-                    }
-                }
-                else if (existing != null)
+        public Update registerWith(Seekable keyOrRange, Ranges slice)
+        {
+            checkNotCompleted();
+            singleRegistrations.add(new ToRegister<>(keyOrRange, slice));
+            return this;
+        }
+
+        protected  <T extends Command> T complete(T updated)
+        {
+            checkNotCompleted();
+
+            if (updated == command)
+                throw new IllegalStateException("Update is the same as the original");
+
+            updated.markActive();
+
+            int initialListenerSize = listeners.size();
+
+            for (ToRegister<Seekables<?, ?>> toRegister : multiRegistrations)
+            {
+                safeStore.register(toRegister.value, toRegister.slice, updated);
+                for (Seekable seekable: toRegister.value)
+                    if (seekable.domain() == Routable.Domain.Key)
+                        addListener(CommandsForKey.listener(seekable.asKey()));
+            }
+
+            for (ToRegister<Seekable> toRegister : singleRegistrations)
+            {
+                safeStore.register(toRegister.value, toRegister.slice, updated);
+                if (toRegister.value.domain() == Routable.Domain.Key)
+                    addListener(CommandsForKey.listener(toRegister.value.asKey()));
+            }
+
+            if (listeners.size() > initialListenerSize)
+            {
+                Command preUpdate = updated;
+                updated = (T) Command.updateAttributes(updated, this);
+                if (updated != preUpdate)
                 {
-                    Ranges covering = adding.with(existing);
-                    Invariants.checkState(covering.containsAll(existingRanges));
-                    if (existingRanges != additionalRanges && !covering.containsAll(additionalRanges))
-                    {
-                        if (action == Check)
-                            return false;
-
-                        throw new IllegalArgumentException("Incomplete additional " + kind + " (" + obj + ") provided; does not cover " + additionalRanges.difference(existingRanges));
-                    }
+                    preUpdate.markInvalidated();
+                    updated.markActive();
                 }
-                else
-                {
-                    if (!adding.containsAll(existingRanges))
-                        return false;
+            }
 
-                    if (existingRanges != additionalRanges && !adding.containsAll(additionalRanges))
-                    {
-                        if (action == Check)
-                            return false;
+            if (command != null)
+                command.markSuperseded();
 
-                        throw new IllegalArgumentException("Incomplete additional " + kind + " (" + obj + ") provided; does not cover " + additionalRanges.difference(existingRanges));
-                    }
-                }
-                break;
-        }
+            safeStore.completeUpdate(this, command, updated);
+            completed = true;
 
-        return true;
-    }
+            return updated;
+        }
 
-    // TODO (low priority, progress): callers should try to consult the local progress shard (if any) to obtain the full set of keys owned locally
-    public Route<?> someRoute()
-    {
-        if (route() != null)
-            return route();
+        public Command updateAttributes()
+        {
+            return complete(Command.updateAttributes(command, this));
+        }
 
-        if (homeKey() != null)
-            return PartialRoute.empty(txnId().domain(), homeKey());
+        public Preaccepted preaccept(Timestamp executeAt, Ballot ballot)
+        {
+            if (command.status() == Status.NotWitnessed)
+            {
+                return complete(Preaccepted.Factory.create(this, executeAt, ballot));
+            }
+            else if (command.status() == Status.AcceptedInvalidate && command.executeAt() == null)
+            {
+                Accepted accepted = command.asAccepted();
+                return complete(Accepted.Factory.create(this, accepted.saveStatus(), executeAt, accepted.promised(), accepted.accepted()));
+            }
+            else
+            {
+                Invariants.checkState(command.status() == Status.Accepted);
+                return (Preaccepted) complete(Command.updateAttributes(command, this));
+            }
+        }
 
-        return null;
-    }
+        public Accepted markDefined(Ballot promised)
+        {
+            Invariants.checkState(command.hasBeen(Status.AcceptedInvalidate));

Review Comment:
   PreCommitted state isn't correctly handled. I have addressed this in my suggestion patch.



##########
accord-core/src/main/java/accord/local/ImmutableState.java:
##########
@@ -0,0 +1,202 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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 accord.local;
+
+/**
+ * Since metadata instances are immutable, there can be several copies floating around in memory, all but one
+ * of which is stale. This can lead to difficult to diagnose bugs, especially when an implementation side cache
+ * is involved.
+ * The ImmutableState base class defines the various lifecycle stage and helps restrict what the user does with it,
+ * with the goal or throwing an exception as soon as an illegal usage occurs, instead of after.
+ *
+ * An up to date instances can have one of 2 statuses, DORMANT or ACTIVE. An instance is only ACTIVE in the time
+ * between when the safe store for it's current operation is created, and closed, and is otherwise marked DORMANT.
+ * While DORMANT, it cannot be read from or updated. This is to help detect leaked instances being read from or
+ * updated when they shouldn't be.
+ *
+ * Once an update has created a superseding instance, the original instance is marked SUPERSEDED. It can then be
+ * marked CLEANING_UP, during which time its fields can be read to assist in determining what has been updated.
+ * From CLEANING_UP, an instance can be marked INVALIDATED to indicate that any access is illegal. An instance
+ * marked SUPERSEDED can also go directly to INVALIDATED, in the case of intermediate updates.
+ */
+public abstract class ImmutableState

Review Comment:
   So, it looks like this has been introduced to grapple with multiple versions of a `Command`. But it seems to me that this isn't sufficient (there's a related just-found bug with range transactions as testimony), but also that this materially harms readability in many unrelated parts of the system. The checks are also not easily maintained, future maintenance will likely cause them to atrophy.
   
   I think we should instead be working to forbid having more than one version accessible to the `CommandStore`, without at least knowing (with strong typing) that one may be stale.
   
   Firstly, I wonder if a cleaner concept mightn't be to have a concept of `SafeCommand` or `LiveCommand` that is an indirect reference to the store's latest version of the `Command` (or has such a pointer for validation purposes, and fails if the local reference is different). In other cases a command should be treated as stale, or we could have a dedicated `StaleCommand` interface.
   
   I think we should also make sure that, as far as possible, we do not keep more than one command around internally. For instance, our `SafeCommandStore` doesn't need to have its own separate copy, it should reference the global map directly, and publish updates to the global map directly. This should be easier without the builder control flow.
   
   WDYT?



##########
accord-core/src/main/java/accord/local/SafeCommandStore.java:
##########
@@ -90,6 +107,37 @@ <T> T mapReduce(Seekables<?, ?> keys, Ranges slice,
     long latestEpoch();
     Timestamp preaccept(TxnId txnId, Seekables<?, ?> keys);
 
-    Future<Void> execute(PreLoadContext context, Consumer<? super SafeCommandStore> consumer);
-    <T> Future<T> submit(PreLoadContext context, Function<? super SafeCommandStore, T> function);
+    default void notifyListeners(Command command)
+    {
+        TxnId txnId = command.txnId();
+        for (CommandListener listener : command.listeners())
+        {
+            PreLoadContext context = listener.listenerPreLoadContext(command.txnId());
+            if (canExecuteWith(context))
+            {
+                listener.onChange(this, txnId);
+            }
+            else
+            {
+                commandStore().execute(context, safeStore -> listener.onChange(safeStore, txnId)).begin(agent());
+            }
+        }
+    }
+
+    Command.Update beginUpdate(Command command);
+
+    default Command.Update beginUpdate(TxnId txnId)
+    {
+        return beginUpdate(command(txnId));
+    }
+
+    void completeUpdate(Command.Update update, Command current, Command updated);
+
+    CommandsForKey.Update beginUpdate(CommandsForKey commandsForKey);
+
+    void completeUpdate(CommandsForKey.Update update, CommandsForKey current, CommandsForKey updated);
+
+    PostExecuteContext complete();

Review Comment:
   This method and some of the others seem to be an implementation detail, and perhaps better not to be on the interface?



##########
accord-core/src/main/java/accord/impl/CommandsForKey.java:
##########
@@ -20,97 +20,550 @@
 
 import accord.api.Key;
 import accord.local.*;
-import accord.local.SafeCommandStore.CommandFunction;
-import accord.local.SafeCommandStore.TestDep;
-import accord.local.SafeCommandStore.TestKind;
-import accord.primitives.Keys;
-import accord.primitives.Timestamp;
-import accord.primitives.TxnId;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
+import accord.primitives.*;
+import com.google.common.collect.ImmutableSortedMap;
 
 import javax.annotation.Nullable;
+import java.util.NavigableMap;
+import java.util.Objects;
+import java.util.TreeMap;
+import java.util.concurrent.TimeUnit;
+import java.util.function.Consumer;
+import java.util.function.Predicate;
+import java.util.stream.Stream;
 
-public abstract class CommandsForKey implements CommandListener
+import static accord.local.SafeCommandStore.TestDep.ANY_DEPS;
+import static accord.local.SafeCommandStore.TestDep.WITH;
+import static accord.local.SafeCommandStore.TestKind.Ws;
+import static accord.local.Status.PreAccepted;
+import static accord.local.Status.PreCommitted;
+import static accord.utils.Utils.*;
+
+public class CommandsForKey extends ImmutableState
 {
-    private static final Logger logger = LoggerFactory.getLogger(CommandsForKey.class);
+    // sentinel value to indicate a cfk requested in a preexecute context was not found
+    // should not escape the safe command store
+    public static final CommandsForKey EMPTY = new CommandsForKey(null, null)
+    {
+        @Override public Key key() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Timestamp max() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Timestamp lastExecutedTimestamp() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public long lastExecutedMicros() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Timestamp lastWriteTimestamp() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public CommandTimeseries<?> byId() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public CommandTimeseries<?> byExecuteAt() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+
+        @Override
+        public String toString()
+        {
+            return "CommandsForKey[EMPTY]";
+        }
+    };
+
+    static
+    {
+        EMPTY.markInvalidated();
+    }
+
+    public static class SerializerSupport
+    {
+        public static CommandsForKey.Listener listener(Key key)
+        {
+            return new CommandsForKey.Listener(key);
+        }
+
+        public static  <D> CommandsForKey create(Key key, Timestamp max,
+                                                 Timestamp lastExecutedTimestamp, long lastExecutedMicros, Timestamp lastWriteTimestamp,
+                                                 CommandLoader<D> loader,
+                                                 ImmutableSortedMap<Timestamp, D> byId,
+                                                 ImmutableSortedMap<Timestamp, D> byExecuteAt)
+        {
+            return new CommandsForKey(key, max, lastExecutedTimestamp, lastExecutedMicros, lastWriteTimestamp, loader, byId, byExecuteAt);
+        }
+    }
+
+    public interface CommandLoader<D>
+    {
+        D saveForCFK(Command command);
+
+        TxnId txnId(D data);
+        Timestamp executeAt(D data);
+        Txn.Kind txnKind(D data);
+        SaveStatus saveStatus(D data);
+        PartialDeps partialDeps(D data);
+
+        default Status status(D data)
+        {
+            return saveStatus(data).status;
+        }
+
+        default Status.Known known(D data)
+        {
+            return saveStatus(data).known;
+        }
+    }
 
-    public interface CommandTimeseries
+    public static class CommandTimeseries<D>
     {
-        void add(Timestamp timestamp, Command command);
-        void remove(Timestamp timestamp);
+        public enum TestTimestamp {BEFORE, AFTER}
+
+        private final Key key;
+        protected final CommandLoader<D> loader;
+        public final ImmutableSortedMap<Timestamp, D> commands;
+
+        public CommandTimeseries(Update<D> builder)
+        {
+            this.key = builder.key;
+            this.loader = builder.loader;
+            this.commands = ensureSortedImmutable(builder.commands);
+        }
+
+        CommandTimeseries(Key key, CommandLoader<D> loader, ImmutableSortedMap<Timestamp, D> commands)
+        {
+            this.key = key;
+            this.loader = loader;
+            this.commands = commands;
+        }
 
-        boolean isEmpty();
+        public CommandTimeseries(Key key, CommandLoader<D> loader)
+        {
+            this(key, loader, ImmutableSortedMap.of());
+        }
 
-        enum TestTimestamp { BEFORE, AFTER }
+        @Override
+        public boolean equals(Object o)
+        {
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+            CommandTimeseries<?> that = (CommandTimeseries<?>) o;
+            return key.equals(that.key) && loader.equals(that.loader) && commands.equals(that.commands);
+        }
+
+        @Override
+        public int hashCode()
+        {
+            int hash = 1;
+            hash = 31 * hash + Objects.hashCode(key);
+            hash = 31 * hash + Objects.hashCode(loader);
+            hash = 31 * hash + Objects.hashCode(commands);
+            return hash;
+        }
+
+        public D get(Timestamp key)
+        {
+            return commands.get(key);
+        }
+
+        public boolean isEmpty()
+        {
+            return commands.isEmpty();
+        }
 
         /**
          * All commands before/after (exclusive of) the given timestamp
-         *
+         * <p>
          * Note that {@code testDep} applies only to commands that know at least proposed deps; if specified any
          * commands that do not know any deps will be ignored.
-         *
+         * <p>
          * TODO (expected, efficiency): TestDep should be asynchronous; data should not be kept memory-resident as only used for recovery
          */
-        <T> T mapReduce(TestKind testKind, TestTimestamp testTimestamp, Timestamp timestamp,
-                        TestDep testDep, @Nullable TxnId depId,
-                        @Nullable Status minStatus, @Nullable Status maxStatus,
-                        CommandFunction<T, T> map, T initialValue, T terminalValue);
+        public <T> T mapReduce(SafeCommandStore.TestKind testKind, TestTimestamp testTimestamp, Timestamp timestamp,
+                               SafeCommandStore.TestDep testDep, @Nullable TxnId depId,
+                               @Nullable Status minStatus, @Nullable Status maxStatus,
+                               SafeCommandStore.CommandFunction<T, T> map, T initialValue, T terminalValue)
+        {
+
+            for (D data : (testTimestamp == TestTimestamp.BEFORE ? commands.headMap(timestamp, false) : commands.tailMap(timestamp, false)).values())
+            {
+                TxnId txnId = loader.txnId(data);
+                Timestamp executeAt = loader.executeAt(data);
+                SaveStatus status = loader.saveStatus(data);
+                PartialDeps deps = loader.partialDeps(data);
+                if (testKind == Ws && txnId.isRead()) continue;
+                // If we don't have any dependencies, we treat a dependency filter as a mismatch
+                if (testDep != ANY_DEPS && (!status.known.deps.hasProposedOrDecidedDeps() || (deps.contains(depId) != (testDep == WITH))))
+                    continue;
+                if (minStatus != null && minStatus.compareTo(status.status) > 0)
+                    continue;
+                if (maxStatus != null && maxStatus.compareTo(status.status) < 0)
+                    continue;
+                initialValue = map.apply(key, txnId, executeAt, initialValue);
+                if (initialValue.equals(terminalValue))
+                    break;
+            }
+            return initialValue;
+        }
+
+        Stream<TxnId> between(Timestamp min, Timestamp max, Predicate<Status> statusPredicate)
+        {
+            return commands.subMap(min, true, max, true).values().stream()
+                    .filter(d -> statusPredicate.test(loader.status(d))).map(loader::txnId);
+        }
+
+        public Stream<D> all()
+        {
+            return commands.values().stream();
+        }
+
+        Update<D> beginUpdate()
+        {
+            return new Update<>(this);
+        }
+
+        public CommandLoader<D> loader()
+        {
+            return loader;
+        }
+
+        public static class Update<D>
+        {
+            private final Key key;
+            protected CommandLoader<D> loader;
+            protected NavigableMap<Timestamp, D> commands;
+
+            public Update(Key key, CommandLoader<D> loader)
+            {
+                this.key = key;
+                this.loader = loader;
+                this.commands = new TreeMap<>();
+            }
+
+            public Update(CommandTimeseries<D> timeseries)
+            {
+                this.key = timeseries.key;
+                this.loader = timeseries.loader;
+                this.commands = timeseries.commands;
+            }
+
+            public void add(Timestamp timestamp, Command command)
+            {
+                commands = ensureSortedMutable(commands);
+                commands.put(timestamp, loader.saveForCFK(command));
+            }
+
+            public void remove(Timestamp timestamp)
+            {
+                commands = ensureSortedMutable(commands);
+                commands.remove(timestamp);
+            }
+
+            CommandTimeseries<D> build()
+            {
+                return new CommandTimeseries<>(this);
+            }
+        }
     }
 
-    public abstract Key key();
-    public abstract CommandTimeseries byId();
-    public abstract CommandTimeseries byExecuteAt();
+    public static class Listener implements CommandListener
+    {
+        protected final Key listenerKey;
+
+        private Listener(Key listenerKey)
+        {
+            this.listenerKey = listenerKey;
+        }
+
+        @Override
+        public boolean equals(Object o)
+        {
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+            Listener that = (Listener) o;
+            return listenerKey.equals(that.listenerKey);
+        }
+
+        @Override
+        public int hashCode()
+        {
+            return Objects.hash(listenerKey);
+        }
+
+        @Override
+        public String toString()
+        {
+            return "ListenerProxy{" + listenerKey + '}';
+        }
+
+        public Key key()
+        {
+            return listenerKey;
+        }
 
-    public abstract Timestamp max();
-    protected abstract void updateMax(Timestamp timestamp);
+        @Override
+        public void onChange(SafeCommandStore safeStore, TxnId txnId)
+        {
+            CommandsForKeys.listenerUpdate(safeStore, safeStore.commandsForKey(listenerKey), safeStore.command(txnId));
+        }
+
+        @Override
+        public PreLoadContext listenerPreLoadContext(TxnId caller)
+        {
+            return PreLoadContext.contextFor(caller, Keys.of(listenerKey));
+        }
+    }
+
+    public static CommandListener listener(Key key)
+    {
+        return new Listener(key);
+    }
+
+    // TODO (now): add validation that anything inserted into *committedBy* has everything prior in its dependencies
+    private final Key key;
+    private final Timestamp max;
+    private final Timestamp lastExecutedTimestamp;
+    private final long lastExecutedMicros;
+    private final Timestamp lastWriteTimestamp;
+    private final CommandTimeseries<?> byId;
+    private final CommandTimeseries<?> byExecuteAt;
+
+    private  <D> CommandsForKey(Key key, Timestamp max,
+                              Timestamp lastExecutedTimestamp, long lastExecutedMicros, Timestamp lastWriteTimestamp,
+                              CommandLoader<D> loader,
+                              ImmutableSortedMap<Timestamp, D> committedById,
+                              ImmutableSortedMap<Timestamp, D> committedByExecuteAt)
+    {
+        this.key = key;
+        this.max = max;
+        this.lastExecutedTimestamp = lastExecutedTimestamp;
+        this.lastExecutedMicros = lastExecutedMicros;
+        this.lastWriteTimestamp = lastWriteTimestamp;
+        this.byId = new CommandTimeseries<>(key, loader, committedById);
+        this.byExecuteAt = new CommandTimeseries<>(key, loader, committedByExecuteAt);
+    }
+
+    public <D> CommandsForKey(Key key, CommandLoader<D> loader)
+    {
+        this.key = key;
+        this.max = Timestamp.NONE;
+        this.lastExecutedTimestamp = Timestamp.NONE;
+        this.lastExecutedMicros = 0;
+        this.lastWriteTimestamp = Timestamp.NONE;
+        this.byId = new CommandTimeseries<>(key, loader);
+        this.byExecuteAt = new CommandTimeseries<>(key, loader);
+    }
+
+    public CommandsForKey(Update builder)
+    {
+        this.key = builder.key;
+        this.max = builder.max;
+        this.lastExecutedTimestamp = builder.lastExecutedTimestamp;
+        this.lastExecutedMicros = builder.lastExecutedMicros;
+        this.lastWriteTimestamp = builder.lastWriteTimestamp;
+        this.byId = builder.byId.build();
+        this.byExecuteAt = builder.byExecuteAt.build();
+    }
+
+    @Override
+    public String toString()
+    {
+        return "CommandsForKey@" + System.identityHashCode(this) + '{' + key + '}';
+    }
 
     @Override
-    public PreLoadContext listenerPreLoadContext(TxnId caller)
+    public boolean equals(Object o)
     {
-        return PreLoadContext.contextFor(caller, Keys.of(key()));
+        if (this == o) return true;
+        if (o == null || getClass() != o.getClass()) return false;
+        CommandsForKey that = (CommandsForKey) o;
+        return lastExecutedMicros == that.lastExecutedMicros
+                && key.equals(that.key)
+                && Objects.equals(max, that.max)
+                && Objects.equals(lastExecutedTimestamp, that.lastExecutedTimestamp)
+                && Objects.equals(lastWriteTimestamp, that.lastWriteTimestamp)
+                && byId.equals(that.byId)
+                && byExecuteAt.equals(that.byExecuteAt);
     }
 
     @Override
-    public void onChange(SafeCommandStore safeStore, Command command)
-    {
-        logger.trace("[{}]: updating as listener in response to change on {} with status {} ({})",
-                     key(), command.txnId(), command.status(), command);
-        updateMax(command.executeAt());
-        switch (command.status())
-        {
-            default: throw new AssertionError();
-            case PreAccepted:
-            case NotWitnessed:
-            case Accepted:
-            case AcceptedInvalidate:
-            case PreCommitted:
-                break;
-            case Applied:
-            case PreApplied:
-            case Committed:
-            case ReadyToExecute:
-                byExecuteAt().remove(command.txnId());
-                byExecuteAt().add(command.executeAt(), command);
-                break;
-            case Invalidated:
-                byId().remove(command.txnId());
-                byExecuteAt().remove(command.txnId());
-                command.removeListener(this);
-                break;
-        }
-    }
-
-    public void register(Command command)
-    {
-        updateMax(command.executeAt());
-        byId().add(command.txnId(), command);
-        byExecuteAt().add(command.txnId(), command);
-        command.addListener(this);
-    }
-
-    public boolean isEmpty()
-    {
-        return byId().isEmpty();
+    public int hashCode()
+    {
+        int hash = 1;
+        hash = 31 * hash + Objects.hashCode(key);
+        hash = 31 * hash + Objects.hashCode(max);
+        hash = 31 * hash + Objects.hashCode(lastExecutedTimestamp);
+        hash = 31 * hash + Long.hashCode(lastExecutedMicros);
+        hash = 31 * hash + Objects.hashCode(lastWriteTimestamp);
+        hash = 31 * hash + byId.hashCode();
+        hash = 31 * hash + byExecuteAt.hashCode();
+        return hash;
+    }
+
+    public Key key()
+    {
+        checkCanReadFrom();
+        return key;
+    }
+
+    public Timestamp max()
+    {
+        checkCanReadFrom();
+        return max;
+    }
+
+    public Timestamp lastExecutedTimestamp()
+    {
+        return lastExecutedTimestamp;
+    }
+
+    public long lastExecutedMicros()
+    {
+        return lastExecutedMicros;
+    }
+
+    public Timestamp lastWriteTimestamp()
+    {
+        return lastWriteTimestamp;
+    }
+
+    public CommandTimeseries<?> byId()
+    {
+        return byId;
+    }
+
+    public CommandTimeseries<?> byExecuteAt()
+    {
+        return byExecuteAt;
+    }
+
+    public void forWitnessed(Timestamp minTs, Timestamp maxTs, Consumer<TxnId> consumer)
+    {
+        byId.between(minTs, maxTs, status -> status.hasBeen(PreAccepted)).forEach(consumer);
+        byExecuteAt.between(minTs, maxTs, status -> status.hasBeen(PreCommitted)).forEach(consumer);
+    }
+
+    private static long getTimestampMicros(Timestamp timestamp)
+    {
+        return timestamp.msb + timestamp.lsb;
+    }
+
+
+    private void validateExecuteAtTime(Timestamp executeAt, boolean isForWriteTxn)
+    {
+        if (executeAt.compareTo(lastWriteTimestamp) < 0)
+            throw new IllegalArgumentException(String.format("%s is less than the most recent write timestamp %s", executeAt, lastWriteTimestamp));
+
+        int cmp = executeAt.compareTo(lastExecutedTimestamp);
+        // execute can be in the past if it's for a read and after the most recent write
+        if (cmp == 0 || (!isForWriteTxn && cmp < 0))
+            return;
+        if (cmp < 0)
+            throw new IllegalArgumentException(String.format("%s is less than the most recent executed timestamp %s", executeAt, lastExecutedTimestamp));
+        else
+            throw new IllegalArgumentException(String.format("%s is greater than the most recent executed timestamp, cfk should be updated", executeAt, lastExecutedTimestamp));
+    }
+
+    public int nowInSecondsFor(Timestamp executeAt, boolean isForWriteTxn)
+    {
+        validateExecuteAtTime(executeAt, isForWriteTxn);
+        // we use the executeAt time instead of the monotonic database timestamp to prevent uneven
+        // ttl expiration in extreme cases, ie 1M+ writes/second to a key causing timestamps to overflow
+        // into the next second on some keys and not others.
+        return Math.toIntExact(TimeUnit.MICROSECONDS.toSeconds(getTimestampMicros(lastExecutedTimestamp)));
+    }
+
+    public long timestampMicrosFor(Timestamp executeAt, boolean isForWriteTxn)
+    {
+        validateExecuteAtTime(executeAt, isForWriteTxn);
+        return lastExecutedMicros;
+    }
+
+    public static class Update
+    {
+        private final SafeCommandStore safeStore;
+        private boolean completed = false;
+        private final Key key;
+        private final CommandsForKey original;
+        private Timestamp max;
+        private Timestamp lastExecutedTimestamp;
+        private long lastExecutedMicros;
+        private Timestamp lastWriteTimestamp;
+        private final CommandTimeseries.Update<?> byId;
+        private final CommandTimeseries.Update<?> byExecuteAt;
+
+        public Update(SafeCommandStore safeStore, CommandsForKey original)
+        {
+            original.checkCanUpdate();
+            this.safeStore = safeStore;
+            this.original = original;
+            this.key = original.key;
+            this.max = original.max;
+            this.lastExecutedTimestamp = original.lastExecutedTimestamp;
+            this.lastExecutedMicros = original.lastExecutedMicros;
+            this.lastWriteTimestamp = original.lastWriteTimestamp;
+            this.byId = original.byId.beginUpdate();
+            this.byExecuteAt = original.byId.beginUpdate();
+        }
+
+        private void checkNotCompleted()
+        {
+            if (completed)
+                throw new IllegalStateException(this + " has been completed");
+        }
+
+        public Key key()
+        {
+            return key;
+        }
+
+        public void updateMax(Timestamp timestamp)
+        {
+            checkNotCompleted();
+            max = Timestamp.max(max, timestamp);
+        }
+
+        public CommandTimeseries.Update<?> byId()
+        {
+            checkNotCompleted();
+            return byId;
+        }
+
+        public CommandTimeseries.Update<?> byExecuteAt()
+        {
+            checkNotCompleted();
+            return byExecuteAt;
+        }
+
+        void updateLastExecutionTimestamps(Timestamp executeAt, boolean isForWriteTxn)
+        {
+            long micros = getTimestampMicros(executeAt);
+            long lastMicros = lastExecutedMicros;
+
+            lastExecutedTimestamp = executeAt;
+            lastExecutedMicros = Math.max(micros, lastMicros + 1);
+            if (isForWriteTxn)
+                lastWriteTimestamp = executeAt;
+        }
+
+        public CommandsForKey complete()
+        {
+            checkNotCompleted();
+            CommandsForKey updated = new CommandsForKey(this);
+            if (original != null)
+                original.markSuperseded();
+            updated.markActive();
+            safeStore.completeUpdate(this, original, updated);
+            completed = true;
+            return updated;
+        }
+    }
+
+    public static CommandsForKey updateLastExecutionTimestamps(CommandsForKey current, SafeCommandStore safeStore, Timestamp executeAt, boolean isForWriteTxn)

Review Comment:
   unused?



##########
accord-core/src/main/java/accord/impl/InMemoryCommandStore.java:
##########
@@ -18,41 +18,113 @@
 
 package accord.impl;
 
+import accord.api.*;
 import accord.local.*;
-import accord.local.SyncCommandStores.SyncCommandStore; // java8 fails compilation if this is in correct position
-import accord.api.Agent;
-import accord.api.DataStore;
-import accord.api.Key;
-import accord.api.ProgressLog;
-import accord.impl.InMemoryCommandStore.SingleThread.AsyncState;
-import accord.impl.InMemoryCommandStore.Synchronized.SynchronizedState;
-import accord.local.CommandStores.RangesForEpochHolder;
 import accord.local.CommandStores.RangesForEpoch;
-import accord.impl.CommandsForKey.CommandTimeseries;
+import accord.local.CommandStores.RangesForEpochHolder;
 import accord.primitives.Timestamp;
 import accord.primitives.TxnId;
 import accord.primitives.*;
 import accord.utils.Invariants;
-import org.apache.cassandra.utils.concurrent.AsyncPromise;
-import org.apache.cassandra.utils.concurrent.Future;
+import accord.utils.async.AsyncChain;
+import accord.utils.async.AsyncChains;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
 
 import javax.annotation.Nullable;
 import java.util.*;
+import java.util.concurrent.Callable;
+import java.util.concurrent.ConcurrentLinkedQueue;
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Executors;
 import java.util.concurrent.atomic.AtomicReference;
-import java.util.function.BiFunction;
-import java.util.function.Consumer;
-import java.util.function.Function;
+import java.util.function.*;
 
-import static accord.local.SafeCommandStore.TestDep.*;
+import static accord.local.SafeCommandStore.TestDep.ANY_DEPS;
+import static accord.local.SafeCommandStore.TestDep.WITH;
 import static accord.local.SafeCommandStore.TestKind.Ws;
 import static accord.local.Status.Committed;
 import static accord.primitives.Routables.Slice.Minimal;
 
-public class InMemoryCommandStore
+public abstract class InMemoryCommandStore extends CommandStore
 {
-    public static abstract class State implements SafeCommandStore
+    private static final Logger logger = LoggerFactory.getLogger(InMemoryCommandStore.class);
+
+    public static <State extends ImmutableState, V> V withActiveState(State state, Callable<V> callable)
+    {
+        state.checkIsDormant();
+        state.markActive();
+        try
+        {
+            return callable.call();
+        }
+        catch (Exception e)
+        {
+            throw new RuntimeException(e);
+        }
+        finally
+        {
+            state.checkIsActive();
+            state.markDormant();
+        }
+    }
+
+    public static <State extends ImmutableState, V> V ensureActiveState(State state, Callable<V> callable)

Review Comment:
   This method really makes me think we need to find another solution to the stateful lifecycle of the immutable Commands. There's a *lot* of additional boiler-plate around the codebase now with these states, and they make the code harder to read and reason about.



##########
accord-core/src/main/java/accord/local/Command.java:
##########
@@ -18,1178 +18,1435 @@
 
 package accord.local;
 
-import accord.api.*;
-import accord.local.Status.Durability;
-import accord.local.Status.Known;
+import accord.api.Data;
+import accord.api.Result;
+import accord.api.RoutingKey;
+import accord.impl.CommandsForKey;
+import accord.impl.CommandsForKeys;
 import accord.primitives.*;
-import accord.primitives.Writes;
 import accord.utils.Invariants;
-import org.apache.cassandra.utils.concurrent.Future;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
-import java.util.function.Function;
-
-import static accord.local.Status.*;
-import static accord.local.Status.Known.*;
-import static accord.local.Status.Known.Done;
-import static accord.local.Status.Known.ExecuteAtOnly;
-import static accord.primitives.Route.isFullRoute;
-import static accord.utils.Utils.listOf;
-
-import javax.annotation.Nonnull;
+import accord.utils.Utils;
+import accord.utils.async.AsyncChain;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSortedMap;
+import com.google.common.collect.ImmutableSortedSet;
+
 import javax.annotation.Nullable;
+import java.util.*;
 
-import accord.api.ProgressLog.ProgressShard;
-import accord.primitives.Ranges;
-import accord.primitives.Ballot;
-import accord.primitives.PartialDeps;
-import accord.primitives.PartialTxn;
-import accord.primitives.Route;
-import accord.primitives.Timestamp;
-import accord.primitives.TxnId;
-import accord.api.Result;
-import accord.api.RoutingKey;
+import static accord.local.Status.Durability.Local;
+import static accord.local.Status.Durability.NotDurable;
+import static accord.local.Status.Known.DefinitionOnly;
+import static accord.utils.Utils.*;
+import static java.lang.String.format;
 
-import static accord.api.ProgressLog.ProgressShard.Home;
-import static accord.api.ProgressLog.ProgressShard.Local;
-import static accord.api.ProgressLog.ProgressShard.No;
-import static accord.api.ProgressLog.ProgressShard.Unsure;
-import static accord.local.Command.EnsureAction.Add;
-import static accord.local.Command.EnsureAction.Check;
-import static accord.local.Command.EnsureAction.Ignore;
-import static accord.local.Command.EnsureAction.Set;
-import static accord.local.Command.EnsureAction.TrySet;
-
-public abstract class Command implements CommandListener, BiConsumer<SafeCommandStore, CommandListener>, PreLoadContext
+public abstract class Command extends ImmutableState
 {
-    private static final Logger logger = LoggerFactory.getLogger(Command.class);
+    // sentinel value to indicate a command requested in a preexecute context was not found
+    // should not escape the safe command store
+    public static final Command EMPTY = new Command()
+    {
+        @Override public Route<?> route() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public RoutingKey progressKey() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public RoutingKey homeKey() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public TxnId txnId() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Ballot promised() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Status.Durability durability() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public ImmutableSet<CommandListener> listeners() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public SaveStatus saveStatus() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Timestamp executeAt() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Ballot accepted() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public PartialTxn partialTxn() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Nullable
+        @Override public PartialDeps partialDeps() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
 
-    public abstract TxnId txnId();
+        @Override
+        public String toString()
+        {
+            return "Command(EMPTY)";
+        }
+    };
 
-    // TODO (desirable, API consistency): should any of these calls be replaced by corresponding known() registers?
-    public boolean hasBeen(Status status)
+    static
     {
-        return status().hasBeen(status);
+        EMPTY.markInvalidated();
     }
 
-    public boolean has(Known known)
+    static PreLoadContext contextForCommand(Command command)
     {
-        return known.isSatisfiedBy(saveStatus().known);
+        Invariants.checkState(command.hasBeen(Status.PreAccepted) && command.partialTxn() != null);
+        return command instanceof PreLoadContext ? (PreLoadContext) command : PreLoadContext.contextFor(command.txnId(), command.partialTxn().keys());
     }
 
-    public boolean has(Definition definition)
+    private static Status.Durability durability(Status.Durability durability, SaveStatus status)
     {
-        return known().definition.compareTo(definition) >= 0;
+        if (status.compareTo(SaveStatus.PreApplied) >= 0 && durability == NotDurable)
+            return Local; // not necessary anywhere, but helps for logical consistency
+        return durability;
     }
 
-    public boolean has(Outcome outcome)
+    public interface CommonAttributes
     {
-        return known().outcome.compareTo(outcome) >= 0;
+        TxnId txnId();
+        Status.Durability durability();
+        RoutingKey homeKey();
+        RoutingKey progressKey();
+        Route<?> route();
+        PartialTxn partialTxn();
+        PartialDeps partialDeps();
+        ImmutableSet<CommandListener> listeners();
     }
 
-    public boolean is(Status status)
+    public static class SerializerSupport
     {
-        return status() == status;
-    }
-
-    /**
-     * homeKey is a global value that defines the home shard - the one tasked with ensuring the transaction is finished.
-     * progressKey is a local value that defines the local shard responsible for ensuring progress on the transaction.
-     * This will be homeKey if it is owned by the node, and some other key otherwise. If not the home shard, the progress
-     * shard has much weaker responsibilities, only ensuring that the home shard has durably witnessed the txnId.
-     *
-     * TODO (expected, efficiency): we probably do not want to save this on its own, as we probably want to
-     *  minimize IO interactions and discrete registers, so will likely reference commit log entries directly
-     *  At which point we may impose a requirement that only a Route can be saved, not a homeKey on its own.
-     *  Once this restriction is imposed, we no longer need to pass around Routable.Domain with TxnId.
-     */
-    public abstract RoutingKey homeKey();
-    protected abstract void setHomeKey(RoutingKey key);
-
-    public abstract RoutingKey progressKey();
-    protected abstract void setProgressKey(RoutingKey key);
-
-    /**
-     * If this is the home shard, we require that this is a Route for all states &gt; NotWitnessed;
-     * otherwise for the local progress shard this is ordinarily a PartialRoute, and for other shards this is not set,
-     * so that there is only one copy per node that can be consulted to construct the full set of involved keys.
-     *
-     * If hasBeen(Committed) this must contain the keys for both txnId.epoch and executeAt.epoch
-     */
-    public abstract @Nullable Route<?> route();
-    protected abstract void setRoute(Route<?> route);
-
-    public abstract PartialTxn partialTxn();
-    protected abstract void setPartialTxn(PartialTxn txn);
-
-    public abstract Ballot promised();
-    protected abstract void setPromised(Ballot ballot);
-
-    public abstract Ballot accepted();
-    protected abstract void setAccepted(Ballot ballot);
-
-    public abstract Timestamp executeAt();
-    protected abstract void setExecuteAt(Timestamp timestamp);
-
-    /**
-     * While !hasBeen(Committed), used only as a register for Accept state, used by Recovery
-     * If hasBeen(Committed), represents the full deps owned by this range for execution at both txnId.epoch
-     * AND executeAt.epoch so that it may be used for Recovery (which contacts only txnId.epoch topology),
-     * but also for execution.
-     */
-    public abstract PartialDeps partialDeps();
-    protected abstract void setPartialDeps(PartialDeps deps);
-
-    public abstract Writes writes();
-    protected abstract void setWrites(Writes writes);
-
-    public abstract Result result();
-    protected abstract void setResult(Result result);
-
-    public abstract SaveStatus saveStatus();
-    protected abstract void setSaveStatus(SaveStatus status);
-
-    public Status status() { return saveStatus().status; }
-    protected void setStatus(Status status) { setSaveStatus(SaveStatus.get(status, known())); }
-
-    public Known known() { return saveStatus().known; }
-
-    public abstract Durability durability();
-    public abstract void setDurability(Durability v);
+        public static Command.Listener listener(TxnId txnId)

Review Comment:
   Should this be next to Listener?



##########
accord-core/src/main/java/accord/local/Command.java:
##########
@@ -18,1178 +18,1435 @@
 
 package accord.local;
 
-import accord.api.*;
-import accord.local.Status.Durability;
-import accord.local.Status.Known;
+import accord.api.Data;
+import accord.api.Result;
+import accord.api.RoutingKey;
+import accord.impl.CommandsForKey;
+import accord.impl.CommandsForKeys;
 import accord.primitives.*;
-import accord.primitives.Writes;
 import accord.utils.Invariants;
-import org.apache.cassandra.utils.concurrent.Future;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
-import java.util.function.Function;
-
-import static accord.local.Status.*;
-import static accord.local.Status.Known.*;
-import static accord.local.Status.Known.Done;
-import static accord.local.Status.Known.ExecuteAtOnly;
-import static accord.primitives.Route.isFullRoute;
-import static accord.utils.Utils.listOf;
-
-import javax.annotation.Nonnull;
+import accord.utils.Utils;
+import accord.utils.async.AsyncChain;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSortedMap;
+import com.google.common.collect.ImmutableSortedSet;
+
 import javax.annotation.Nullable;
+import java.util.*;
 
-import accord.api.ProgressLog.ProgressShard;
-import accord.primitives.Ranges;
-import accord.primitives.Ballot;
-import accord.primitives.PartialDeps;
-import accord.primitives.PartialTxn;
-import accord.primitives.Route;
-import accord.primitives.Timestamp;
-import accord.primitives.TxnId;
-import accord.api.Result;
-import accord.api.RoutingKey;
+import static accord.local.Status.Durability.Local;
+import static accord.local.Status.Durability.NotDurable;
+import static accord.local.Status.Known.DefinitionOnly;
+import static accord.utils.Utils.*;
+import static java.lang.String.format;
 
-import static accord.api.ProgressLog.ProgressShard.Home;
-import static accord.api.ProgressLog.ProgressShard.Local;
-import static accord.api.ProgressLog.ProgressShard.No;
-import static accord.api.ProgressLog.ProgressShard.Unsure;
-import static accord.local.Command.EnsureAction.Add;
-import static accord.local.Command.EnsureAction.Check;
-import static accord.local.Command.EnsureAction.Ignore;
-import static accord.local.Command.EnsureAction.Set;
-import static accord.local.Command.EnsureAction.TrySet;
-
-public abstract class Command implements CommandListener, BiConsumer<SafeCommandStore, CommandListener>, PreLoadContext
+public abstract class Command extends ImmutableState
 {
-    private static final Logger logger = LoggerFactory.getLogger(Command.class);
+    // sentinel value to indicate a command requested in a preexecute context was not found
+    // should not escape the safe command store
+    public static final Command EMPTY = new Command()
+    {
+        @Override public Route<?> route() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public RoutingKey progressKey() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public RoutingKey homeKey() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public TxnId txnId() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Ballot promised() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Status.Durability durability() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public ImmutableSet<CommandListener> listeners() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public SaveStatus saveStatus() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Timestamp executeAt() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Ballot accepted() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public PartialTxn partialTxn() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Nullable
+        @Override public PartialDeps partialDeps() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
 
-    public abstract TxnId txnId();
+        @Override
+        public String toString()
+        {
+            return "Command(EMPTY)";
+        }
+    };
 
-    // TODO (desirable, API consistency): should any of these calls be replaced by corresponding known() registers?
-    public boolean hasBeen(Status status)
+    static
     {
-        return status().hasBeen(status);
+        EMPTY.markInvalidated();
     }
 
-    public boolean has(Known known)
+    static PreLoadContext contextForCommand(Command command)
     {
-        return known.isSatisfiedBy(saveStatus().known);
+        Invariants.checkState(command.hasBeen(Status.PreAccepted) && command.partialTxn() != null);
+        return command instanceof PreLoadContext ? (PreLoadContext) command : PreLoadContext.contextFor(command.txnId(), command.partialTxn().keys());
     }
 
-    public boolean has(Definition definition)
+    private static Status.Durability durability(Status.Durability durability, SaveStatus status)
     {
-        return known().definition.compareTo(definition) >= 0;
+        if (status.compareTo(SaveStatus.PreApplied) >= 0 && durability == NotDurable)
+            return Local; // not necessary anywhere, but helps for logical consistency
+        return durability;
     }
 
-    public boolean has(Outcome outcome)
+    public interface CommonAttributes
     {
-        return known().outcome.compareTo(outcome) >= 0;
+        TxnId txnId();
+        Status.Durability durability();
+        RoutingKey homeKey();
+        RoutingKey progressKey();
+        Route<?> route();
+        PartialTxn partialTxn();
+        PartialDeps partialDeps();
+        ImmutableSet<CommandListener> listeners();
     }
 
-    public boolean is(Status status)
+    public static class SerializerSupport
     {
-        return status() == status;
-    }
-
-    /**
-     * homeKey is a global value that defines the home shard - the one tasked with ensuring the transaction is finished.
-     * progressKey is a local value that defines the local shard responsible for ensuring progress on the transaction.
-     * This will be homeKey if it is owned by the node, and some other key otherwise. If not the home shard, the progress
-     * shard has much weaker responsibilities, only ensuring that the home shard has durably witnessed the txnId.
-     *
-     * TODO (expected, efficiency): we probably do not want to save this on its own, as we probably want to
-     *  minimize IO interactions and discrete registers, so will likely reference commit log entries directly
-     *  At which point we may impose a requirement that only a Route can be saved, not a homeKey on its own.
-     *  Once this restriction is imposed, we no longer need to pass around Routable.Domain with TxnId.
-     */
-    public abstract RoutingKey homeKey();
-    protected abstract void setHomeKey(RoutingKey key);
-
-    public abstract RoutingKey progressKey();
-    protected abstract void setProgressKey(RoutingKey key);
-
-    /**
-     * If this is the home shard, we require that this is a Route for all states &gt; NotWitnessed;
-     * otherwise for the local progress shard this is ordinarily a PartialRoute, and for other shards this is not set,
-     * so that there is only one copy per node that can be consulted to construct the full set of involved keys.
-     *
-     * If hasBeen(Committed) this must contain the keys for both txnId.epoch and executeAt.epoch
-     */
-    public abstract @Nullable Route<?> route();
-    protected abstract void setRoute(Route<?> route);
-
-    public abstract PartialTxn partialTxn();
-    protected abstract void setPartialTxn(PartialTxn txn);
-
-    public abstract Ballot promised();
-    protected abstract void setPromised(Ballot ballot);
-
-    public abstract Ballot accepted();
-    protected abstract void setAccepted(Ballot ballot);
-
-    public abstract Timestamp executeAt();
-    protected abstract void setExecuteAt(Timestamp timestamp);
-
-    /**
-     * While !hasBeen(Committed), used only as a register for Accept state, used by Recovery
-     * If hasBeen(Committed), represents the full deps owned by this range for execution at both txnId.epoch
-     * AND executeAt.epoch so that it may be used for Recovery (which contacts only txnId.epoch topology),
-     * but also for execution.
-     */
-    public abstract PartialDeps partialDeps();
-    protected abstract void setPartialDeps(PartialDeps deps);
-
-    public abstract Writes writes();
-    protected abstract void setWrites(Writes writes);
-
-    public abstract Result result();
-    protected abstract void setResult(Result result);
-
-    public abstract SaveStatus saveStatus();
-    protected abstract void setSaveStatus(SaveStatus status);
-
-    public Status status() { return saveStatus().status; }
-    protected void setStatus(Status status) { setSaveStatus(SaveStatus.get(status, known())); }
-
-    public Known known() { return saveStatus().known; }
-
-    public abstract Durability durability();
-    public abstract void setDurability(Durability v);
+        public static Command.Listener listener(TxnId txnId)
+        {
+            return new Command.Listener(txnId);
+        }
 
-    public abstract Command addListener(CommandListener listener);
-    public abstract void removeListener(CommandListener listener);
-    protected abstract void notifyListeners(SafeCommandStore safeStore);
+        public static NotWitnessed notWitnessed(CommonAttributes attributes, Ballot promised)
+        {
+            return NotWitnessed.Factory.create(attributes, promised);
+        }
 
-    protected abstract void addWaitingOnCommit(TxnId txnId);
-    protected abstract void removeWaitingOnCommit(TxnId txnId);
-    protected abstract TxnId firstWaitingOnCommit();
+        public static Preaccepted preaccepted(CommonAttributes common, Timestamp executeAt, Ballot promised)
+        {
+            return Preaccepted.Factory.create(common, executeAt, promised);
+        }
 
-    protected abstract void addWaitingOnApplyIfAbsent(TxnId txnId, Timestamp executeAt);
-    protected abstract TxnId firstWaitingOnApply(@Nullable TxnId ifExecutesBefore);
+        public static Accepted accepted(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted)
+        {
+            return Accepted.Factory.create(common, status, executeAt, promised, accepted);
+        }
 
-    protected abstract void removeWaitingOn(TxnId txnId, Timestamp executeAt);
-    protected abstract boolean isWaitingOnDependency();
+        public static Committed committed(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply)
+        {
+            return Committed.Factory.create(common, status, executeAt, promised, accepted, waitingOnCommit, waitingOnApply);
+        }
 
-    public boolean hasBeenWitnessed()
-    {
-        return partialTxn() != null;
+        public static Executed executed(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply, Writes writes, Result result)
+        {
+            return Executed.Factory.create(common, status, executeAt, promised, accepted, waitingOnCommit, waitingOnApply, writes, result);
+        }
     }
 
-    @Override
-    public Iterable<TxnId> txnIds()
+    private static SaveStatus validateCommandClass(SaveStatus status, Class<?> expected, Class<?> actual)
     {
-        return Collections.singleton(txnId());
+        if (actual != expected)
+        {
+            throw new IllegalStateException(format("Cannot instantiate %s for status %s. %s expected",
+                                                   actual.getSimpleName(), status, expected.getSimpleName()));
+        }
+        return status;
     }
 
-    @Override
-    public Seekables<?, ?> keys()
+    private static SaveStatus validateCommandClass(SaveStatus status, Class<?> klass)
     {
-        // TODO (expected, consider): when do we need this, and will it always be sufficient?
-        return partialTxn().keys();
+        switch (status)
+        {
+            case NotWitnessed:
+                return validateCommandClass(status, NotWitnessed.class, klass);
+            case PreAccepted:
+                return validateCommandClass(status, Preaccepted.class, klass);
+            case AcceptedInvalidate:
+            case AcceptedInvalidateWithDefinition:
+            case Accepted:
+            case AcceptedWithDefinition:
+                return validateCommandClass(status, Accepted.class, klass);
+            case Committed:
+            case ReadyToExecute:
+                return validateCommandClass(status, Committed.class, klass);
+            case PreApplied:
+            case Applied:
+            case Invalidated:
+                return validateCommandClass(status, Executed.class, klass);
+            default:
+                throw new IllegalStateException("Unhandled status " + status);
+        }
     }
 
-    public void setDurability(SafeCommandStore safeStore, Durability durability, RoutingKey homeKey, @Nullable Timestamp executeAt)
+    public static Command addListener(SafeCommandStore safeStore, Command command, CommandListener listener)
     {
-        updateHomeKey(safeStore, homeKey);
-        if (executeAt != null && hasBeen(PreCommitted) && !this.executeAt().equals(executeAt))
-            safeStore.agent().onInconsistentTimestamp(this, this.executeAt(), executeAt);
-        setDurability(durability);
+        return safeStore.beginUpdate(command).addListener(listener).updateAttributes();
     }
 
-    public enum AcceptOutcome
+    public static Command removeListener(SafeCommandStore safeStore, Command command, CommandListener listener)
     {
-        Success, Redundant, RejectedBallot
+        return safeStore.beginUpdate(command).removeListener(listener).updateAttributes();
     }
 
-    public AcceptOutcome preaccept(SafeCommandStore safeStore, PartialTxn partialTxn, Route<?> route, @Nullable RoutingKey progressKey)
+    public static Committed updateWaitingOn(SafeCommandStore safeStore, Committed command, WaitingOn.Update waitingOn)
     {
-        return preacceptOrRecover(safeStore, partialTxn, route, progressKey, Ballot.ZERO);
+        if (!waitingOn.hasChanges())
+            return command;
+
+        Update update = safeStore.beginUpdate(command);
+        Committed updated =  command instanceof Executed ?
+                Executed.Factory.update(command.asExecuted(), update, waitingOn.build()) :
+                Committed.Factory.update(command, update, waitingOn.build());
+        return update.complete(updated);
     }
 
-    public AcceptOutcome recover(SafeCommandStore safeStore, PartialTxn partialTxn, Route<?> route, @Nullable RoutingKey progressKey, Ballot ballot)
+    public static class Listener implements CommandListener
     {
-        return preacceptOrRecover(safeStore, partialTxn, route, progressKey, ballot);
-    }
+        protected final TxnId listenerId;
 
-    private AcceptOutcome preacceptOrRecover(SafeCommandStore safeStore, PartialTxn partialTxn, Route<?> route, @Nullable RoutingKey progressKey, Ballot ballot)
-    {
-        int compareBallots = promised().compareTo(ballot);
-        if (compareBallots > 0)
+        private Listener(TxnId listenerId)
         {
-            logger.trace("{}: skipping preaccept - higher ballot witnessed ({})", txnId(), promised());
-            return AcceptOutcome.RejectedBallot;
+            this.listenerId = listenerId;
         }
-        else if (compareBallots < 0)
+
+        @Override
+        public boolean equals(Object o)
         {
-            // save the new ballot as a promise
-            setPromised(ballot);
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+            Listener that = (Listener) o;
+            return listenerId.equals(that.listenerId);
         }
 
-        if (known().definition.isKnown())
+        @Override
+        public int hashCode()
         {
-            Invariants.checkState(status() == Invalidated || executeAt() != null);
-            logger.trace("{}: skipping preaccept - already known ({})", txnId(), status());
-            // in case of Ballot.ZERO, we must either have a competing recovery coordinator or have late delivery of the
-            // preaccept; in the former case we should abandon coordination, and in the latter we have already completed
-            return ballot.equals(Ballot.ZERO) ? AcceptOutcome.Redundant : AcceptOutcome.Success;
+            return Objects.hash(listenerId);
         }
 
-        Ranges coordinateRanges = coordinateRanges(safeStore);
-        Invariants.checkState(!coordinateRanges.isEmpty());
-        ProgressShard shard = progressShard(safeStore, route, progressKey, coordinateRanges);
-        if (!validate(Ranges.EMPTY, coordinateRanges, shard, route, Set, partialTxn, Set, null, Ignore))
-            throw new IllegalStateException();
-
-        if (executeAt() == null)
+        @Override
+        public String toString()
         {
-            TxnId txnId = txnId();
-            // unlike in the Accord paper, we partition shards within a node, so that to ensure a total order we must either:
-            //  - use a global logical clock to issue new timestamps; or
-            //  - assign each shard _and_ process a unique id, and use both as components of the timestamp
-            // if we are performing recovery (i.e. non-zero ballot), do not permit a fast path decision as we want to
-            // invalidate any transactions that were not completed by their initial coordinator
-            if (ballot.equals(Ballot.ZERO)) setExecuteAt(safeStore.preaccept(txnId, partialTxn.keys()));
-            else setExecuteAt(safeStore.time().uniqueNow(txnId));
+            return "ListenerProxy{" + listenerId + '}';
+        }
 
-            if (status() == NotWitnessed)
-                setStatus(PreAccepted);
-            safeStore.progressLog().preaccepted(this, shard);
+        public TxnId txnId()
+        {
+            return listenerId;
         }
-        else
+
+        @Override
+        public void onChange(SafeCommandStore safeStore, TxnId txnId)
         {
-            // TODO (expected, ?): in the case that we are pre-committed but had not been preaccepted/accepted, should we inform progressLog?
-            setSaveStatus(SaveStatus.enrich(saveStatus(), DefinitionOnly));
+            Commands.listenerUpdate(safeStore, safeStore.command(listenerId), safeStore.command(txnId));
         }
-        set(safeStore, Ranges.EMPTY, coordinateRanges, shard, route, partialTxn, Set, null, Ignore);
 
-        notifyListeners(safeStore);
-        return AcceptOutcome.Success;
+        @Override
+        public PreLoadContext listenerPreLoadContext(TxnId caller)
+        {
+            return PreLoadContext.contextFor(Utils.listOf(listenerId, caller), Keys.EMPTY);
+        }
     }
 
-    public boolean preacceptInvalidate(Ballot ballot)
+    public static CommandListener listener(TxnId txnId)
     {
-        if (promised().compareTo(ballot) > 0)
-        {
-            logger.trace("{}: skipping preacceptInvalidate - witnessed higher ballot ({})", txnId(), promised());
-            return false;
-        }
-        setPromised(ballot);
-        return true;
+        return new Listener(txnId);
     }
 
-    public AcceptOutcome accept(SafeCommandStore safeStore, Ballot ballot, PartialRoute<?> route, Seekables<?, ?> keys, @Nullable RoutingKey progressKey, Timestamp executeAt, PartialDeps partialDeps)
+    private abstract static class AbstractCommand extends Command
     {
-        if (this.promised().compareTo(ballot) > 0)
+        private final TxnId txnId;
+        private final SaveStatus status;
+        private final Status.Durability durability;
+        private final RoutingKey homeKey;
+        private final RoutingKey progressKey;
+        private final Route<?> route;
+        private final Ballot promised;
+        private final ImmutableSet<CommandListener> listeners;
+
+        private AbstractCommand(TxnId txnId, SaveStatus status, Status.Durability durability, RoutingKey homeKey, RoutingKey progressKey, Route<?> route, Ballot promised, ImmutableSet<CommandListener> listeners)
         {
-            logger.trace("{}: skipping accept - witnessed higher ballot ({} > {})", txnId(), promised(), ballot);
-            return AcceptOutcome.RejectedBallot;
+            this.txnId = txnId;
+            this.status = validateCommandClass(status, getClass());
+            this.durability = durability;
+            this.homeKey = homeKey;
+            this.progressKey = progressKey;
+            this.route = route;
+            this.promised = promised;
+            this.listeners = listeners;
         }
 
-        if (hasBeen(PreCommitted))
+        private AbstractCommand(CommonAttributes common, SaveStatus status, Ballot promised)
         {
-            logger.trace("{}: skipping accept - already committed ({})", txnId(), status());
-            return AcceptOutcome.Redundant;
+            this.txnId = common.txnId();
+            this.status = validateCommandClass(status, getClass());
+            this.durability = common.durability();
+            this.homeKey = common.homeKey();
+            this.progressKey = common.progressKey();
+            this.route = common.route();
+            this.promised = promised;
+            this.listeners = common.listeners();
         }
 
-        TxnId txnId = txnId();
-        Ranges coordinateRanges = coordinateRanges(safeStore);
-        Ranges acceptRanges = txnId.epoch() == executeAt.epoch() ? coordinateRanges : safeStore.ranges().between(txnId.epoch(), executeAt.epoch());
-        Invariants.checkState(!acceptRanges.isEmpty());
-        ProgressShard shard = progressShard(safeStore, route, progressKey, coordinateRanges);
-
-        if (!validate(coordinateRanges, Ranges.EMPTY, shard, route, Ignore, null, Ignore, partialDeps, Set))
-            throw new AssertionError("Invalid response from validate function");
-
-        setExecuteAt(executeAt);
-        setPromised(ballot);
-        setAccepted(ballot);
-
-        // TODO (desired, clarity/efficiency): we don't need to set the route here, and perhaps we don't even need to
-        //  distributed partialDeps at all, since all we gain is not waiting for these transactions to commit during
-        //  recovery. We probably don't want to directly persist a Route in any other circumstances, either, to ease persistence.
-        set(safeStore, coordinateRanges, acceptRanges, shard, route, null, Ignore, partialDeps, Set);
+        @Override
+        public boolean equals(Object o)
+        {
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+            Command command = (Command) o;
+            return txnId.equals(command.txnId())
+                    && status == command.saveStatus()
+                    && durability == command.durability()
+                    && Objects.equals(homeKey, command.homeKey())
+                    && Objects.equals(progressKey, command.progressKey())
+                    && Objects.equals(route, command.route())
+                    && Objects.equals(promised, command.promised())
+                    && listeners.equals(command.listeners());
+        }
 
-        // set only registers by transaction keys, which we mightn't already have received
-        if (!known().isDefinitionKnown())
-            safeStore.register(keys, acceptRanges, this);
+        @Override
+        public String toString()
+        {
+            return "Command@" + System.identityHashCode(this) + '{' + txnId + ':' + status + '}';
+        }
 
-        setStatus(Accepted);
-        safeStore.progressLog().accepted(this, shard);
-        notifyListeners(safeStore);
+        @Override
+        public int hashCode()
+        {
+            int hash = 1;
+            hash = 31 * hash + txnId.hashCode();
+            hash = 31 * hash + status.hashCode();
+            hash = 31 * hash + Objects.hashCode(durability);
+            hash = 31 * hash + Objects.hashCode(homeKey);
+            hash = 31 * hash + Objects.hashCode(progressKey);
+            hash = 31 * hash + Objects.hashCode(route);
+            hash = 31 * hash + Objects.hashCode(promised);
+            hash = 31 * hash + Objects.hashCode(listeners);
+            return hash;
+        }
 
-        return AcceptOutcome.Success;
-    }
+        @Override
+        public TxnId txnId()
+        {
+            return txnId;
+        }
 
-    public AcceptOutcome acceptInvalidate(SafeCommandStore safeStore, Ballot ballot)
-    {
-        if (this.promised().compareTo(ballot) > 0)
+        @Override
+        public final RoutingKey homeKey()
         {
-            logger.trace("{}: skipping accept invalidated - witnessed higher ballot ({} > {})", txnId(), promised(), ballot);
-            return AcceptOutcome.RejectedBallot;
+            checkCanReadFrom();
+            return homeKey;
         }
 
-        if (hasBeen(PreCommitted))
+        @Override
+        public final RoutingKey progressKey()
         {
-            logger.trace("{}: skipping accept invalidated - already committed ({})", txnId(), status());
-            return AcceptOutcome.Redundant;
+            checkCanReadFrom();
+            return progressKey;
         }
 
-        setPromised(ballot);
-        setAccepted(ballot);
-        setStatus(AcceptedInvalidate);
-        setPartialDeps(null);
-        logger.trace("{}: accepted invalidated", txnId());
+        @Override
+        public final Route<?> route()
+        {
+            checkCanReadFrom();
+            return route;
+        }
 
-        notifyListeners(safeStore);
-        return AcceptOutcome.Success;
-    }
+        @Override
+        public Ballot promised()
+        {
+            checkCanReadFrom();
+            return promised;
+        }
 
-    public enum CommitOutcome { Success, Redundant, Insufficient }
+        @Override
+        public Status.Durability durability()
+        {
+            checkCanReadFrom();
+            return Command.durability(durability, saveStatus());
+        }
 
-    // relies on mutual exclusion for each key
-    public CommitOutcome commit(SafeCommandStore safeStore, Route<?> route, @Nullable RoutingKey progressKey, @Nullable PartialTxn partialTxn, Timestamp executeAt, PartialDeps partialDeps)
-    {
-        if (hasBeen(PreCommitted))
+        @Override
+        public ImmutableSet<CommandListener> listeners()
         {
-            logger.trace("{}: skipping commit - already committed ({})", txnId(), status());
-            if (!executeAt.equals(executeAt()) || status() == Invalidated)
-                safeStore.agent().onInconsistentTimestamp(this, (status() == Invalidated ? Timestamp.NONE : this.executeAt()), executeAt);
+            checkCanReadFrom();
+            if (listeners == null)
+                return ImmutableSet.of();
+            return listeners;
+        }
 
-            if (hasBeen(Committed))
-                return CommitOutcome.Redundant;
+        @Override
+        public final SaveStatus saveStatus()
+        {
+            checkCanReadFrom();
+            return status;
         }
+    }
+
+    /**
+     * If this is the home shard, we require that this is a Route for all states &gt; NotWitnessed;
+     * otherwise for the local progress shard this is ordinarily a PartialRoute, and for other shards this is not set,
+     * so that there is only one copy per node that can be consulted to construct the full set of involved keys.
+     *
+     * If hasBeen(Committed) this must contain the keys for both txnId.epoch and executeAt.epoch
+     */
+    public abstract Route<?> route();
+    public abstract RoutingKey progressKey();
 
-        Ranges coordinateRanges = coordinateRanges(safeStore);
-        // TODO (expected, consider): consider ranges between coordinateRanges and executeRanges? Perhaps don't need them
-        Ranges executeRanges = executeRanges(safeStore, executeAt);
-        ProgressShard shard = progressShard(safeStore, route, progressKey, coordinateRanges);
+    /**
+     * homeKey is a global value that defines the home shard - the one tasked with ensuring the transaction is finished.
+     * progressKey is a local value that defines the local shard responsible for ensuring progress on the transaction.
+     * This will be homeKey if it is owned by the node, and some other key otherwise. If not the home shard, the progress
+     * shard has much weaker responsibilities, only ensuring that the home shard has durably witnessed the txnId.
+     *
+     * TODO (expected, efficiency): we probably do not want to save this on its own, as we probably want to
+     *  minimize IO interactions and discrete registers, so will likely reference commit log entries directly
+     *  At which point we may impose a requirement that only a Route can be saved, not a homeKey on its own.
+     *  Once this restriction is imposed, we no longer need to pass around Routable.Domain with TxnId.
+     */
+    public abstract RoutingKey homeKey();
+    public abstract TxnId txnId();
+    public abstract Ballot promised();
+    public abstract Status.Durability durability();
+    public abstract ImmutableSet<CommandListener> listeners();
+    public abstract SaveStatus saveStatus();
 
-        if (!validate(coordinateRanges, executeRanges, shard, route, Check, partialTxn, Add, partialDeps, Set))
-            return CommitOutcome.Insufficient;
+    private static boolean isSameClass(Command command, Class<? extends Command> klass)
+    {
+        return command.getClass() == klass;
+    }
 
-        setExecuteAt(executeAt);
-        set(safeStore, coordinateRanges, executeRanges, shard, route, partialTxn, Add, partialDeps, Set);
+    private static void checkNewBallot(Ballot current, Ballot next, String name)
+    {
+        if (next.compareTo(current) < 0)
+            throw new IllegalArgumentException(String.format("Cannot update %s ballot from %s to %s. New ballot is less than current", name, current, next));
+    }
 
-        setStatus(Committed);
-        logger.trace("{}: committed with executeAt: {}, deps: {}", txnId(), executeAt, partialDeps);
-        populateWaitingOn(safeStore);
+    private static void checkPromised(Command command, Ballot ballot)
+    {
+        checkNewBallot(command.promised(), ballot, "promised");
+    }
 
-        safeStore.progressLog().committed(this, shard);
+    private static void checkAccepted(Command command, Ballot ballot)
+    {
+        checkNewBallot(command.accepted(), ballot, "accepted");
+    }
 
-        // TODO (expected, safety): introduce intermediate status to avoid reentry when notifying listeners (which might notify us)
-        maybeExecute(safeStore, shard, true, true);
-        return CommitOutcome.Success;
+    private static void checkSameClass(Command command, Class<? extends Command> klass, String errorMsg)
+    {
+        if (!isSameClass(command, klass))
+            throw new IllegalArgumentException(errorMsg + format(" expected %s got %s", klass.getSimpleName(), command.getClass().getSimpleName()));
     }
 
-    // relies on mutual exclusion for each key
-    public void precommit(SafeCommandStore safeStore, Timestamp executeAt)
+    // TODO (low priority, progress): callers should try to consult the local progress shard (if any) to obtain the full set of keys owned locally
+    public final Route<?> someRoute()
     {
-        if (hasBeen(PreCommitted))
-        {
-            logger.trace("{}: skipping precommit - already committed ({})", txnId(), status());
-            if (executeAt.equals(executeAt()) && status() != Invalidated)
-                return;
+        checkCanReadFrom();
+        if (route() != null)
+            return route();
 
-            safeStore.agent().onInconsistentTimestamp(this, (status() == Invalidated ? Timestamp.NONE : this.executeAt()), executeAt);
-        }
+        if (homeKey() != null)
+            return PartialRoute.empty(txnId().domain(), homeKey());
 
-        setExecuteAt(executeAt);
-        setStatus(PreCommitted);
-        notifyListeners(safeStore);
-        logger.trace("{}: precommitted with executeAt: {}", txnId(), executeAt);
+        return null;
     }
 
-    protected void populateWaitingOn(SafeCommandStore safeStore)
+    public Unseekables<?, ?> maxUnseekables()
     {
-        Ranges ranges = safeStore.ranges().since(executeAt().epoch());
-        if (ranges != null)
-        {
-            partialDeps().forEach(ranges, txnId -> {
-                Command command = safeStore.ifLoaded(txnId);
-                if (command == null)
-                {
-                    addWaitingOnCommit(txnId);
-                    safeStore.addAndInvokeListener(txnId, this);
-                }
-                else
-                {
-                    switch (command.status())
-                    {
-                        default:
-                            throw new IllegalStateException();
-                        case NotWitnessed:
-                        case PreAccepted:
-                        case Accepted:
-                        case AcceptedInvalidate:
-                            // we don't know when these dependencies will execute, and cannot execute until we do
-                            command.addListener(this);
-                            addWaitingOnCommit(command.txnId());
-                            break;
-                        case PreCommitted:
-                        case Committed:
-                            // TODO (desired, efficiency): split into ReadyToRead and ReadyToWrite;
-                            //                             the distributed read can be performed as soon as those keys are ready,
-                            //                             and in parallel with any other reads. the client can even ACK immediately after;
-                            //                             only the write needs to be postponed until other in-progress reads complete
-                        case ReadyToExecute:
-                        case PreApplied:
-                        case Applied:
-                            command.addListener(this);
-                            insertPredecessor(command);
-                        case Invalidated:
-                            break;
-                    }
-                }
-            });
-        }
+        Route<?> route = someRoute();
+        if (route == null)
+            return null;
+
+        return route.toMaximalUnseekables();
     }
 
-    // TODO (expected, ?): commitInvalidate may need to update cfks _if_ possible
-    public void commitInvalidate(SafeCommandStore safeStore)
+    public PreLoadContext contextForSelf()
     {
-        if (hasBeen(PreCommitted))
-        {
-            logger.trace("{}: skipping commit invalidated - already committed ({})", txnId(), status());
-            if (!hasBeen(Invalidated))
-                safeStore.agent().onInconsistentTimestamp(this, Timestamp.NONE, executeAt());
-
-            return;
-        }
+        checkCanReadFrom();
+        return contextForCommand(this);
+    }
 
-        ProgressShard shard = progressShard(safeStore);
-        safeStore.progressLog().invalidated(this, shard);
-        setExecuteAt(txnId());
-        if (partialDeps() == null)
-            setPartialDeps(PartialDeps.NONE);
-        setStatus(Invalidated);
-        logger.trace("{}: committed invalidated", txnId());
+    public abstract Timestamp executeAt();
+    public abstract Ballot accepted();
+    public abstract PartialTxn partialTxn();
+    public abstract @Nullable PartialDeps partialDeps();
 
-        notifyListeners(safeStore);
+    public final Status status()
+    {
+        checkCanReadFrom();
+        return saveStatus().status;
     }
 
-    public enum ApplyOutcome { Success, Redundant, Insufficient }
+    public final Status.Known known()
+    {
+        checkCanReadFrom();
+        return saveStatus().known;
+    }
 
-    public ApplyOutcome apply(SafeCommandStore safeStore, long untilEpoch, Route<?> route, Timestamp executeAt, @Nullable PartialDeps partialDeps, Writes writes, Result result)
+    public boolean hasBeenWitnessed()
     {
-        if (hasBeen(PreApplied) && executeAt.equals(this.executeAt()))
-        {
-            logger.trace("{}: skipping apply - already executed ({})", txnId(), status());
-            return ApplyOutcome.Redundant;
-        }
-        else if (hasBeen(PreCommitted) && !executeAt.equals(this.executeAt()))
-        {
-            safeStore.agent().onInconsistentTimestamp(this, this.executeAt(), executeAt);
-        }
+        checkCanReadFrom();
+        return partialTxn() != null;
+    }
 
-        Ranges coordinateRanges = coordinateRanges(safeStore);
-        Ranges executeRanges = executeRanges(safeStore, executeAt);
-        if (untilEpoch < safeStore.latestEpoch())
-        {
-            Ranges expectedRanges = safeStore.ranges().between(executeAt.epoch(), untilEpoch);
-            Invariants.checkState(expectedRanges.containsAll(executeRanges));
-        }
-        ProgressShard shard = progressShard(safeStore, route, coordinateRanges);
+    public final boolean hasBeen(Status status)
+    {
+        return status().compareTo(status) >= 0;
+    }
 
-        if (!validate(coordinateRanges, executeRanges, shard, route, Check, null, Check, partialDeps, hasBeen(Committed) ? Add : TrySet))
-            return ApplyOutcome.Insufficient; // TODO (expected, consider): this should probably be an assertion failure if !TrySet
+    public boolean has(Status.Known known)
+    {
+        return known.isSatisfiedBy(saveStatus().known);
+    }
 
-        setWrites(writes);
-        setResult(result);
-        setExecuteAt(executeAt);
-        set(safeStore, coordinateRanges, executeRanges, shard, route, null, Check, partialDeps, hasBeen(Committed) ? Add : TrySet);
+    public boolean has(Status.Definition definition)
+    {
+        return known().definition.compareTo(definition) >= 0;
+    }
 
-        if (!hasBeen(Committed))
-            populateWaitingOn(safeStore);
-        setStatus(PreApplied);
-        logger.trace("{}: apply, status set to Executed with executeAt: {}, deps: {}", txnId(), executeAt, partialDeps);
+    public boolean has(Status.Outcome outcome)
+    {
+        return known().outcome.compareTo(outcome) >= 0;
+    }
 
-        safeStore.progressLog().executed(this, shard);
+    public boolean is(Status status)
+    {
+        return status() == status;
+    }
 
-        maybeExecute(safeStore, shard, true, true);
-        return ApplyOutcome.Success;
+    public final CommandListener asListener()
+    {
+        return listener(txnId());
     }
 
-    @Override
-    public PreLoadContext listenerPreLoadContext(TxnId caller)
+    public final boolean isWitnessed()
     {
-        return PreLoadContext.contextFor(listOf(txnId(), caller));
+        checkCanReadFrom();
+        boolean result = status().hasBeen(Status.PreAccepted);
+        Invariants.checkState(result == (this instanceof Preaccepted));
+        return result;
     }
 
-    @Override
-    public void onChange(SafeCommandStore safeStore, Command command)
+    public final Preaccepted asWitnessed()
     {
-        logger.trace("{}: updating as listener in response to change on {} with status {} ({})",
-                     txnId(), command.txnId(), command.status(), command);
-        switch (command.status())
-        {
-            default:
-                throw new IllegalStateException();
-            case NotWitnessed:
-            case PreAccepted:
-            case Accepted:
-            case AcceptedInvalidate:
-                break;
+        checkCanReadFrom();
+        return (Preaccepted) this;
+    }
 
-            case PreCommitted:
-            case Committed:
-            case ReadyToExecute:
-            case PreApplied:
-            case Applied:
-            case Invalidated:
-                updatePredecessor(command);
-                maybeExecute(safeStore, progressShard(safeStore), false, true);
-                break;
-        }
+    public final boolean isAccepted()
+    {
+        checkCanReadFrom();
+        boolean result = status().hasBeen(Status.AcceptedInvalidate);
+        Invariants.checkState(result == (this instanceof Accepted));
+        return result;
     }
 
-    protected void postApply(SafeCommandStore safeStore)
+    public final Accepted asAccepted()
     {
-        logger.trace("{} applied, setting status to Applied and notifying listeners", txnId());
-        setStatus(Applied);
-        notifyListeners(safeStore);
+        checkCanReadFrom();
+        return (Accepted) this;
     }
 
-    private static Function<SafeCommandStore, Void> callPostApply(TxnId txnId)
+    public final boolean isCommitted()
     {
-        return safeStore -> {
-            safeStore.command(txnId).postApply(safeStore);
-            return null;
-        };
+        checkCanReadFrom();
+        boolean result = status().hasBeen(Status.Committed);
+        Invariants.checkState(result == (this instanceof Committed));
+        return result;
     }
 
-    protected Future<Void> apply(SafeCommandStore safeStore)
+    public final Committed asCommitted()
     {
-        // important: we can't include a reference to *this* in the lambda, since the C* implementation may evict
-        // the command instance from memory between now and the write completing (and post apply being called)
-        CommandStore unsafeStore = safeStore.commandStore();
-        return writes().apply(safeStore).flatMap(unused ->
-            unsafeStore.submit(this, callPostApply(txnId()))
-        );
+        checkCanReadFrom();
+        return (Committed) this;
     }
 
-    public Future<Data> read(SafeCommandStore safeStore)
+    public final boolean isExecuted()
     {
-        return partialTxn().read(safeStore, this);
+        checkCanReadFrom();
+        boolean result = status().hasBeen(Status.PreApplied);
+        Invariants.checkState(result == (this instanceof Executed));
+        return result;
     }
 
-    // TODO (expected, API consistency): maybe split into maybeExecute and maybeApply?
-    private boolean maybeExecute(SafeCommandStore safeStore, ProgressShard shard, boolean alwaysNotifyListeners, boolean notifyWaitingOn)
+    public final Executed asExecuted()
     {
-        if (logger.isTraceEnabled())
-            logger.trace("{}: Maybe executing with status {}. Will notify listeners on noop: {}", txnId(), status(), alwaysNotifyListeners);
+        checkCanReadFrom();
+        return (Executed) this;
+    }
 
-        if (status() != Committed && status() != PreApplied)
+    public static final class NotWitnessed extends AbstractCommand
+    {
+        NotWitnessed(TxnId txnId, SaveStatus status, Status.Durability durability, RoutingKey homeKey, RoutingKey progressKey, Route<?> route, Ballot promised, ImmutableSet<CommandListener> listeners)
         {
-            if (alwaysNotifyListeners)
-                notifyListeners(safeStore);
-            return false;
+            super(txnId, status, durability, homeKey, progressKey, route, promised, listeners);
         }
 
-        if (isWaitingOnDependency())
+        NotWitnessed(CommonAttributes common, SaveStatus status, Ballot promised)
         {
-            if (alwaysNotifyListeners)
-                notifyListeners(safeStore);
-
-            if (notifyWaitingOn)
-                new NotifyWaitingOn(this).accept(safeStore);
-            return false;
+            super(common, status, promised);
         }
 
-        switch (status())
+        public static NotWitnessed create(TxnId txnId)
         {
-            case Committed:
-                // TODO (desirable, efficiency): maintain distinct ReadyToRead and ReadyToWrite states
-                setStatus(ReadyToExecute);
-                logger.trace("{}: set to ReadyToExecute", txnId());
-                safeStore.progressLog().readyToExecute(this, shard);
-                notifyListeners(safeStore);
-                break;
+            return new NotWitnessed(txnId, SaveStatus.NotWitnessed, NotDurable, null, null, null, Ballot.ZERO, null);
+        }
 
-            case PreApplied:
-                Ranges executeRanges = executeRanges(safeStore, executeAt());
-                boolean intersects = writes().keys.intersects(executeRanges);
+        private static class Factory
+        {
+            public static NotWitnessed create(CommonAttributes common, Ballot promised)
+            {
+                return new NotWitnessed(common, SaveStatus.NotWitnessed, promised);
+            }
 
-                if (intersects)
-                {
-                    logger.trace("{}: applying", txnId());
-                    apply(safeStore);
-                }
-                else
-                {
-                    // TODO (desirable, performance): This could be performed immediately upon Committed
-                    //      but: if we later support transitive dependency elision this could be dangerous
-                    logger.trace("{}: applying no-op", txnId());
-                    setStatus(Applied);
-                    notifyListeners(safeStore);
-                }
+            public static NotWitnessed update(NotWitnessed command, CommonAttributes common, Ballot promised)
+            {
+                checkSameClass(command, NotWitnessed.class, "Cannot update");
+                command.checkCanReadFrom();
+                Invariants.checkArgument(command.txnId().equals(common.txnId()));
+                return new NotWitnessed(common, command.saveStatus(), promised);
+            }
         }
-        return true;
-    }
 
-    /**
-     * @param dependency is either committed or invalidated
-     * @return true iff {@code maybeExecute} might now have a different outcome
-     */
-    private boolean updatePredecessor(Command dependency)
-    {
-        Invariants.checkState(dependency.hasBeen(PreCommitted));
-        if (dependency.hasBeen(Invalidated))
+        @Override
+        public Timestamp executeAt()
         {
-            logger.trace("{}: {} is invalidated. Stop listening and removing from waiting on commit set.", txnId(), dependency.txnId());
-            dependency.removeListener(this);
-            removeWaitingOnCommit(dependency.txnId());
-            return true;
+            checkCanReadFrom();
+            return null;
         }
-        else if (dependency.executeAt().compareTo(executeAt()) > 0)
+
+        @Override
+        public Ballot promised()
         {
-            // dependency cannot be a predecessor if it executes later
-            logger.trace("{}: {} executes after us. Stop listening and removing from waiting on apply set.", txnId(), dependency.txnId());
-            removeWaitingOn(dependency.txnId(), dependency.executeAt());
-            dependency.removeListener(this);
-            return true;
+            checkCanReadFrom();
+            return Ballot.ZERO;
         }
-        else if (dependency.hasBeen(Applied))
+
+        @Override
+        public Ballot accepted()
         {
-            logger.trace("{}: {} has been applied. Stop listening and removing from waiting on apply set.", txnId(), dependency.txnId());
-            removeWaitingOn(dependency.txnId(), dependency.executeAt());
-            dependency.removeListener(this);
-            return true;
+            checkCanReadFrom();
+            return Ballot.ZERO;
         }
-        else if (isWaitingOnDependency())
+
+        @Override
+        public PartialTxn partialTxn()
         {
-            logger.trace("{}: adding {} to waiting on apply set.", txnId(), dependency.txnId());
-            addWaitingOnApplyIfAbsent(dependency.txnId(), dependency.executeAt());
-            removeWaitingOnCommit(dependency.txnId());
-            return false;
+            checkCanReadFrom();
+            return null;
         }
-        else
+
+        @Override
+        public @Nullable PartialDeps partialDeps()
         {
-            throw new IllegalStateException();
+            checkCanReadFrom();
+            return null;
         }
     }
 
-    private void insertPredecessor(Command dependency)
+    public static class Preaccepted extends AbstractCommand
     {
-        Invariants.checkState(dependency.hasBeen(PreCommitted));
-        if (dependency.hasBeen(Invalidated))
+        private final Timestamp executeAt;
+        private final PartialTxn partialTxn;
+        private final @Nullable PartialDeps partialDeps;
+
+        private Preaccepted(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised)
+        {
+            super(common, status, promised);
+            this.executeAt = executeAt;
+            this.partialTxn = common.partialTxn();
+            this.partialDeps = common.partialDeps();
+        }
+
+        @Override
+        public boolean equals(Object o)
+        {
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+            if (!super.equals(o)) return false;
+            Preaccepted that = (Preaccepted) o;
+            return executeAt.equals(that.executeAt)
+                    && Objects.equals(partialTxn, that.partialTxn)
+                    && Objects.equals(partialDeps, that.partialDeps);
+        }
+
+        @Override
+        public int hashCode()
         {
-            logger.trace("{}: {} is invalidated. Do not insert.", txnId(), dependency.txnId());
+            int hash = super.hashCode();
+            hash = 31 * hash + Objects.hashCode(executeAt);
+            hash = 31 * hash + Objects.hashCode(partialTxn);
+            hash = 31 * hash + Objects.hashCode(partialDeps);
+            return hash;
         }
-        else if (dependency.executeAt().compareTo(executeAt()) > 0)
+
+        private static class Factory
         {
-            // dependency cannot be a predecessor if it executes later
-            logger.trace("{}: {} executes after us. Do not insert.", txnId(), dependency.txnId());
+            public static Preaccepted create(CommonAttributes common, Timestamp executeAt, Ballot promised)
+            {
+                return new Preaccepted(common, SaveStatus.PreAccepted, executeAt, promised);
+            }
+
+            public static Preaccepted update(Preaccepted command, CommonAttributes common, Ballot promised)
+            {
+                checkPromised(command, promised);
+                checkSameClass(command, Preaccepted.class, "Cannot update");
+                Invariants.checkArgument(command.getClass() == Preaccepted.class);
+                command.checkCanReadFrom();
+                return create(common, command.executeAt(), promised);
+            }
         }
-        else if (dependency.hasBeen(Applied))
+
+        @Override
+        public Timestamp executeAt()
         {
-            logger.trace("{}: {} has been applied. Do not insert.", txnId(), dependency.txnId());
+            checkCanReadFrom();
+            return executeAt;
         }
-        else
+
+        @Override
+        public Ballot accepted()
         {
-            logger.trace("{}: adding {} to waiting on apply set.", txnId(), dependency.txnId());
-            addWaitingOnApplyIfAbsent(dependency.txnId(), dependency.executeAt());
+            checkCanReadFrom();
+            return Ballot.ZERO;
         }
-    }
 
-    void updatePredecessorAndMaybeExecute(SafeCommandStore safeStore, Command predecessor, boolean notifyWaitingOn)
-    {
-        if (hasBeen(Applied))
-            return;
+        @Override
+        public PartialTxn partialTxn()
+        {
+            checkCanReadFrom();
+            return partialTxn;
+        }
 
-        if (updatePredecessor(predecessor))
-            maybeExecute(safeStore, progressShard(safeStore), false, notifyWaitingOn);
+        @Override
+        public @Nullable PartialDeps partialDeps()
+        {
+            checkCanReadFrom();
+            return partialDeps;
+        }
     }
 
-    static class NotifyWaitingOn implements PreLoadContext, Consumer<SafeCommandStore>
+    public static class Accepted extends Preaccepted
     {
-        Known[] blockedUntil = new Known[4];
-        TxnId[] txnIds = new TxnId[4];
-        int depth;
+        private final Ballot accepted;
 
-        public NotifyWaitingOn(Command command)
+        private Accepted(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted)
+        {
+            super(common, status, executeAt, promised);
+            this.accepted = accepted;
+        }
+
+        @Override
+        public boolean equals(Object o)
         {
-            txnIds[0] = command.txnId();
-            blockedUntil[0] = Done;
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+            if (!super.equals(o)) return false;
+            Accepted that = (Accepted) o;
+            return Objects.equals(accepted, that.accepted);
         }
 
         @Override
-        public void accept(SafeCommandStore safeStore)
+        public int hashCode()
         {
-            Command prev = get(safeStore, depth - 1);
-            while (depth >= 0)
+            int hash = super.hashCode();
+            hash = 31 * hash + Objects.hashCode(accepted);
+            return hash;
+        }
+
+        private static class Factory
+        {
+            static Accepted create(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted)
             {
-                Command cur = safeStore.ifLoaded(txnIds[depth]);
-                Known until = blockedUntil[depth];
-                if (cur == null)
-                {
-                    // need to load; schedule execution for later
-                    safeStore.execute(this, this);
-                    return;
-                }
+                return new Accepted(common, status, executeAt, promised, accepted);
+            }
 
-                if (prev != null)
-                {
-                    if (cur.has(until) || (cur.hasBeen(PreCommitted) && cur.executeAt().compareTo(prev.executeAt()) > 0))
-                    {
-                        prev.updatePredecessorAndMaybeExecute(safeStore, cur, false);
-                        --depth;
-                        prev = get(safeStore, depth - 1);
-                        continue;
-                    }
-                }
-                else if (cur.has(until))
-                {
-                    // we're done; have already applied
-                    Invariants.checkState(depth == 0);
-                    break;
-                }
+            static Accepted update(Accepted command, CommonAttributes common, SaveStatus status, Ballot promised)
+            {
+                checkPromised(command, promised);
+                checkSameClass(command, Accepted.class, "Cannot update");
+                command.checkCanUpdate();
+                return new Accepted(common, status, command.executeAt(), promised, command.accepted());
+            }
 
-                TxnId directlyBlockedOnCommit = cur.firstWaitingOnCommit();
-                TxnId directlyBlockedOnApply = cur.firstWaitingOnApply(directlyBlockedOnCommit);
-                if (directlyBlockedOnApply != null)
-                {
-                    push(directlyBlockedOnApply, Done);
-                }
-                else if (directlyBlockedOnCommit != null)
-                {
-                    push(directlyBlockedOnCommit, ExecuteAtOnly);
-                }
-                else
-                {
-                    if (cur.hasBeen(Committed) && !cur.hasBeen(ReadyToExecute) && !cur.isWaitingOnDependency())
-                    {
-                        if (!cur.maybeExecute(safeStore, cur.progressShard(safeStore), false, false))
-                            throw new AssertionError("Is able to Apply, but has not done so");
-                        // loop and re-test the command's status; we may still want to notify blocking, esp. if not homeShard
-                        continue;
-                    }
-
-                    Unseekables<?, ?> someKeys = cur.maxUnseekables();
-                    if (someKeys == null && prev != null) someKeys = prev.partialDeps().someUnseekables(cur.txnId());
-                    Invariants.checkState(someKeys != null);
-                    logger.trace("{} blocked on {} until {}", txnIds[0], cur.txnId(), until);
-                    safeStore.progressLog().waiting(cur.txnId(), until, someKeys);
-                    return;
-                }
-                prev = cur;
+            static Accepted update(Accepted command, CommonAttributes common, Ballot promised)
+            {
+                return update(command, common, command.saveStatus(), promised);
             }
         }
 
-        private Command get(SafeCommandStore safeStore, int i)
+        @Override
+        public Ballot accepted()
         {
-            return i >= 0 ? safeStore.command(txnIds[i]) : null;
+            checkCanReadFrom();
+            return accepted;
         }
+    }
 
-        void push(TxnId by, Known until)
+    public static class Committed extends Accepted
+    {
+        private final ImmutableSortedSet<TxnId> waitingOnCommit;
+        private final ImmutableSortedMap<Timestamp, TxnId> waitingOnApply;
+
+        private Committed(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply)
         {
-            if (++depth == txnIds.length)
-            {
-                txnIds = Arrays.copyOf(txnIds, txnIds.length * 2);
-                blockedUntil = Arrays.copyOf(blockedUntil, txnIds.length);
-            }
-            txnIds[depth] = by;
-            blockedUntil[depth] = until;
+            super(common, status, executeAt, promised, accepted);
+            this.waitingOnCommit = waitingOnCommit;
+            this.waitingOnApply = waitingOnApply;
+        }
+
+        private Committed(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, WaitingOn waitingOn)
+        {
+            this(common, status, executeAt, promised, accepted, waitingOn.waitingOnCommit, waitingOn.waitingOnApply);
         }
 
         @Override
-        public Iterable<TxnId> txnIds()
+        public boolean equals(Object o)
         {
-            return Arrays.asList(txnIds).subList(0, depth + 1);
+            if (this == o) return true;
+            if (o == null || getClass() != o.getClass()) return false;
+            if (!super.equals(o)) return false;
+            Committed committed = (Committed) o;
+            return Objects.equals(waitingOnCommit, committed.waitingOnCommit)
+                    && Objects.equals(waitingOnApply, committed.waitingOnApply);
         }
 
         @Override
-        public Seekables<?, ?> keys()
+        public int hashCode()
         {
-            return Keys.EMPTY;
+            int hash = super.hashCode();
+            hash = 31 * hash + Objects.hashCode(waitingOnCommit);
+            hash = 31 * hash + Objects.hashCode(waitingOnApply);
+            return hash;
         }
-    }
 
-    /**
-     * A key nominated to represent the "home" shard - only members of the home shard may be nominated to recover
-     * a transaction, to reduce the cluster-wide overhead of ensuring progress. A transaction that has only been
-     * witnessed at PreAccept may however trigger a process of ensuring the home shard is durably informed of
-     * the transaction.
-     *
-     * Note that for ProgressLog purposes the "home shard" is the shard as of txnId.epoch.
-     * For recovery purposes the "home shard" is as of txnId.epoch until Committed, and executeAt.epoch once Executed
-     */
-    public final void homeKey(RoutingKey homeKey)
-    {
-        RoutingKey current = homeKey();
-        if (current == null) setHomeKey(homeKey);
-        else if (!current.equals(homeKey)) throw new AssertionError();
-    }
+        private static class Factory

Review Comment:
   Do we need to use factories here? These objects are immutable and we don't accept any user-provided objects I don't think, so it is probably cleaner to just have either static or instance methods that advance the state machine? They could be public or package private.
   
   This also avoids the need to unpack sets into mutable ones, then repack them into immutable ones, halving the cost (which is a very large percentage of time spent on the trace that David shared with us privately)



##########
accord-core/src/main/java/accord/local/Command.java:
##########
@@ -18,1178 +18,1435 @@
 
 package accord.local;
 
-import accord.api.*;
-import accord.local.Status.Durability;
-import accord.local.Status.Known;
+import accord.api.Data;
+import accord.api.Result;
+import accord.api.RoutingKey;
+import accord.impl.CommandsForKey;
+import accord.impl.CommandsForKeys;
 import accord.primitives.*;
-import accord.primitives.Writes;
 import accord.utils.Invariants;
-import org.apache.cassandra.utils.concurrent.Future;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
-import java.util.function.Function;
-
-import static accord.local.Status.*;
-import static accord.local.Status.Known.*;
-import static accord.local.Status.Known.Done;
-import static accord.local.Status.Known.ExecuteAtOnly;
-import static accord.primitives.Route.isFullRoute;
-import static accord.utils.Utils.listOf;
-
-import javax.annotation.Nonnull;
+import accord.utils.Utils;
+import accord.utils.async.AsyncChain;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSortedMap;
+import com.google.common.collect.ImmutableSortedSet;
+
 import javax.annotation.Nullable;
+import java.util.*;
 
-import accord.api.ProgressLog.ProgressShard;
-import accord.primitives.Ranges;
-import accord.primitives.Ballot;
-import accord.primitives.PartialDeps;
-import accord.primitives.PartialTxn;
-import accord.primitives.Route;
-import accord.primitives.Timestamp;
-import accord.primitives.TxnId;
-import accord.api.Result;
-import accord.api.RoutingKey;
+import static accord.local.Status.Durability.Local;
+import static accord.local.Status.Durability.NotDurable;
+import static accord.local.Status.Known.DefinitionOnly;
+import static accord.utils.Utils.*;
+import static java.lang.String.format;
 
-import static accord.api.ProgressLog.ProgressShard.Home;
-import static accord.api.ProgressLog.ProgressShard.Local;
-import static accord.api.ProgressLog.ProgressShard.No;
-import static accord.api.ProgressLog.ProgressShard.Unsure;
-import static accord.local.Command.EnsureAction.Add;
-import static accord.local.Command.EnsureAction.Check;
-import static accord.local.Command.EnsureAction.Ignore;
-import static accord.local.Command.EnsureAction.Set;
-import static accord.local.Command.EnsureAction.TrySet;
-
-public abstract class Command implements CommandListener, BiConsumer<SafeCommandStore, CommandListener>, PreLoadContext
+public abstract class Command extends ImmutableState
 {
-    private static final Logger logger = LoggerFactory.getLogger(Command.class);
+    // sentinel value to indicate a command requested in a preexecute context was not found
+    // should not escape the safe command store
+    public static final Command EMPTY = new Command()
+    {
+        @Override public Route<?> route() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public RoutingKey progressKey() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public RoutingKey homeKey() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public TxnId txnId() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Ballot promised() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Status.Durability durability() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public ImmutableSet<CommandListener> listeners() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public SaveStatus saveStatus() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Timestamp executeAt() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Ballot accepted() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public PartialTxn partialTxn() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Nullable
+        @Override public PartialDeps partialDeps() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
 
-    public abstract TxnId txnId();
+        @Override
+        public String toString()
+        {
+            return "Command(EMPTY)";
+        }
+    };
 
-    // TODO (desirable, API consistency): should any of these calls be replaced by corresponding known() registers?
-    public boolean hasBeen(Status status)
+    static
     {
-        return status().hasBeen(status);
+        EMPTY.markInvalidated();
     }
 
-    public boolean has(Known known)
+    static PreLoadContext contextForCommand(Command command)
     {
-        return known.isSatisfiedBy(saveStatus().known);
+        Invariants.checkState(command.hasBeen(Status.PreAccepted) && command.partialTxn() != null);
+        return command instanceof PreLoadContext ? (PreLoadContext) command : PreLoadContext.contextFor(command.txnId(), command.partialTxn().keys());
     }
 
-    public boolean has(Definition definition)
+    private static Status.Durability durability(Status.Durability durability, SaveStatus status)
     {
-        return known().definition.compareTo(definition) >= 0;
+        if (status.compareTo(SaveStatus.PreApplied) >= 0 && durability == NotDurable)
+            return Local; // not necessary anywhere, but helps for logical consistency
+        return durability;
     }
 
-    public boolean has(Outcome outcome)
+    public interface CommonAttributes

Review Comment:
   Should this extend `Command`, or to extract a common interface?



##########
accord-core/src/main/java/accord/local/Commands.java:
##########
@@ -0,0 +1,1073 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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 accord.local;
+
+import accord.api.ProgressLog.ProgressShard;
+import accord.api.Result;
+import accord.api.RoutingKey;
+import accord.local.Command.WaitingOn;
+import accord.primitives.*;
+import accord.utils.Invariants;
+import accord.utils.async.AsyncChain;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import javax.annotation.Nonnull;
+import javax.annotation.Nullable;
+
+import java.util.Arrays;
+import java.util.Map;
+import java.util.function.Consumer;
+import java.util.function.Function;
+
+import static accord.api.ProgressLog.ProgressShard.*;
+import static accord.api.ProgressLog.ProgressShard.Local;
+import static accord.local.Commands.EnsureAction.*;
+import static accord.local.Status.*;
+import static accord.local.Status.Known.ExecuteAtOnly;
+import static accord.primitives.Route.isFullRoute;
+
+public class Commands

Review Comment:
   Is it definitely clearer to have this in a separate class to Command?



##########
accord-core/src/main/java/accord/local/Command.java:
##########
@@ -18,1178 +18,1435 @@
 
 package accord.local;
 
-import accord.api.*;
-import accord.local.Status.Durability;
-import accord.local.Status.Known;
+import accord.api.Data;
+import accord.api.Result;
+import accord.api.RoutingKey;
+import accord.impl.CommandsForKey;
+import accord.impl.CommandsForKeys;
 import accord.primitives.*;
-import accord.primitives.Writes;
 import accord.utils.Invariants;
-import org.apache.cassandra.utils.concurrent.Future;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
-import java.util.function.Function;
-
-import static accord.local.Status.*;
-import static accord.local.Status.Known.*;
-import static accord.local.Status.Known.Done;
-import static accord.local.Status.Known.ExecuteAtOnly;
-import static accord.primitives.Route.isFullRoute;
-import static accord.utils.Utils.listOf;
-
-import javax.annotation.Nonnull;
+import accord.utils.Utils;
+import accord.utils.async.AsyncChain;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSortedMap;
+import com.google.common.collect.ImmutableSortedSet;
+
 import javax.annotation.Nullable;
+import java.util.*;
 
-import accord.api.ProgressLog.ProgressShard;
-import accord.primitives.Ranges;
-import accord.primitives.Ballot;
-import accord.primitives.PartialDeps;
-import accord.primitives.PartialTxn;
-import accord.primitives.Route;
-import accord.primitives.Timestamp;
-import accord.primitives.TxnId;
-import accord.api.Result;
-import accord.api.RoutingKey;
+import static accord.local.Status.Durability.Local;
+import static accord.local.Status.Durability.NotDurable;
+import static accord.local.Status.Known.DefinitionOnly;
+import static accord.utils.Utils.*;
+import static java.lang.String.format;
 
-import static accord.api.ProgressLog.ProgressShard.Home;
-import static accord.api.ProgressLog.ProgressShard.Local;
-import static accord.api.ProgressLog.ProgressShard.No;
-import static accord.api.ProgressLog.ProgressShard.Unsure;
-import static accord.local.Command.EnsureAction.Add;
-import static accord.local.Command.EnsureAction.Check;
-import static accord.local.Command.EnsureAction.Ignore;
-import static accord.local.Command.EnsureAction.Set;
-import static accord.local.Command.EnsureAction.TrySet;
-
-public abstract class Command implements CommandListener, BiConsumer<SafeCommandStore, CommandListener>, PreLoadContext
+public abstract class Command extends ImmutableState
 {
-    private static final Logger logger = LoggerFactory.getLogger(Command.class);
+    // sentinel value to indicate a command requested in a preexecute context was not found
+    // should not escape the safe command store
+    public static final Command EMPTY = new Command()
+    {
+        @Override public Route<?> route() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public RoutingKey progressKey() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public RoutingKey homeKey() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public TxnId txnId() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Ballot promised() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Status.Durability durability() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public ImmutableSet<CommandListener> listeners() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public SaveStatus saveStatus() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Timestamp executeAt() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public Ballot accepted() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Override public PartialTxn partialTxn() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
+        @Nullable
+        @Override public PartialDeps partialDeps() { throw new IllegalStateException("Attempting to access EMPTY sentinel values"); }
 
-    public abstract TxnId txnId();
+        @Override
+        public String toString()
+        {
+            return "Command(EMPTY)";
+        }
+    };
 
-    // TODO (desirable, API consistency): should any of these calls be replaced by corresponding known() registers?
-    public boolean hasBeen(Status status)
+    static
     {
-        return status().hasBeen(status);
+        EMPTY.markInvalidated();
     }
 
-    public boolean has(Known known)
+    static PreLoadContext contextForCommand(Command command)
     {
-        return known.isSatisfiedBy(saveStatus().known);
+        Invariants.checkState(command.hasBeen(Status.PreAccepted) && command.partialTxn() != null);
+        return command instanceof PreLoadContext ? (PreLoadContext) command : PreLoadContext.contextFor(command.txnId(), command.partialTxn().keys());
     }
 
-    public boolean has(Definition definition)
+    private static Status.Durability durability(Status.Durability durability, SaveStatus status)
     {
-        return known().definition.compareTo(definition) >= 0;
+        if (status.compareTo(SaveStatus.PreApplied) >= 0 && durability == NotDurable)
+            return Local; // not necessary anywhere, but helps for logical consistency
+        return durability;
     }
 
-    public boolean has(Outcome outcome)
+    public interface CommonAttributes
     {
-        return known().outcome.compareTo(outcome) >= 0;
+        TxnId txnId();
+        Status.Durability durability();
+        RoutingKey homeKey();
+        RoutingKey progressKey();
+        Route<?> route();
+        PartialTxn partialTxn();
+        PartialDeps partialDeps();
+        ImmutableSet<CommandListener> listeners();
     }
 
-    public boolean is(Status status)
+    public static class SerializerSupport
     {
-        return status() == status;
-    }
-
-    /**
-     * homeKey is a global value that defines the home shard - the one tasked with ensuring the transaction is finished.
-     * progressKey is a local value that defines the local shard responsible for ensuring progress on the transaction.
-     * This will be homeKey if it is owned by the node, and some other key otherwise. If not the home shard, the progress
-     * shard has much weaker responsibilities, only ensuring that the home shard has durably witnessed the txnId.
-     *
-     * TODO (expected, efficiency): we probably do not want to save this on its own, as we probably want to
-     *  minimize IO interactions and discrete registers, so will likely reference commit log entries directly
-     *  At which point we may impose a requirement that only a Route can be saved, not a homeKey on its own.
-     *  Once this restriction is imposed, we no longer need to pass around Routable.Domain with TxnId.
-     */
-    public abstract RoutingKey homeKey();
-    protected abstract void setHomeKey(RoutingKey key);
-
-    public abstract RoutingKey progressKey();
-    protected abstract void setProgressKey(RoutingKey key);
-
-    /**
-     * If this is the home shard, we require that this is a Route for all states &gt; NotWitnessed;
-     * otherwise for the local progress shard this is ordinarily a PartialRoute, and for other shards this is not set,
-     * so that there is only one copy per node that can be consulted to construct the full set of involved keys.
-     *
-     * If hasBeen(Committed) this must contain the keys for both txnId.epoch and executeAt.epoch
-     */
-    public abstract @Nullable Route<?> route();
-    protected abstract void setRoute(Route<?> route);
-
-    public abstract PartialTxn partialTxn();
-    protected abstract void setPartialTxn(PartialTxn txn);
-
-    public abstract Ballot promised();
-    protected abstract void setPromised(Ballot ballot);
-
-    public abstract Ballot accepted();
-    protected abstract void setAccepted(Ballot ballot);
-
-    public abstract Timestamp executeAt();
-    protected abstract void setExecuteAt(Timestamp timestamp);
-
-    /**
-     * While !hasBeen(Committed), used only as a register for Accept state, used by Recovery
-     * If hasBeen(Committed), represents the full deps owned by this range for execution at both txnId.epoch
-     * AND executeAt.epoch so that it may be used for Recovery (which contacts only txnId.epoch topology),
-     * but also for execution.
-     */
-    public abstract PartialDeps partialDeps();
-    protected abstract void setPartialDeps(PartialDeps deps);
-
-    public abstract Writes writes();
-    protected abstract void setWrites(Writes writes);
-
-    public abstract Result result();
-    protected abstract void setResult(Result result);
-
-    public abstract SaveStatus saveStatus();
-    protected abstract void setSaveStatus(SaveStatus status);
-
-    public Status status() { return saveStatus().status; }
-    protected void setStatus(Status status) { setSaveStatus(SaveStatus.get(status, known())); }
-
-    public Known known() { return saveStatus().known; }
-
-    public abstract Durability durability();
-    public abstract void setDurability(Durability v);
+        public static Command.Listener listener(TxnId txnId)
+        {
+            return new Command.Listener(txnId);
+        }
 
-    public abstract Command addListener(CommandListener listener);
-    public abstract void removeListener(CommandListener listener);
-    protected abstract void notifyListeners(SafeCommandStore safeStore);
+        public static NotWitnessed notWitnessed(CommonAttributes attributes, Ballot promised)
+        {
+            return NotWitnessed.Factory.create(attributes, promised);
+        }
 
-    protected abstract void addWaitingOnCommit(TxnId txnId);
-    protected abstract void removeWaitingOnCommit(TxnId txnId);
-    protected abstract TxnId firstWaitingOnCommit();
+        public static Preaccepted preaccepted(CommonAttributes common, Timestamp executeAt, Ballot promised)
+        {
+            return Preaccepted.Factory.create(common, executeAt, promised);
+        }
 
-    protected abstract void addWaitingOnApplyIfAbsent(TxnId txnId, Timestamp executeAt);
-    protected abstract TxnId firstWaitingOnApply(@Nullable TxnId ifExecutesBefore);
+        public static Accepted accepted(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted)
+        {
+            return Accepted.Factory.create(common, status, executeAt, promised, accepted);
+        }
 
-    protected abstract void removeWaitingOn(TxnId txnId, Timestamp executeAt);
-    protected abstract boolean isWaitingOnDependency();
+        public static Committed committed(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply)
+        {
+            return Committed.Factory.create(common, status, executeAt, promised, accepted, waitingOnCommit, waitingOnApply);
+        }
 
-    public boolean hasBeenWitnessed()
-    {
-        return partialTxn() != null;
+        public static Executed executed(CommonAttributes common, SaveStatus status, Timestamp executeAt, Ballot promised, Ballot accepted, ImmutableSortedSet<TxnId> waitingOnCommit, ImmutableSortedMap<Timestamp, TxnId> waitingOnApply, Writes writes, Result result)
+        {
+            return Executed.Factory.create(common, status, executeAt, promised, accepted, waitingOnCommit, waitingOnApply, writes, result);
+        }
     }
 
-    @Override
-    public Iterable<TxnId> txnIds()
+    private static SaveStatus validateCommandClass(SaveStatus status, Class<?> expected, Class<?> actual)
     {
-        return Collections.singleton(txnId());
+        if (actual != expected)
+        {
+            throw new IllegalStateException(format("Cannot instantiate %s for status %s. %s expected",
+                                                   actual.getSimpleName(), status, expected.getSimpleName()));
+        }
+        return status;
     }
 
-    @Override
-    public Seekables<?, ?> keys()
+    private static SaveStatus validateCommandClass(SaveStatus status, Class<?> klass)
     {
-        // TODO (expected, consider): when do we need this, and will it always be sufficient?
-        return partialTxn().keys();
+        switch (status)
+        {
+            case NotWitnessed:
+                return validateCommandClass(status, NotWitnessed.class, klass);
+            case PreAccepted:
+                return validateCommandClass(status, Preaccepted.class, klass);
+            case AcceptedInvalidate:
+            case AcceptedInvalidateWithDefinition:
+            case Accepted:
+            case AcceptedWithDefinition:
+                return validateCommandClass(status, Accepted.class, klass);
+            case Committed:
+            case ReadyToExecute:
+                return validateCommandClass(status, Committed.class, klass);
+            case PreApplied:
+            case Applied:
+            case Invalidated:
+                return validateCommandClass(status, Executed.class, klass);
+            default:
+                throw new IllegalStateException("Unhandled status " + status);
+        }
     }
 
-    public void setDurability(SafeCommandStore safeStore, Durability durability, RoutingKey homeKey, @Nullable Timestamp executeAt)
+    public static Command addListener(SafeCommandStore safeStore, Command command, CommandListener listener)

Review Comment:
   Since preparing this feedback, I've seen David's traces that show this alone accounting for 7% of cpu time, where as much as 24% of cpu time is also spent on logging (so if we exclude that, we're at around 10% of cpu time). So I think we need to address this, but perhaps it can be in follow-up work, and perhaps this will be ameliorated once we elide transitive dependencies. We might also be able to move listener registration to `NotifyWaitingOn` so that we only register them on demand (saving some wasted work), or else elide transitive dependencies at registration time. Or all of the above.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: pr-unsubscribe@cassandra.apache.org
For additional commands, e-mail: pr-help@cassandra.apache.org