Hypercube topology for byzantine fault tolerant solutions to reduce network communication overhead of PBFT-based protocols
One example method includes receiving, by each node in a group of nodes that is organized in a logical hypercube topology, a message from a primary node that is a member of the group of nodes. When none of the nodes in the group of nodes are faulty, for each of ‘n’ prepare phases and ‘n’ commit phases of a communication protocol, transmitting, by each node to only a first respective pair node, a first group of one or more messages accumulated by the node, receiving, by each node from only a second respective pair node, a second group of one or more messages accumulated by the second respective pair node and, after the ‘n’ prepare phases and ‘n’ commit phases have been completed, each of the nodes has accumulated at least a minimum number of total messages to declare consensus.
1 . A method, comprising:
receiving, by each node in a group of nodes that is organized in a logical hypercube topology, a message from a primary node that is a member of the group of nodes;
when none of the nodes in the group of nodes are faulty, for each of ‘n’ prepare phases and ‘n’ commit phases of a communication protocol, where ‘n’ is an integer that is equal to, or greater than, 1:
transmitting, by each node to only a first respective pair node, a first group of one or more messages accumulated by the node performing the transmitting;
receiving, by each node from only a second respective pair node, a second group of one or more messages accumulated by the second respective pair node; and
wherein after the ‘n’ prepare phases and ‘n’ commit phases have been completed, each of the nodes has accumulated at least a minimum number of total messages to declare consensus; and
after the ‘n’ prepare phases and ‘n’ commit phases have been completed, transmitting, by each node to a client, a reply.
2 . The method as recited in claim 1 , wherein the logical hypercube topology comprises an ‘n’ dimensional hypercube.
3 . The method as recited in claim 1 , wherein the replies indicate a consensus of the nodes regarding an aspect of a communication network modeled by the logical hypercube topology.
4 . The method as recited in claim 1 , wherein the total messages accumulated by any of the nodes is no more than 2 n total messages.
5 . The method as recited in claim 1 , wherein when one of the nodes is a faulty node that has not transmitted any messages, only a node without the minimum number of total messages, calls a post-phase that is either a prepare post-phase, or a commit post-phase.
6 . The method as recited in claim 5 , wherein during execution of the post-phase, the node that has not accumulated the minimum number of total messages performs operations comprising:
verifying which node is a pair node in a next phase of a next Hamming channel available;
requesting a message from that pair node; and
after receiving a reply from the pair node, verifying if the minimum number of total messages has been accumulated and, if not, moving to a next phase of the Hamming channel or moving to a next Hamming channel, until the minimum number of total messages has been accumulated, or there are no more Hamming channels available.
7 . The method as recited in claim 1 , wherein each node communicates only with nodes in a same Hamming distance channel for each prepare phase and each commit phase of the communication protocol.
8 . The method as recited in claim 1 , wherein when no nodes are faulty, a message complexity for a communication network modeled by the logical hypercube topology is no more than O(n*log 2 n).
9 . A pBFT (practical Byzantine Fault Tolerant) protocol comprising the method as recited in claim 1 , and wherein the primary node transmits its message after receipt, by the primary node, of a request from a client.
10 . The method as recited in claim 1 , wherein the logical hypercube topology comprises an incomplete hypercube, and the incomplete hypercube is hardened by either adding one or more nodes to the incomplete hypercube, or removing one or more nodes from the hypercube.
11 . A non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising:
receiving, by each node in a group of nodes that is organized in a logical hypercube topology, a message from a primary node that is a member of the group of nodes;
when none of the nodes in the group of nodes are faulty, for each of ‘n’ prepare phases and ‘n’ commit phases of a communication protocol, where ‘n’ is an integer that is equal to, or greater than, 1:
transmitting, by each node to only a first respective pair node, a first group of one or more messages accumulated by the node performing the transmitting;
receiving, by each node from only a second respective pair node, a second group of one or more messages accumulated by the second respective pair node; and
wherein after the ‘n’ prepare phases and ‘n’ commit phases have been completed, each of the nodes has accumulated at least a minimum number of total messages to declare consensus; and
after the ‘n’ prepare phases and ‘n’ commit phases have been completed, transmitting, by each node to a client, a reply.
12 . The non-transitory storage medium as recited in claim 11 , wherein the logical hypercube topology comprises an ‘n’ dimensional hypercube.
13 . The non-transitory storage medium as recited in claim 11 , wherein the replies indicate a consensus of the nodes regarding an aspect of a communication network modeled by the logical hypercube topology.
14 . The non-transitory storage medium as recited in claim 11 , wherein the total messages accumulated by any of the nodes is no more than 2 n total messages.
15 . The non-transitory storage medium as recited in claim 11 , wherein when one of the nodes is a faulty node that has not transmitted any messages, only a node without the minimum number of total messages, calls a post-phase that is either a prepare post-phase, or a commit post-phase.
16 . The non-transitory storage medium as recited in claim 15 , wherein during execution of the post-phase, the node that has not accumulated the minimum number of total messages performs operations comprising:
verifying which node is a pair node in a next phase of a next Hamming channel available;
requesting a message from that pair node; and
after receiving a reply from the pair node, verifying if the minimum number of total messages has been accumulated and, if not, moving to a next phase of the Hamming channel or moving to a next Hamming channel, until the minimum number of total messages has been accumulated, or there are no more Hamming channels available.
17 . The non-transitory storage medium as recited in claim 11 , wherein each node communicates only with nodes in a same Hamming distance channel for each prepare phase and each commit phase of the communication protocol.
18 . The non-transitory storage medium as recited in claim 11 , wherein when no nodes are faulty, a message complexity for a communication network modeled by the logical hypercube topology is no more than O(n*log 2 n).
19 . The non-transitory storage medium as recited in claim 11 , wherein the operations are performed as part of a pBFT (practical Byzantine Fault Tolerant) protocol, and wherein the primary node transmits its message after receipt, by the primary node, of a request from a client.
20 . The non-transitory storage medium as recited in claim 11 , wherein the logical hypercube topology comprises an incomplete hypercube, and the incomplete hypercube is hardened by either adding one or more nodes to the incomplete hypercube, or removing one or more nodes from the hypercube.