aboutsummaryrefslogtreecommitdiff
path: root/include/hotstuff
diff options
context:
space:
mode:
authorDeterminant <[email protected]>2018-08-16 15:57:06 -0400
committerDeterminant <[email protected]>2018-08-16 15:57:06 -0400
commita5f0a7198334caf95bff0bf1c6c5a2c30eb32795 (patch)
treeb3d7ce958ddec7fc05fcf0f703eadd5dea40d719 /include/hotstuff
parenta95e4362fa197b44138616c8e1c8a05d192b0a82 (diff)
fix bugs in PaceMaker
Diffstat (limited to 'include/hotstuff')
-rw-r--r--include/hotstuff/consensus.h14
-rw-r--r--include/hotstuff/liveness.h148
2 files changed, 113 insertions, 49 deletions
diff --git a/include/hotstuff/consensus.h b/include/hotstuff/consensus.h
index a99e6af..d27f8c5 100644
--- a/include/hotstuff/consensus.h
+++ b/include/hotstuff/consensus.h
@@ -32,13 +32,18 @@ class HotStuffCore {
std::unordered_map<block_t, promise_t> qc_waiting;
promise_t propose_waiting;
promise_t receive_proposal_waiting;
+ promise_t bqc_update_waiting;
+ /* == feature switches == */
+ /** always vote negatively, useful for some PaceMakers */
+ bool neg_vote;
block_t get_delivered_blk(const uint256_t &blk_hash);
void sanity_check_delivered(const block_t &blk);
void check_commit(const block_t &_bqc);
bool update(const uint256_t &bqc_hash);
+ void on_bqc_update();
void on_qc_finish(const block_t &blk);
- void on_propose_(const block_t &blk);
+ void on_propose_(const Proposal &prop);
void on_receive_proposal_(const Proposal &prop);
protected:
@@ -127,9 +132,11 @@ class HotStuffCore {
/** Get a promise resolved when the block gets a QC. */
promise_t async_qc_finish(const block_t &blk);
/** Get a promise resolved when a new block is proposed. */
- promise_t async_wait_propose();
+ promise_t async_wait_proposal();
/** Get a promise resolved when a new proposal is received. */
promise_t async_wait_receive_proposal();
+ /** Get a promise resolved when bqc is updated. */
+ promise_t async_bqc_update();
/* Other useful functions */
block_t get_genesis() { return b0; }
@@ -137,6 +144,7 @@ class HotStuffCore {
ReplicaID get_id() const { return id; }
const std::set<block_t, BlockHeightCmp> get_tails() const { return tails; }
operator std::string () const;
+ void set_neg_vote(bool _neg_vote) { neg_vote = _neg_vote; }
};
/** Abstraction for proposal messages. */
@@ -154,7 +162,7 @@ struct Proposal: public Serializable {
Proposal(): blk(nullptr), hsc(nullptr) {}
Proposal(ReplicaID proposer,
const uint256_t &bqc_hash,
- block_t &blk,
+ const block_t &blk,
HotStuffCore *hsc):
proposer(proposer),
bqc_hash(bqc_hash),
diff --git a/include/hotstuff/liveness.h b/include/hotstuff/liveness.h
index 0e1103a..fbf7134 100644
--- a/include/hotstuff/liveness.h
+++ b/include/hotstuff/liveness.h
@@ -31,7 +31,7 @@ class PaceMaker {
/** 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
* */
- virtual promise_t next_proposer(ReplicaID last_proposer) = 0;
+ virtual promise_t beat_resp(ReplicaID last_proposer) = 0;
};
using pacemaker_bt = BoxObj<PaceMaker>;
@@ -41,24 +41,64 @@ using pacemaker_bt = BoxObj<PaceMaker>;
* direct parent, while including other tail blocks (up to parent_limit) as
* uncles/aunts. */
class PMAllParents: public virtual PaceMaker {
+ block_t bqc_tail;
const int32_t parent_limit; /**< maximum number of parents */
+
+ void reg_bqc_update() {
+ hsc->async_bqc_update().then([this](const block_t &bqc) {
+ for (const auto &blk: hsc->get_tails())
+ {
+ block_t b;
+ for (b = blk;
+ b->get_height() > bqc->get_height();
+ b = b->get_parents()[0]);
+ if (b == bqc && b->get_height() > bqc_tail->get_height())
+ bqc_tail = b;
+ }
+ reg_bqc_update();
+ });
+ }
+
+ void reg_proposal() {
+ hsc->async_wait_proposal().then([this](const Proposal &prop) {
+ if (prop.blk->get_parents()[0] == bqc_tail)
+ bqc_tail = prop.blk;
+ reg_proposal();
+ });
+ }
+
+ void reg_receive_proposal() {
+ hsc->async_wait_receive_proposal().then([this](const Proposal &prop) {
+ if (prop.blk->get_parents()[0] == bqc_tail)
+ bqc_tail = prop.blk;
+ reg_receive_proposal();
+ });
+ }
+
public:
PMAllParents(int32_t parent_limit): parent_limit(parent_limit) {}
+ void init() {
+ bqc_tail = hsc->get_genesis();
+ reg_bqc_update();
+ reg_proposal();
+ reg_receive_proposal();
+ }
+
std::vector<block_t> get_parents() override {
- auto tails = hsc->get_tails();
- size_t nparents = tails.size();
+ const auto &tails = hsc->get_tails();
+ std::vector<block_t> parents{bqc_tail};
+ auto 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--)
+ for (const auto &blk: tails)
{
- auto it = tails.begin();
- parents.push_back(*it);
- tails.erase(it);
+ if (blk != bqc_tail)
+ {
+ parents.push_back(blk);
+ if (!--nparents) break;
+ }
}
return std::move(parents);
}
@@ -86,17 +126,16 @@ class PMWaitQC: public virtual PaceMaker {
}
void update_last_proposed() {
- hsc->async_wait_propose().then([this](block_t blk) {
+ hsc->async_wait_proposal().then([this](const Proposal &prop) {
update_last_proposed();
- last_proposed = blk;
+ last_proposed = prop.blk;
locked = false;
schedule_next();
});
}
public:
- void init(HotStuffCore *hsc) override {
- PaceMaker::init(hsc);
+ void init() {
last_proposed = hsc->get_genesis();
locked = false;
update_last_proposed();
@@ -113,7 +152,7 @@ class PMWaitQC: public virtual PaceMaker {
return pm;
}
- promise_t next_proposer(ReplicaID last_proposer) override {
+ promise_t beat_resp(ReplicaID last_proposer) override {
return promise_t([last_proposer](promise_t &pm) {
pm.resolve(last_proposer);
});
@@ -124,6 +163,11 @@ class PMWaitQC: public virtual PaceMaker {
struct PaceMakerDummy: public PMAllParents, public PMWaitQC {
PaceMakerDummy(int32_t parent_limit):
PMAllParents(parent_limit), PMWaitQC() {}
+ void init(HotStuffCore *hsc) override {
+ PaceMaker::init(hsc);
+ PMAllParents::init();
+ PMWaitQC::init();
+ }
};
/** PaceMakerDummy with a fixed proposer. */
@@ -140,7 +184,7 @@ class PaceMakerDummyFixed: public PaceMakerDummy {
return proposer;
}
- promise_t next_proposer(ReplicaID) override {
+ promise_t beat_resp(ReplicaID) override {
return promise_t([this](promise_t &pm) {
pm.resolve(proposer);
});
@@ -178,7 +222,7 @@ class PMStickyProposer: virtual public PaceMaker {
/** QC timer or randomized timeout */
Event timer;
block_t last_proposed;
- /** the proposer it believes when it is a follower */
+ /** the proposer it believes */
ReplicaID proposer;
/* extra state needed for a proposer */
@@ -207,6 +251,8 @@ class PMStickyProposer: virtual public PaceMaker {
last_proposed_by.clear();
}
+ /* helper functions for a follower */
+
void reg_follower_receive_proposal() {
pm_wait_receive_proposal.reject();
(pm_wait_receive_proposal = hsc->async_wait_receive_proposal())
@@ -219,13 +265,10 @@ class PMStickyProposer: virtual public PaceMaker {
if (prop.proposer == proposer)
{
auto &qc_ref = prop.blk->get_qc_ref();
- if (last_proposed)
+ if (last_proposed && qc_ref != last_proposed)
{
- if (qc_ref != last_proposed)
- {
- HOTSTUFF_LOG_PROTO("proposer misbehave");
- to_candidate(); /* proposer misbehave */
- }
+ HOTSTUFF_LOG_PROTO("proposer misbehave");
+ to_candidate(); /* proposer misbehave */
}
HOTSTUFF_LOG_PROTO("proposer emits new QC");
last_proposed = prop.blk;
@@ -234,14 +277,16 @@ class PMStickyProposer: virtual public PaceMaker {
reg_follower_receive_proposal();
}
+ /* helper functions for a proposer */
+
void proposer_schedule_next() {
if (!pending_beats.empty() && !locked)
{
auto pm = pending_beats.front();
pending_beats.pop();
pm_qc_finish.reject();
- pm_qc_finish =
- hsc->async_qc_finish(last_proposed).then([this, pm]() {
+ (pm_qc_finish = hsc->async_qc_finish(last_proposed))
+ .then([this, pm]() {
reset_qc_timer();
pm.resolve(proposer);
});
@@ -251,43 +296,46 @@ class PMStickyProposer: virtual public PaceMaker {
void reg_proposer_propose() {
pm_wait_propose.reject();
- (pm_wait_propose = hsc->async_wait_propose()).then(
+ (pm_wait_propose = hsc->async_wait_proposal()).then(
salticidae::generic_bind(
&PMStickyProposer::proposer_propose, this, _1));
}
- void proposer_propose(const block_t &blk) {
- last_proposed = blk;
+ void proposer_propose(const Proposal &prop) {
+ last_proposed = prop.blk;
locked = false;
proposer_schedule_next();
reg_proposer_propose();
}
- void gen() {
+ void propose_elect_block() {
DataStream s;
/* FIXME: should extra data be the voter's id? */
s << hsc->get_id();
+ /* propose a block for leader election */
hsc->on_propose(std::vector<command_t>{},
get_parents(), std::move(s));
}
+ /* helper functions for a candidate */
+
void candidate_qc_timeout() {
pm_qc_finish.reject();
pm_wait_propose.reject();
- (pm_wait_propose = hsc->async_wait_propose()).then([this](const block_t &blk) {
- pm_qc_finish.reject();
- pm_qc_finish = hsc->async_qc_finish(blk).then([this, blk]() {
+ (pm_wait_propose = hsc->async_wait_proposal()).then([this](const Proposal &prop) {
+ const auto &blk = prop.blk;
+ (pm_qc_finish = hsc->async_qc_finish(blk)).then([this, blk]() {
HOTSTUFF_LOG_PROTO("collected QC for %s", std::string(*blk).c_str());
/* managed to collect a QC */
to_proposer();
- gen();
+ propose_elect_block();
});
});
double t = salticidae::gen_rand_timeout(candidate_timeout);
timer.del();
timer.add_with_timeout(t);
HOTSTUFF_LOG_PROTO("candidate next try in %.2fs", t);
- gen();
+ propose_elect_block();
}
void reg_candidate_receive_proposal() {
@@ -299,22 +347,25 @@ class PMStickyProposer: virtual public PaceMaker {
}
void candidate_receive_proposal(const Proposal &prop) {
- auto proposer = prop.proposer;
- auto &p = last_proposed_by[proposer];
- HOTSTUFF_LOG_PROTO("got block %s from %d", std::string(*prop.blk).c_str(), proposer);
+ auto _proposer = prop.proposer;
+ auto &p = last_proposed_by[_proposer];
+ HOTSTUFF_LOG_PROTO("got block %s from %d", std::string(*prop.blk).c_str(), _proposer);
p.reject();
- p = hsc->async_qc_finish(prop.blk).then([this, proposer]() {
- to_follower(proposer);
+ (p = hsc->async_qc_finish(prop.blk)).then([this, _proposer]() {
+ to_follower(_proposer);
});
reg_candidate_receive_proposal();
}
+ /* role transitions */
+
void to_follower(ReplicaID new_proposer) {
HOTSTUFF_LOG_PROTO("new role: follower");
clear_promises();
role = FOLLOWER;
proposer = new_proposer;
last_proposed = nullptr;
+ hsc->set_neg_vote(false);
timer = Event(ec, -1, 0, [this](int, short) {
/* unable to get a QC in time */
to_candidate();
@@ -334,11 +385,12 @@ class PMStickyProposer: virtual public PaceMaker {
role = PROPOSER;
proposer = hsc->get_id();
last_proposed = nullptr;
+ hsc->set_neg_vote(true);
timer = Event(ec, -1, 0, [this](int, short) {
/* proposer unable to get a QC in time */
to_candidate();
});
- proposer_propose(hsc->get_genesis());
+ proposer_propose(Proposal(-1, uint256_t(), hsc->get_genesis(), nullptr));
reset_qc_timer();
}
@@ -348,6 +400,7 @@ class PMStickyProposer: virtual public PaceMaker {
role = CANDIDATE;
proposer = hsc->get_id();
last_proposed = nullptr;
+ hsc->set_neg_vote(false);
timer = Event(ec, -1, 0, [this](int, short) {
candidate_qc_timeout();
});
@@ -360,10 +413,7 @@ class PMStickyProposer: virtual public PaceMaker {
PMStickyProposer(double qc_timeout, const EventContext &ec):
qc_timeout(qc_timeout), ec(ec) {}
- void init(HotStuffCore *hsc) override {
- PaceMaker::init(hsc);
- to_candidate();
- }
+ void init() { to_candidate(); }
ReplicaID get_proposer() override {
return proposer;
@@ -384,9 +434,9 @@ class PMStickyProposer: virtual public PaceMaker {
});
}
- promise_t next_proposer(ReplicaID last_proposer) override {
+ promise_t beat_resp(ReplicaID last_proposer) override {
return promise_t([this, last_proposer](promise_t &pm) {
- pm.resolve(last_proposer); //role == CANDIDATE ? last_proposer : proposer);
+ pm.resolve(last_proposer);
});
}
};
@@ -394,6 +444,12 @@ class PMStickyProposer: virtual public PaceMaker {
struct PaceMakerSticky: public PMAllParents, public PMStickyProposer {
PaceMakerSticky(int32_t parent_limit, double qc_timeout, EventContext eb):
PMAllParents(parent_limit), PMStickyProposer(qc_timeout, eb) {}
+
+ void init(HotStuffCore *hsc) override {
+ PaceMaker::init(hsc);
+ PMAllParents::init();
+ PMStickyProposer::init();
+ }
};
}