Byzantine Geoconsensus

The problem of Byzantine consensus [12, 17] has been attracting extensive attention from researchers and engineers in distributed systems. It has applications in distributed storage [1, 2, 4, 5, 11], secure communication [7], safety-critical systems [19], blockchain [15, 20, 22], and Internet of Things (IoT) [13].

Consider a set of $N$ processes with unique IDs that can communicate with each other. Assume that $f$ processes out of these $N$ processes are Byzantine. Assume also that which process is Byzantine is not known to correct processes, except possibly the size $f$ of Byzantine processes. The Byzantine consensus problem here requires the $N-f$ correct processes to reach to an agreement tolerating arbitrary behaviors of the $f$ Byzantine processes.

Pease et al. [17] showed that the maximum possible number of faults $f$ that can be tolerated depends on the way how the (correct) processes communicate: through oral messages or through unforgable written messages (also called signatures). An oral message is completely under the control of the sender, therefore, if the sender is Byzantine, then it can transmit any possible message. This is not true for a signed, written message. Pease et al. [17] showed that the consensus is solvable only if $f<N/3$ when communication between processes is through oral messages. For signed, written messages, they showed that the consensus is possible tolerating any number of faulty processes $f\leq N$.

The Byzantine consensus problem discussed above assumes nothing about the locations of the processes, except that they have unique IDs. Since each process can communicate with each other, it can be assumed that the $N$ processes work under a complete graph (i.e., clique) topology consisting of $N$ vertices and $N(N-1)/2$ edges. Byzantine consensus has also been studied in arbitrary graphs [21, 17] and in wireless networks [16], relaxing the complete graph topology requirement so that a process may not be able to communicate with all other $N-1$ processes. The goal in these studies is to establish necessary and sufficient conditions for consensus to be solvable. For example, Pease et al. [17] showed that the consensus is solvable through oral messages tolerating $f$ Byzantine processes if the communication topology is $3f$-regular. Furthermore, there is a number of studies on a related problem of Byzantine broadcast when the communication topology is not a complete graph topology, see for example [10, 18]. Byzantine broadcast becomes fairly simple for a complete graph topology.

Recently, motivated by IoT-blockchain applications, Lao et al. [13] proposed a consensus protocol, which they call Geographic-PBFT or simply G-PBFT, that extends the well-known PBFT consensus protocol by Castro and Liskov [4] to the geographic setting. The authors considered the case of fixed IoT devices embedded on geographical locations for data collection and processing. The location data can be obtained through recording location information at the installation time or can also be obtained using low-cost GPS receivers or location estimation algorithms [3, 9]. They argued that the fixed IoT devices have more computational power than other mobile IoT devices (e.g., mobile phones and sensors) and are less likely to become malicious nodes. They then exploited (geographical) location information of fixed IoT devices to reach consensus. They argued that G-PBFT avoids Sybil attacks, reduces the overhead for validating and recording transactions, and achieves high consensus efficiency and low traffic intensity. However, G-PBFT is validated only experimentally and no formal analysis is given.

In this paper, we formally define and study the Byzantine consensus problem when processes are embedded on the geographical locations in fixed unique coordinates, which we call the Byzantine geoconsensus problem. If fault locations are not constrained, the geoconsensus problem differs little from the Byzantine consensus. This is because the unique locations serve as IDs of the processes and same set of results can be established depending on whether communication between processes is through oral messages or unforgable written messages. Therefore, we relate the fault locations to the geometry of the problem, assuming that the faults are limited to a fault area $F$ (going beyond the limitation of mapping Byzantine behavior to individual processes). In other words, the fault area lifts the restriction of mapping Byzantine behavior to individual processes in the classic setting and now maps the Byzantine behavior to all the processors within a certain area in the geographical setting. Applying the classic approaches of Byzantine consensus may not exploit the collective Byzantine behavior of the processes in the fault area and hence they may not provide benefits in the geographical setting. Furthermore, we are not aware of prior work in Byzantine consensus where processes are embedded in a geometric plane while faulty processes are located in a fixed area.

In light of the recent development on location-based consensus protocols, such as G-PBFT [13], discussed above, we believe that our setting deserves a formal study. In this paper we consider the Byzantine geoconsensus problem in case the processes are embedded in a $d$-dimensional plane, $d\geq 2$. We study the possibility and bounds for a solution to geoconsensus. We demonstrate that geoconsensus allows quite robust solutions: all but a fixed number of processes may be Byzantine.

In this paper, we made the following five contributions:

• (i)

  An impossibility result that geoconsensus is not solvable if all $N$ processes may be covered by $3$ equal size areas $F$ and one of them may be fault area. This extends to the case of $N$ processes being covered by $3M$ areas $F$ with $M$ areas being faulty.

• (ii)

  The algorithm BASIC that solves geoconsensus tolerating $f\leq N-(2M+1)$ Byzantine processes, provided that there are $9M+3$ processes with pairwise distance between them greater than $D$.

• (iii)

  The algorithm GENERIC that solves geoconsensus tolerating $f\leq N-15M$ Byzantine processes, provided that all $N$ processes are covered by $22M$ axis-aligned squares of the same size as the fault area $F$, removing the pairwise distance assumption in the algorithm BASIC.

• (iv)

  An extension of the GENERIC algorithm to circular $F$ tolerating $f\leq N-57M$ Byzantine processes if all $N$ processes are covered by $85M$ circles of same size as $F$.

• (v)

  Extensions of the results (iii) and (iv) to various size combinations of fault and non-fault areas as well as to $d$-dimensional process embeddings, $d\geq 3$.

Our results are interesting as they provide trade-offs among $N,M,$ and $f$, which is in contrast to the trade-off provided only between $N$ and $f$ in the Byzantine consensus literature. For example, the results in Byzantine consensus show that only $f<N/3$ Byzantine processes can be tolerated, whereas our results show that as many as $f\leq N-\alpha M$, Byzantine processes can be tolerated provided that the processes are placed on the geographical locations so that at least $\beta M$ areas (same size as $F$) are needed to cover them. Here $\alpha$ and $\beta$ are both integers with $\beta\geq c\cdot\alpha$ for some constant $c$.

Furthermore, our geoconsensus algorithms reduce the message and space complexity in solving consensus. In the Byzantine consensus literature, every process sends communication with every other process in each round. Therefore, in one round there are $O(N^{2})$ messages exchanged in total. As the consensus algorithm runs for $O(f)$ rounds, in total $O(f\cdot N^{2})$ messages are exchanged in the worst-case. In our algorithms, let $N$ processes are covered by $X$ areas of size the same as fault area $F$. Then in a round only $O(X^{2})$ messages are exchanged. Since the algorithm runs for $O(M)$ rounds to reach geoconsensus, in total $O(M\cdot X^{2})$ messages are exchanged in the worst-case. Therefore, our geoconsensus algorithms are message (equivalently communication) efficient. The improvement on space complexity can also be argued analogously.

Finally, Pease et al. [17] showed that it is impossible to solve consensus through oral messages when $N=3f$ but there is a solution when $N\geq 3f+1$. That is, there is no gap on the impossibility result and a solution. We can only show that it is impossible to solve consensus when all $N$ processes are covered by $3M$ areas that are the same size as $F$ but there is a solution when all $N$ processes are covered by at least $22M$ areas (for the axis-aligned squares case). Therefore, there is a general gap between the condition for impossibility and the condition for a solution. We leave this gap as open and note that it would be interesting at the same time challenging to close this gap.

For the algorithm GENERIC, we start by covering processes by axis-aligned squares and studying how these squares may intersect with fault areas of various shapes and sizes. Determining optimal axis-aligned square coverage is NP-hard. We provide constant-ratio approximation algorithms. We also discuss how to cover processes by circular areas. Then, we use these ideas to construct algorithm GENERIC for fault areas that are either square or circular, which does not need the pairwise distance requirement of BASIC but requires the bound on the number of areas in the cover area set. Finally, we extend these ideas to develop covering techniques for higher dimensions.

A fault area set or just fault set is the set $\mathcal{F}$ of identical fault areas $F$. The size of this set is $M$, i.e., $|\mathcal{F}|=M$. The adversary controls the placement of all areas in $\mathcal{F}$. Correct processes know the shape and size of the fault areas $F$ as well as $M$, the size of $\mathcal{F}$. However, correct processes do not know the precise placement of the fault areas $\mathcal{F}$. For example, if $\mathcal{F}$ contains $4$ fault square fault areas $F$ with the side $\ell$, then correct processes know that there are $4$ square fault areas with side $\ell$ each but do not know where they are located. Table 1 summarizes notation used in this paper.

agreement

– no two correct processes decide differently;

validity

– if all the correct processes input the same value $v$, then every correct process decides $v$;

termination

– every correct process eventually decides.

In this section, we present the algorithm we call BASIC that solves geoconsensus for up to $f<N-(2M+1),M\geq 1$ faulty processes located in fault area set $\mathcal{F}$ of size $|\mathcal{F}|=M$ provided that ${\mathcal{P}}$ contains at least $9M+3$ processes such that the pairwise distance between them is greater than the diameter $D$ of the fault areas $F\in\mathcal{F}$.

The pseudocode of BASIC is shown in Algorithm 1. It contains two parts: the leaders selection and the consensus procedure. The first component is the selection of leaders. So as to not be covered by $F$ jointly, the leaders need to be located pairwise distance more than $D$ away from each other. Finding the largest set of such leaders is equivalent to computing the maximal independent set in a unit disk graph. This problem is known to be NP-hard [6]. We, therefore, employ a greedy heuristic.

For the leaders selection, for each process $p_{i}$, denote by $\mathit{Nb}(p_{i},D)$ the distance $D$ neighborhood of $p_{i}$. That is, $p_{j}\in\mathit{Nb}(p_{i},D)$ if $d(p_{i},p_{j})\leq D$. A distance $D$ independent set for a planar graph is a set of processes such that all processes in the planar graph are at most $D$ away from the processes in this independent set. It is known [14, Lemma 3.3] that every distance $D$ graph has a neighborhood whose induced subgraph contains any independent set of size at most 3.

The set of leaders ${\mathcal{P}}_{D}\subset{\mathcal{P}}$ selection procedure operates as follows. A set $P_{C}$ of leader candidates is processed. At first, all processes are candidates. All processes whose distance $D$ neighborhood induce a subgraph with an independent set no more than $3$ are found. The process $p_{i}$ with lexicographically smallest coordinates, i.e. the process in the bottom left corner, is selected into the leader set ${\mathcal{P}}_{D}$. Then, all processes in $\mathit{Nb}(p_{i},D)$ are removed from the leader candidate set ${\mathcal{P}}_{C}$. This procedure repeats until ${\mathcal{P}}_{C}$ is exhausted.

The second part of BASIC relies on the classic consensus algorithm of Pease et al. [17]. We denote this algorithm as PSL. The input of PSL is the set of $3f+1$ processes such that at most $f$ of them are faulty as well as the input $1$ or $0$ for each process. As output, the correct processes provide the decisions value subject to the three properties of the solution to consensus. PSL requires $f+1$ communication rounds.

The complete BASIC operates as follows. All processes select leaders in $P_{D}$. Then, the leaders run PSL and broadcast their decision. The rest of the correct processes, if any, adopt this decision.

In this section, in preparation for describing the GENERIC geoconsensus algorithm, we discuss techniques of covering processes by axis-aligned squares and circles. These techniques vary depending on the shape and alignment of the fault area $F$.

Let process $p_{i}$ be at coordinate $(x_{i},y_{i})$. We say that $p_{i}$ is covered by $A$ if and only if $x_{1}\leq x_{i}\leq x_{1}+\ell$ and $y_{1}\leq y_{i}\leq y_{1}+\ell$. We assume that $A$ is closed, i.e., process $p_{i}$ is assumed to be covered by $A$ even when $p_{i}$ is positioned on the boundary of $A$.

We first formally define the covering problem by square areas $A$, which we denote by SQUARE-COVER. Let ${\mathcal{A}}$ be a set of square areas $A$. We say that ${\mathcal{A}}$ completely covers all $N$ processes if each $p_{i}\in{\mathcal{P}}$ is covered by at least one square of ${\mathcal{A}}$.

GSQUARE operates as follows. Suppose the coordinates of process $p_{i}\in{\mathcal{P}}$ are $(x_{i},y_{i})$. Let $x_{min}=\min_{1\leq i\leq N}x_{i},x_{max}=\max_{1\leq i\leq N}x_{i},y_{min}=\min_{1\leq i\leq N}y_{i},$ and $y_{max}=\max_{1\leq i\leq N}y_{i}.$ Let $R$ be an axis-aligned rectangle with the bottom left corner at $(x_{min},y_{min})$ and the top right corner at $(x_{max},y_{max})$. It is immediate that $R$ is the smallest axis-aligned rectangle that covers all $N$ processes. The width of $R$ is $width(R)=x_{max}-x_{min}$ and the height is $height(R)=y_{max}-y_{min}$. See Figure 1 for illustration.

Cover rectangle $R$ by a set ${\mathcal{R}}$ of $m$ slabs ${\mathcal{R}}=\{R_{1},R_{2},\ldots,R_{m}\}$. The height of each slab $R_{i}$ is $\ell$, except for the last slab $R_{m}$ whose height may be less than $\ell$. The width of each slab is $width(R)$. That is this width is the same is the width of $R$.

This slab-covering is done as follows. Let $y_{1}=y_{min}+\ell$. The area of $R$ between two horizontal lines passing through $y_{min}$ to $y_{1}$ is the first slab $R_{1}$. Now consider only the processes in $R$ that are not covered by $R_{1}$. Denote that process set by ${\mathcal{P}}^{\prime}$. Consider the bottom-most process in ${\mathcal{P}}^{\prime}$, i.e., process $p_{min^{\prime}}=(x_{min^{\prime}},y_{min^{\prime}})\in{\mathcal{P}}^{\prime}$. We have that $y_{min^{\prime}}>y_{min}+\ell$. Draw two horizontal lines passing through $y_{min^{\prime}}$ and $y_{min^{\prime}}+\ell$. The area of $R$ between these lines is in slab $R_{2}$. Continue this way until all the points in ${\mathcal{P}}$ are covered by a slab. In the last slab $R_{m}$, it may be the case that its height $height(R_{m})<\ell$.

So far, we covered $R$ by a set of $m$ slabs ${\mathcal{R}}=\{R_{1},\ldots,R_{m}\}$. We now we cover each such slab by axis-aligned square areas $A=\ell\times\ell$. See Figure 2 for illustration. This square-covering is done as follows. Let $R_{i}$ be a slab to cover. Put area $A$ on $R_{i}$ so that the top left corner of $A$ overlaps with the top left corner of slab $R_{i}$. Slide $A$ horizontally to the right so that there is a process in $R_{i}$ positioned on the left vertical line of $A$. Fix that area $A$ as one cover square and name it $A_{1}({R_{i}})$. Now consider only the points in $R_{i}$ not covered by $A_{1}(R_{i})$. It is immediate that those points are to the right of $A_{1}(R_{i})$. Place $A$ on those points so that there is a point in $R_{i}$ positioned on the left side of $A$. Thus, there is no point of $R_{i}$ to the left of this second $A$ that is not covered by $A_{1}({R_{i}})$). Fix this as the second cover square and name it $A_{2}({R_{i}})$. Continue in this manner to cover all the points in $R_{i}$. Repeat this process for every slab of $R$.

Let $k_{opt}({\mathcal{R}})$ be the number of axis-aligned square areas $A=\ell\times\ell$ to cover all $N$ processes in $R$ in the optimal cover algorithm. We now show that $k_{greedy}({\mathcal{R}})\leq 2\cdot k_{opt}({\mathcal{R}})$, i.e., GSQUARE provides 2-approximation. We divide the slabs in the set ${\mathcal{R}}$ into two sets ${\mathcal{R}}_{odd}$ and ${\mathcal{R}}_{even}$. For $1\leq i\leq m$, let

The first lemma below is for each $A$ being an axis-aligned square of side $\ell$ or a circle of diameter $\ell$ while $F$ being either a square of side $\ell/\sqrt{2}$ or a circle of diameter $\ell/\sqrt{2}$. The second lemma below considers circular fault area $F$ of diameter $\sqrt{2}\ell$.

We now describe an algorithm solving geoconsensus we call GENERIC for a set ${\mathcal{P}}$ of $N$ processes on the plane. Each process $p_{k}$ knows the coordinates of all other processes and can communicate with all of them. Each process $p_{k}$ knows the shape (circle, square, etc.) and size (diameter, side, etc.) of the fault area $F$. There are $M\geq 1$ fault areas, i.e., $|\mathcal{F}|=M$ and $p_{k}$ knows $M$. The processes do not know the orientation and location of each fault area $F$. Fault area $F$ is controlled by an adversary and all processes covered by that area $F$ are Byzantine. Each process $p_{k}$ is given an initial value either 0 or 1. The output of each process has to comply with the three properties of geoconsensus.

The pseudocode is given in Algorithm 2. GENERIC operates as follows. Each process $p_{k}$ computes a set ${\mathcal{A}}$ of covers $A_{j}(R_{i})$ that are of same size as $F$. Then $p_{k}$ determines the leader $l_{j}(A_{j}(R_{i}))$ in each cover $A_{j}(R_{i})$. The process in $A_{j}(R_{i})$ with smallest $y$-coordinate is selected as a leader. If there exist two processes with the same smallest $y$-coordinate, then the process with the smaller $x$-coordinate between them is picked. If $p_{k}$ is selected leader, it participates in running PSL [17]. The leaders run PSL then broadcast the achieved decision. The non-leader processes adopt it.

Let the fault area $F=\ell\times\ell$ be a, not necessarily axis-aligned, square.