move parent selection to PaceMaker

7 files changed, 76 insertions, 49 deletions

diff --git a/TODO.rst b/TODO.rst
index b9d7020..e9e67ea 100644
--- a/TODO.rst
+++ b/TODO.rst
@@ -1 +1 @@
-- leave parent selection to PaceMaker
+- Implement a basic long-standing leader PaceMaker
diff --git a/include/hotstuff/consensus.h b/include/hotstuff/consensus.h
index cb18db5..73d47ef 100644
--- a/include/hotstuff/consensus.h
+++ b/include/hotstuff/consensus.h
@@ -40,14 +40,11 @@ class HotStuffCore {
 
     protected:
     ReplicaID id;                  /**< identity of the replica itself */
-    const int32_t parent_limit;         /**< maximum number of parents */
 
     public:
     BoxObj<EntityStorage> storage;
 
-    HotStuffCore(ReplicaID id,
-                privkey_bt &&priv_key,
-                int32_t parent_limit);
+    HotStuffCore(ReplicaID id, privkey_bt &&priv_key);
     virtual ~HotStuffCore() = default;
 
     /* Inputs of the state machine triggered by external events, should called
@@ -73,8 +70,11 @@ class HotStuffCore {
      * The block mentioned in the message should be already delivered. */
     void on_receive_vote(const Vote &vote);
 
-    /** Call to submit new commands to be decided (executed). */
-    void on_propose(const std::vector<command_t> &cmds);
+    /** Call to submit new commands to be decided (executed). "Parents" must
+     * contain at least one block, and the first block is the actual parent,
+     * while the others are uncles/aunts */
+    void on_propose(const std::vector<command_t> &cmds,
+                    const std::vector<block_t> &parents);
 
     /* Functions required to construct concrete instances for abstract classes.
      * */
@@ -127,6 +127,7 @@ class HotStuffCore {
     const ReplicaConfig &get_config() { return config; }
     int8_t get_cmd_decision(const uint256_t &cmd_hash);
     ReplicaID get_id() const { return id; }
+    const std::set<block_t, BlockHeightCmp> get_tails() const { return tails; }
     operator std::string () const;
 };
 
diff --git a/include/hotstuff/hotstuff.h b/include/hotstuff/hotstuff.h
index 9d1a8a8..0aa83de 100644
--- a/include/hotstuff/hotstuff.h
+++ b/include/hotstuff/hotstuff.h
@@ -157,12 +157,11 @@ class HotStuffBase: public HotStuffCore {
 
     public:
     HotStuffBase(uint32_t blk_size,
-            int32_t parent_limit,
             ReplicaID rid,
             privkey_bt &&priv_key,
             NetAddr listen_addr,
-            EventContext eb,
-            pacemaker_bt pmaker);
+            pacemaker_bt pmaker,
+            EventContext eb);
 
     ~HotStuffBase();
 
@@ -220,19 +219,17 @@ class HotStuff: public HotStuffBase {
 
     public:
     HotStuff(uint32_t blk_size,
-            int32_t parent_limit,
             ReplicaID rid,
             const bytearray_t &raw_privkey,
             NetAddr listen_addr,
-            EventContext eb = EventContext(),
-            pacemaker_bt pmaker = new PaceMakerDummy()):
+            pacemaker_bt pmaker,
+            EventContext eb = EventContext()):
         HotStuffBase(blk_size,
-                    parent_limit,
                     rid,
                     new PrivKeyType(raw_privkey),
                     listen_addr,
-                    eb,
-                    std::move(pmaker)) {}
+                    std::move(pmaker),
+                    eb) {}
 
     void add_replica(ReplicaID idx, const NetAddr &addr, const bytearray_t &pubkey_raw) {
         DataStream s(pubkey_raw);
diff --git a/include/hotstuff/liveness.h b/include/hotstuff/liveness.h
index b23d4c2..a51c032 100644
--- a/include/hotstuff/liveness.h
+++ b/include/hotstuff/liveness.h
@@ -17,6 +17,7 @@ class PaceMaker {
      * propose the command. */
     virtual promise_t beat() = 0;
     virtual ReplicaID get_proposer() = 0;
+    virtual std::vector<block_t> get_parents() = 0;
     /** Get a promise resolved when the pace maker thinks it is a *good* time
      * to vote for a block. The promise is resolved with the next proposer's ID
      * */
@@ -25,8 +26,31 @@ class PaceMaker {
 
 using pacemaker_bt = BoxObj<PaceMaker>;
 
-/** A pace maker that waits for the qc of the last proposed block. */
-class PaceMakerDummy: public PaceMaker {
+class PMAllParents: public virtual PaceMaker {
+    const int32_t parent_limit;         /**< maximum number of parents */
+    public:
+    PMAllParents(int32_t parent_limit): parent_limit(parent_limit) {}
+    std::vector<block_t> get_parents() override {
+        auto tails = hsc->get_tails();
+        size_t nparents = tails.size();
+        if (parent_limit > 0)
+            nparents = std::min(nparents, (size_t)parent_limit);
+        assert(nparents > 0);
+        block_t p = *tails.rbegin();
+        std::vector<block_t> parents{p};
+        nparents--;
+        /* add the rest of tails as "uncles/aunts" */
+        while (nparents--)
+        {
+            auto it = tails.begin();
+            parents.push_back(*it);
+            tails.erase(it);
+        }
+        return std::move(parents);
+    }
+};
+
+class PMWaitQC: public virtual PaceMaker {
     std::queue<promise_t> pending_beats;
     block_t last_proposed;
     bool locked;
@@ -53,8 +77,6 @@ class PaceMakerDummy: public PaceMaker {
     }
 
     public:
-    PaceMakerDummy() = default;
-
     void init(HotStuffCore *hsc) override {
         PaceMaker::init(hsc);
         last_proposed = hsc->get_genesis();
@@ -80,16 +102,25 @@ class PaceMakerDummy: public PaceMaker {
     }
 };
 
+/** A pace maker that waits for the qc of the last proposed block. */
+struct PaceMakerDummy: public PMAllParents, public PMWaitQC {
+    PaceMakerDummy(int32_t parent_limit):
+        PMAllParents(parent_limit), PMWaitQC() {}
+};
+
 class PaceMakerDummyFixed: public PaceMakerDummy {
     ReplicaID proposer;
 
     public:
+    PaceMakerDummyFixed(ReplicaID proposer,
+                        int32_t parent_limit):
+        PaceMakerDummy(parent_limit),
+        proposer(proposer) {}
+
     ReplicaID get_proposer() override {
         return proposer;
     }
 
-    PaceMakerDummyFixed(ReplicaID proposer): proposer(proposer) {}
-
     promise_t next_proposer(ReplicaID) override {
         return promise_t([this](promise_t &pm) {
             pm.resolve(proposer);
diff --git a/src/consensus.cpp b/src/consensus.cpp
index e42fb49..688c450 100644
--- a/src/consensus.cpp
+++ b/src/consensus.cpp
@@ -10,11 +10,10 @@
 
 namespace hotstuff {
 
-/* The core logic of HotStuff, is farily simple :) */
+/* The core logic of HotStuff, is fairly simple :). */
 /*** begin HotStuff protocol logic ***/
 HotStuffCore::HotStuffCore(ReplicaID id,
-                            privkey_bt &&priv_key,
-                            int32_t parent_limit):
+                            privkey_bt &&priv_key):
         b0(new Block(true, 1)),
         bqc(b0),
         bexec(b0),
@@ -22,7 +21,6 @@ HotStuffCore::HotStuffCore(ReplicaID id,
         priv_key(std::move(priv_key)),
         tails{bqc},
         id(id),
-        parent_limit(parent_limit),
         storage(new EntityStorage()) {
     storage->add_blk(b0);
     b0->qc_ref = b0;
@@ -110,20 +108,12 @@ bool HotStuffCore::update(const uint256_t &bqc_hash) {
     return true;
 }
 
-void HotStuffCore::on_propose(const std::vector<command_t> &cmds) {
-    size_t nparents = parent_limit < 1 ? tails.size() : parent_limit;
-    assert(tails.size() > 0);
-    block_t p = *tails.rbegin();
-    std::vector<block_t> parents{p};
-    tails.erase(p);
-    nparents--;
-    /* add the rest of tails as "uncles/aunts" */
-    while (nparents--)
-    {
-        auto it = tails.begin();
-        parents.push_back(*it);
-        tails.erase(it);
-    }
+void HotStuffCore::on_propose(const std::vector<command_t> &cmds,
+                            const std::vector<block_t> &parents) {
+    if (parents.empty())
+        throw std::runtime_error("empty parents");
+    for (const auto &_: parents) tails.erase(_);
+    block_t p = parents[0];
     quorum_cert_bt qc = nullptr;
     block_t qc_ref = nullptr;
     if (p != b0 && p->voted.size() >= config.nmajority)
@@ -211,7 +201,13 @@ void HotStuffCore::on_receive_vote(const Vote &vote) {
     size_t qsize = blk->voted.size();
     if (qsize <= config.nmajority)
     {
-        blk->self_qc->add_part(vote.voter, *vote.cert);
+        auto &qc = blk->self_qc;
+        if (qc == nullptr)
+        {
+            LOG_WARN("vote for block not proposed by itself");
+            qc = create_quorum_cert(blk->get_hash());
+        }
+        qc->add_part(vote.voter, *vote.cert);
         if (qsize == config.nmajority)
             on_qc_finish(blk);
     }
diff --git a/src/hotstuff.cpp b/src/hotstuff.cpp
index f4454d4..d0b42c3 100644
--- a/src/hotstuff.cpp
+++ b/src/hotstuff.cpp
@@ -84,7 +84,7 @@ ReplicaID HotStuffBase::add_command(command_t cmd) {
             cmd_pending.pop();
         }
         pmaker->beat().then([this, cmds = std::move(cmds)]() {
-            on_propose(cmds);
+            on_propose(cmds, pmaker->get_parents());
         });
     }
     return proposer;
@@ -383,13 +383,12 @@ promise_t HotStuffBase::async_decide(const uint256_t &cmd_hash) {
 }
 
 HotStuffBase::HotStuffBase(uint32_t blk_size,
-                    int32_t parent_limit,
                     ReplicaID rid,
                     privkey_bt &&priv_key,
                     NetAddr listen_addr,
-                    EventContext eb,
-                    pacemaker_bt pmaker):
-        HotStuffCore(rid, std::move(priv_key), parent_limit),
+                    pacemaker_bt pmaker,
+                    EventContext eb):
+        HotStuffCore(rid, std::move(priv_key)),
         listen_addr(listen_addr),
         blk_size(blk_size),
         eb(eb),
diff --git a/src/hotstuff_app.cpp b/src/hotstuff_app.cpp
index 5f21fec..e1eec1b 100644
--- a/src/hotstuff_app.cpp
+++ b/src/hotstuff_app.cpp
@@ -61,6 +61,7 @@ class HotStuffApp: public HotStuff {
     Event ev_stat_timer;
     /** the binding address for client RPC */
     NetAddr clisten_addr;
+    int32_t parent_limit;
 
     using conn_client_t = MsgNetwork<MsgClient>::conn_t;
 
@@ -209,12 +210,14 @@ HotStuffApp::HotStuffApp(uint32_t blk_size,
                         NetAddr plisten_addr,
                         NetAddr clisten_addr,
                         const EventContext &eb):
-    HotStuff(blk_size, parent_limit, idx, raw_privkey,
-            plisten_addr, eb, new hotstuff::PaceMakerDummyFixed(1)),
+    HotStuff(blk_size, idx, raw_privkey,
+            plisten_addr,
+            new hotstuff::PaceMakerDummyFixed(1, parent_limit), eb),
     stat_period(stat_period),
     eb(eb),
     cn(eb),
-    clisten_addr(clisten_addr) {
+    clisten_addr(clisten_addr),
+    parent_limit(parent_limit) {
     /* register the handlers for msg from clients */
     cn.reg_handler(hotstuff::REQ_CMD, std::bind(&HotStuffApp::client_request_cmd_handler, this, _1, _2));
     cn.reg_handler(hotstuff::CHK_CMD, std::bind(&HotStuffApp::client_check_cmd_handler, this, _1, _2));