diff --git a/src/scheduler.h b/src/scheduler.h
--- a/src/scheduler.h
+++ b/src/scheduler.h
@@ -90,9 +90,13 @@
 
 /**
  * Class used by CScheduler clients which may schedule multiple jobs
- * which are required to be run serially. Does not require such jobs
- * to be executed on the same thread, but no two jobs will be executed
- * at the same time.
+ * which are required to be run serially. Jobs may not be run on the
+ * same thread, but no two jobs will be executed
+ * at the same time and memory will be release-acquire consistent
+ * (the scheduler will internally do an acquire before invoking a callback
+ * as well as a release at the end). In practice this means that a callback
+ * B() will be able to observe all of the effects of callback A() which executed
+ * before it.
  */
 class SingleThreadedSchedulerClient {
 private:
@@ -109,6 +113,13 @@
 public:
     explicit SingleThreadedSchedulerClient(CScheduler *pschedulerIn)
         : m_pscheduler(pschedulerIn) {}
+
+    /**
+     * Add a callback to be executed. Callbacks are executed serially
+     * and memory is sequentially consistent between callback executions.
+     * Practially, this means that callbacks can behave as if they are executed
+     * in order by a single thread.
+     */
     void AddToProcessQueue(std::function<void()> func);
 
     // Processes all remaining queue members on the calling thread, blocking
diff --git a/src/test/scheduler_tests.cpp b/src/test/scheduler_tests.cpp
--- a/src/test/scheduler_tests.cpp
+++ b/src/test/scheduler_tests.cpp
@@ -66,7 +66,7 @@
     size_t nTasks = microTasks.getQueueInfo(first, last);
     BOOST_CHECK(nTasks == 0);
 
-    for (int i = 0; i < 100; i++) {
+    for (int i = 0; i < 100; ++i) {
         boost::chrono::system_clock::time_point t =
             now + boost::chrono::microseconds(randomMsec(rng));
         boost::chrono::system_clock::time_point tReschedule =
@@ -174,4 +174,47 @@
     BOOST_CHECK_EQUAL(counter, 42);
 }
 
+BOOST_AUTO_TEST_CASE(singlethreadedscheduler_ordered) {
+    CScheduler scheduler;
+
+    // each queue should be well ordered with respect to itself but not other
+    // queues
+    SingleThreadedSchedulerClient queue1(&scheduler);
+    SingleThreadedSchedulerClient queue2(&scheduler);
+
+    // create more threads than queues
+    // if the queues only permit execution of one task at once then
+    // the extra threads should effectively be doing nothing
+    // if they don't we'll get out of order behaviour
+    boost::thread_group threads;
+    for (int i = 0; i < 5; ++i) {
+        threads.create_thread(
+            boost::bind(&CScheduler::serviceQueue, &scheduler));
+    }
+
+    // these are not atomic, if SinglethreadedSchedulerClient prevents
+    // parallel execution at the queue level no synchronization should be
+    // required here
+    int counter1 = 0;
+    int counter2 = 0;
+
+    // just simply count up on each queue - if execution is properly ordered
+    // then the callbacks should run in exactly the order in which they were
+    // enqueued
+    for (int i = 0; i < 100; ++i) {
+        queue1.AddToProcessQueue(
+            [i, &counter1]() { BOOST_CHECK_EQUAL(i, counter1++); });
+
+        queue2.AddToProcessQueue(
+            [i, &counter2]() { BOOST_CHECK_EQUAL(i, counter2++); });
+    }
+
+    // finish up
+    scheduler.stop(true);
+    threads.join_all();
+
+    BOOST_CHECK_EQUAL(counter1, 100);
+    BOOST_CHECK_EQUAL(counter2, 100);
+}
+
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/validationinterface.h b/src/validationinterface.h
--- a/src/validationinterface.h
+++ b/src/validationinterface.h
@@ -53,6 +53,21 @@
  */
 void SyncWithValidationInterfaceQueue();
 
+/**
+ * Implement this to subscribe to events generated in validation
+ *
+ * Each CValidationInterface() subscriber will receive event callbacks
+ * in the order in which the events were generated by validation.
+ * Furthermore, each ValidationInterface() subscriber may assume that
+ * callbacks effectively run in a single thread with single-threaded
+ * memory consistency. That is, for a given ValidationInterface()
+ * instantiation, each callback will complete before the next one is
+ * invoked. This means, for example when a block is connected that the
+ * UpdatedBlockTip() callback may depend on an operation performed in
+ * the BlockConnected() callback without worrying about explicit
+ * synchronization. No ordering should be assumed across
+ * ValidationInterface() subscribers.
+ */
 class CValidationInterface {
 protected:
     /**