How to  generate  a  fault-resilient network  at a lower cost]How to  generate  a  fault-resilient network  at a lower cost

Alexander Mozeika

Mohammad M. Jalalzai

Marcin P. Pawlowski

Status Research & Development GmbH
Baarerstrasse 10

Blockchains facilitate decentralization, security, identity, and data management in cyber-physical systems. However,  consensus protocols used in blockchains are prone to high message and computational complexity costs and are not suitable to be used in IoT. One way to reduce message complexity is to randomly assign network nodes into committees or shards. Keeping committee sizes small is then desirable in order to achieve lower message complexity, but this comes with a penalty of reduced reliability as there is a higher probability that a  large number of faulty nodes will end up in a  committee.
In this work, we study the problem of estimating a probability of a failure in randomly sharded networks. We provide new results and improve existing bounds on the failure probability. Thus,  our framework also paves the way to reduce committee sizes without reducing reliability.

<concept_desc>Security and privacy Security requirements</concept_desc>
<concept_desc>Networks Network reliability</concept_desc>
<concept_desc>Computer systems organization Peer-to-peer architectures</concept_desc>
<concept_desc>Computing methodologies Distributed algorithms</concept_desc>

[100]Security and privacy Security requirements
[300]Networks Network reliability
[500]Computer systems organization Peer-to-peer architectures
[100]Computing methodologies Distributed algorithms

20 February 2007
[revised]12 March 2009
[accepted]5 June 2009

§ INTRODUCTION

Large-scale applications of Cyber-Physical Systems require a significant amount of coordination of a plethora of interconnected devices. Managing thousands of devices pushes the technology to its limits, and creates one of the most important and not yet solved problems of scaling the solution to myriads of connected devices. There are many approaches that try to address this problem efficiently, some of them are focus on centralized solutions, such as cloud   <cit.>, others are introducing novel architectures like mist and fog <cit.> or leveraging fully decentralized solutions based on blockchain <cit.>. Each of them has its own merits but in this work, we are focusing on blockchains that have been leveraged to provide decentralized, verifiable, trusted, and traceable IoT-based applications <cit.>.

Similarly, due to the strict requirements of IoT networks, blockchains are suitable to defend against data manipulation attacks by providing immutability and avoiding  centralized trusted authority for devices to communicate <cit.>. Therefore, there have been several research works on leveraging blockchains to provide public safety service <cit.>, smart surveillance for smart cities <cit.>, automotive industry <cit.> and avionics <cit.>. Furthermore, blockchain technology has also been leveraged to provide    privacy and security in IoT, identity and data management for IoT and monetization for IoT <cit.>.

Blockchain uses distributed consensus mechanism to reach an agreement for a value to be added to the chain. Consensus makes sure every honest node will eventually agree on the same block at the same sequence in the chain.  Consensus is used to achieve State Machine Replication (SMR).
It makes sure that each participant of the network maintains the same state all the time. Well-constructed blockchains must be fault-resilient in order to survive Byzantine faults <cit.> which are one of the most powerful groups of faults in distributed systems.
A Byzantine Fault Tolerant (BFT) system tolerates arbitrary faults (and adversaries). A BFT SMR system provides SMR services in the presence of Byzantine Faults. The upper bound on tolerating Byzantine faults is $f= \frac{n-1}{3}$ <cit.>. This means a system can remain  reliable as long as the number of Byzantine faults is less than one-third.

BFT-based consensus protocols provide BFT SMR services. These services constitute the core layer of blockchains.
Due to the high interest in blockchain, its scalability in terms of the number of nodes (participants) has been one of the main research problems <cit.>. One of the limitations of scaling blockchains is the high message complexity and authenticator (cryptographic signatures) complexity.  Processing a higher number of messages and/or cryptographic operations in a consensus protocol makes it unsuitable for IoT use cases. This is due to the reason that IoT devices have limited bandwidth and processing capacity. Generally, the number of messages as well as cryptographic operations increase as the number of nodes in the network increases.
To scale blockchains (to reduce message and authenticator complexity) different methods were developed to assign nodes randomly in committees <cit.>. The introduction of committees helps to reduce the message and authenticator complexity from $O(N)$  to $O(n)$ with $n \ll N$, where $n$ is the size of the committee and $N$ is the total number of nodes.

However, randomly assigning nodes into committees is not a straightforward task. One does not want to form a committee with a majority of Byzantine nodes. Therefore, it is paramount to estimate the probability of such an event. Achieving tighter bounds on a committee size for a desired failure probability will allow a protocol to have smaller committees. Smaller committees mean lower message complexity and cryptographic operations, making a protocol more suitable for IoT use cases.
Therefore, in this work, we present  analytical results  of calculating the probability of a failure of a network in an event of network random partition. First, we introduce  a very general probabilistic framework of random partitions of $N$ nodes of different “colours”  into $K$ committees.  This framework allows us to construct joint probability distributions of  random partitions. Second, we obtain exact expressions  for these probability distributions  and use them to study the probability of failure.   The latter is the probability of  the event that in at least one of the randomly generated committees, the nodes of some colour exceed a fraction $A$ of all nodes. We consider the probability of failure and we obtain  exact expressions,  bounds, and asymptotic estimates. Finally, we apply our analytical  framework to the sharding of blockchains, which is  a special case of random partitions with two colours  labelling Byzantine and honest nodes, and improve upon known results in this area. In particular,  we  achieve tighter bounds on committee sizes for a given probability of failure, than the previous known results. Moreover, the term Byzantine and adversarial has been used interchangeably in this document.

§.§ Related work

The number of adversaries in a single committee  is usually  modeled with the binomial <cit.> and hypergeometric <cit.> probability distributions.  The probability of failure is estimated by the union bound which multiplies the probability of failure of  a single committee,  which  uses cumulative distribution function of one of these distributions, by the number of committees $K$. The latter suggests that  these univariate distributions are marginals of some joint probability distribution.  Recently it was established that in hypergeometric case  this joint distribution is the multivariate hypergeometric <cit.>.  The latter  corresponds to  a sampling scenario where nodes for committees are selected, without replacement, from a  population of $N$ nodes where it is assumed that $M$ nodes in this population are adversarial. However, it is not clear what is this joint distribution for the binomial case. We note that the binomial distribution is quite often chosen as an approximation <cit.> for the hypergeometric and is  expected to be accurate when the  committee size $n$ is small,  the number of nodes  $N$ is large and the number of adversarial nodes  $M$ is also large.  The probability of failure which  uses full  joint probability distribution, to the best of our knowledge, has not been studied  but in  one work <cit.> where  intuitive derivation of the multivariate hypergeometric distribution was provided  and  corresponding probability of failure  was studied by simulations.  The latter showed advantages of using the joint distribution instead of the union bound  but left analytic solution to be an  open problem <cit.>. The main contribution of this work is to provide a solution to this open problem.

The “urn problem” associated with different sampling scenarios considered for random partitions. Initially, all $N$ nodes of different colours (here only two colours are shown ) are in one large  committee. The number of nodes of colour $\alpha$ in this committee is  $N\times\Prob(\alpha)$ either on average or exactly. A node is selected in a random and unbiased way from this large committee  and  is moved into one of smaller committees  labeled by  $\mu \in[K]$, where $K<N$. This step is governed by the probability $\Prob(\mu\vert\alpha)$, but possibly subject to constraints such as committee sizes and the number of nodes $M=N\times\Prob(\alpha)$ of colour $\alpha$. After $N$ steps all nodes will be moved into smaller committees.

§ MODEL OF RANDOM PARTITIONS

We consider $N$ nodes of $L$ “colours”  distributed into $K$  shards (or committees).  We assume that partition $\A=(\av_1,\ldots,\av_N)$ with  $\av_i=(a_i(1), a_i(2))$, where[For $L\in\mathbb{N}$ we use  the definition $[L]=\{1,\ldots,L\}$.]  $a_i(1)\in[L]$ and $a_i(2)\in[K]$, is observed with the probability

\begin{eqnarray}
\Prob(\A)=\prod_{i=1}^N \Prob(\av_i)  \label{def:P(A)},
\end{eqnarray}

where $\Prob(\av_i)= \Prob(a_i(1),a_i(2))$
is the probability that the node $i$ of colour $a_i(1)$ is in the committee  $a_i(2)$. Let us define[We use the definition   $ \Ind[\mathcal{E}]\in\{0,1\}$ for  the indicator function of some event $\mathcal{E}$ and $\delta_{x;y}$  is  the Kronecker delta function, i.e.  $\delta_{x;y}=\Ind[x=y]$ for   $x,y\in\mathbb{Z}$.] the random variables    $N_{\mu}(\A)= \sum_{i=1}^N\delta_{\mu;\, a_i(2)}$, i.e. the total number of nodes  in committee $\mu$, $N_{\mu}^\alpha(\A)= \sum_{i=1}^N\delta_{\alpha;\, a_i(1)}\delta_{\mu;\, a_i(2)}$, i.e. the number of nodes of colour $\alpha$ in committee $\mu$, and $M= \sum_{\mu=1}^K N_{\mu}^\alpha(\A)$, i.e. the  total number of nodes of colour $\alpha$. We note that $\sum_{\mu=1}^K N_{\mu}(\A)=N$ and $N_{\mu}(\A)= \sum_{\alpha=1}^L N_{\mu}^\alpha(\A)$. The joint probability distribution of these random variables in all of the $K$ committees is given by

\begin{eqnarray}
\Prob\left(N_{1}^\alpha,\ldots, N_{K}^\alpha; N_{1},\ldots,N_{K};M\right)&=&\sum_{\A}\Prob(\A)\,\delta_{M;\sum_{\mu=1}^K N_{\mu}^\alpha(\A)}\prod_{\mu=1}^K\delta_{N_{\mu}^\alpha;N_{\mu}^\alpha(\A)}\delta_{N_{\mu};N_{\mu}(\A)}\label{def:Prob-joint-master},
\end{eqnarray}

where $\sum_{\mu=1}^KN_{\mu}=N$,  $N_{\mu}^\alpha\leq N_{\mu}$ for all $\mu$ and $M\leq N$.

From  the probability distribution (<ref>)  we construct, by  marginalization  and application of Bayes' theorem, the joint distribution

\begin{eqnarray}
%\Prob\left(\left\{N_{\mu}^\alpha, N_{\mu}\right\}\right)
\Prob\left(N_{1}^\alpha,\ldots, N_{K}^\alpha; N_{1},\ldots,N_{K}\right)&=&\sum_{\A}\Prob(\A)\prod_{\mu=1}^K\delta_{N_{\mu}^\alpha;N_{\mu}^\alpha(\A)}\delta_{N_{\mu};N_{\mu}(\A)}\label{def:Prob}
\end{eqnarray}

the conditional distribution

\begin{eqnarray}
\Prob\left(N_{1}^\alpha,\ldots, N_{K}^\alpha\vert N_{1},\ldots,N_{K}\right)
&=&\frac{\Prob\left(N_{1}^\alpha,\ldots, N_{K}^\alpha; N_{1},\ldots,N_{K}\right)}{\Prob\left(N_{1},\ldots,N_{K}\right)}\label{def:Prob-cond}
\end{eqnarray}

and the conditional distribution

\begin{eqnarray}
\Prob\left(N_{1}^\alpha,\ldots, N_{K}^\alpha\vert N_{1},\ldots,N_{K}; M\right)
&=&\frac{\Prob\left(N_{1}^\alpha,\ldots, N_{K}^\alpha; N_{1},\ldots,N_{K};M\right)}{\Prob\left(N_{1},\ldots,N_{K};M\right)}\label{def:Prob-cond-M}.
\end{eqnarray}

These  probability distributions  correspond to three different sampling scenarios  of random partitions (see Figure <ref>).  In the first  scenario, described by (<ref>), each node is assigned randomly to a committee independently from other nodes. The second scenario, described by (<ref>),  corresponds to fixed numbers of (randomly selected) nodes being  assigned  to committees. Finally, the third scenario, described by (<ref>), is similar to the second one  but when we have exactly $M$ nodes of colour $\alpha$.

§ STATISTICAL PROPERTIES OF  RANDOM PARTITIONS

§.§ Probability distributions

For the   probability distributions (<ref>)-(<ref>) we obtain the following results.

Assuming that partition $\A$ is generated with the probability   (<ref>) the joint distribution (<ref>) is the product

\begin{eqnarray}
\Prob\left(N_1,N^\alpha_1,\cdots,N_K,N^\alpha_K \right)
&=&\Prob\left(N_1,\cdots,N_K\vert N \right)\prod_{\mu=1}^K\Prob^\alpha_\mu\left(N^\alpha_\mu\vert N_\mu \right)\label{eq:Prob-joint}
\end{eqnarray}

of the multinomial

\begin{eqnarray}
\Prob\left(N_1,\cdots,N_K\vert N \right)&=&\Ind\left[\sum_{\mu=1}^KN_\mu=N\right]\frac{N!}{\prod_{\mu=1}^KN_\mu!}\prod_{\mu=1}^K \Prob^{N_\mu}(\mu)\label{def:multinomial-dist}
\end{eqnarray}

and the product  $\prod_{\mu=1}^K\Prob^\alpha_\mu\left(N^\alpha_\mu\vert N_\mu \right)$ of the binomial

\begin{eqnarray}
\Prob^\alpha_\mu\left(N^\alpha_\mu\vert N_\mu \right)&=&{N_\mu\choose N^\alpha_\mu}\,\Prob^{N^\alpha_\mu}(\alpha\vert \mu)  \left[1-\Prob(\alpha\vert \mu)\right]^{N_\mu-N^\alpha_\mu}
\label{def:binomial-distr}
\end{eqnarray}

To show this we consider the moment-generating function

\begin{eqnarray}
\mathrm{Z}\left[\tv_1,\tv_2\right]&=&\sum_{N_{1}}\sum_{N_{1}^\alpha}\cdots\sum_{N_{K}}\sum_{N_{K}^\alpha}
\,\Prob\left(N_{1}^\alpha,N_{1},\ldots, N_{K}^\alpha,N_{K}\right)\nonumber\\
&&~~~~~~~~~~\times\rme^{\sum_{\mu=1}^K\left\{N_{\mu}^\alpha\, t_1(\mu)+N_{\mu}\,t_2(\mu)\right\}}\label{def:MGF},
\end{eqnarray}

where $\tv_1,\tv_2\in\R^K$. Now using in above the definition (<ref>) we obtain

\begin{eqnarray}
\mathrm{Z}\left[\tv_1,\tv_2\right]&=&\sum_{\A}\Prob(\A)\,\rme^{\sum_{\mu=1}^K\left\{N_{\mu}^\alpha(\A)\, t_1(\mu)+N_{\mu}(\A)\,t_2(\mu)\right\}}\nonumber\\
&=&\left[\sum_{\beta=1}^L \sum_{\nu=1}^K\Prob(\beta, \nu)\,\rme^{\sum_{\mu=1}^K\,\delta_{\mu;\, \nu}\{t_1(\mu)\,\delta_{\alpha;\, \beta} +t_2(\mu)\}}\right]^N\nonumber\\
&=&\sum_{N_1=0}^N\cdots\sum_{N_K=0}^N \Prob\left(N_1,\cdots,N_K\vert N \right)\prod_{\mu=1}^K\Prob^\alpha_\mu\left(N^\alpha_\mu\vert N_\mu \right)\nonumber\\
&&\times \rme^{\sum_{\mu=1}^K\{t_1(\mu)\,N^\alpha_\mu +t_2(\mu)\,N_\mu\}}\label{eq:MGF}
\end{eqnarray}

and hence comparing above with  (<ref>)  we arrive at  (<ref>).

The consequence of the Lemma <ref> is that the conditional probability distribution  (<ref>) is given  by

\begin{eqnarray}
\Prob\left(N_{1}^\alpha,\ldots, N_{K}^\alpha\vert N_{1},\ldots,N_{K}\right)&=&\prod_{\mu=1}^K\Prob^\alpha_\mu\left(N^\alpha_\mu\vert N_\mu \right)\label{eq:Prob-cond},
\end{eqnarray}

where $\sum_{\mu=1}^KN_\mu=N$, which follows from the equation  (<ref>) and from the  property  $\Prob(Y,X)=\Prob(Y\vert X)\,\Prob(X)$ of a  joint probability distribution. Furthermore,  the marginal of (<ref>) is the product of distributions

\begin{eqnarray}
\Prob^\alpha\!\left(N_\mu,N^\alpha_\mu\vert N\right)
&=&\Prob_\mu\!\left(N_\mu\vert N\right)\,\Prob^\alpha_\mu\!\left(N^\alpha_\mu\vert N_\mu \right),\label{eq:P-marginal}
\end{eqnarray}

where  $\Prob_\mu\left(N_\mu\vert N\right)$ is the binomial distribution

\begin{eqnarray}
\Prob_\mu\left(N_\mu\vert N \right)&=&{N\choose N_\mu}\,\Prob^{N_\mu}(\mu)  \left[1-\Prob(\mu)\right]^{N-N_\mu}.
\end{eqnarray}

Finally, we  also obtain  the following

The conditional probability (<ref>) is the multivariate hypergeometric  distribution

\begin{eqnarray}
%\Prob\left(\{N_{\mu}^\alpha\}\vert \{N_{\mu}\}; M\right)
\Prob\left(N_{1}^\alpha,\ldots, N_{K}^\alpha\vert N_{1},\ldots,N_{K}; M\right)
&=&\frac{\delta_{M;\sum_{\mu=1}^K N_{\mu}^\alpha}\prod_{\mu=1}^K {N_\mu\choose N^\alpha_\mu}}{{N\choose M}}\label{eq:Prob-cond-M}.
\end{eqnarray}

To show this  we first rewrite the probability distribution (<ref>) as follows

\begin{eqnarray}
\Prob\left(N_{1}^\alpha,\ldots, N_{K}^\alpha\vert N_{1},\ldots,N_{K}; M\right)
&=&\frac{\delta_{M;\sum_{\mu=1}^K N_{\mu}^\alpha}\Prob\left(N_{1}^\alpha,N_{1},\ldots, N_{K}^\alpha, N_{K}\right)}{\sum_{\tilde{N}_{1}^\alpha} \cdots \sum_{\tilde{N}_{1}^\alpha}\delta_{M;\sum_{\mu=1}^K \tilde{N}_{\mu}^\alpha}\Prob\left(\tilde{N}_{1}^\alpha,N_{1},\ldots, \tilde{N}_{K}^\alpha, N_{K}\right)}\nonumber\\
&=&\frac{\delta_{M;\sum_{\mu=1}^K N_{\mu}^\alpha}\Prob\left(N_{1}^\alpha,\ldots, N_{K}^\alpha\vert N_{1},\ldots,N_{K}\right)}{\sum_{\tilde{N}_{1}^\alpha} \cdots \sum_{\tilde{N}_{1}^\alpha}\delta_{M;\sum_{\mu=1}^K \tilde{N}_{\mu}^\alpha}\Prob\left(\tilde{N}_{1}^\alpha,\ldots, \tilde{N}_{K}^\alpha\vert N_{1},\ldots,N_{K}\right)}.
\label{eq:Prob-cond-M-der-1}
\end{eqnarray}

Second, by equation  (<ref>) the numerator

\begin{eqnarray}
\delta_{M;\sum_{\mu=1}^K N_{\mu}^\alpha}\Prob\left(N_{1}^\alpha,\ldots, N_{K}^\alpha\vert N_{1},\ldots,N_{K}\right)
&=&\delta_{M;\sum_{\mu=1}^K N_{\mu}^\alpha}\prod_{\mu=1}^K\Prob^\alpha_\mu\left(N^\alpha_\mu\vert N_\mu \right)\nonumber\\
%&=&\delta_{M;\sum_{\mu=1}^K N_{\mu}^\alpha}\prod_{\mu=1}^K {N_\mu\choose N^\alpha_\mu}\,\Prob^{N^\alpha_\mu}(\alpha\vert \mu)  \left[1-\Prob(\alpha\vert \mu)\right]^{N_\mu-N^\alpha_\mu}\nonumber\\
&=&\delta_{M;\sum_{\mu=1}^K N_{\mu}^\alpha}\Prob^{M}(\alpha\vert \mu)  \left[1-\Prob(\alpha\vert \mu)\right]^{N-M}\prod_{\mu=1}^K {N_\mu\choose N^\alpha_\mu}
\end{eqnarray}

and hence

\begin{eqnarray}
\Prob\left(N_{1}^\alpha,\ldots, N_{K}^\alpha\vert N_{1},\ldots,N_{K}; M\right)&=&\frac{\delta_{M;\sum_{\mu=1}^K N_{\mu}^\alpha}\prod_{\mu=1}^K {N_\mu\choose N^\alpha_\mu}}{\sum_{\tilde{N}^\alpha_1=0}^{N_1}\cdots\sum_{\tilde{N}^\alpha_K=0}^{N_K}\delta_{M;\sum_{\mu=1}^K \tilde{N}_{\mu}^\alpha}\prod_{\mu=1}^K {N_\mu\choose \tilde{N}^\alpha_\mu}}\label{eq:Prob-cond-M-der-2}.
\end{eqnarray}

Now the denominator, using the integral representation $\delta_{k;n}=\int_{-\pi}^{\pi} \frac{\rmd \hat{m}}{2\pi}\rme^{\rmi\hat{m}(k-n)}$, is given by

\begin{eqnarray}
\sum_{N^\alpha_1=0}^{N_1}\cdots\sum_{N^\alpha_K=0}^{N_K}\delta_{M;\sum_{\mu=1}^K N_{\mu}^\alpha}\prod_{\mu=1}^K {N_\mu\choose N^\alpha_\mu}&=&\int_{-\pi}^{\pi} \frac{\rmd \hat{m}}{2\pi}\rme^{\rmi\hat{m}M}\prod_{\mu=1}^K\sum_{N^\alpha_\mu=0}^{N_\mu} {N_\mu\choose N^\alpha_\mu}\rme^{-\rmi\hat{m} N_{\mu}^\alpha}\nonumber\\
%&=&\int_{-\pi}^{\pi} \frac{\rmd \hat{m}}{2\pi}\rme^{\rmi\hat{m}M}\prod_{\mu=1}^K2^{N_\mu}\sum_{N^\alpha_\mu=0}^{N_\mu} {N_\mu\choose N^\alpha_\mu}\frac{1}{2^{N_\mu}}\rme^{-\rmi\hat{m} N_{\mu}^\alpha}\nonumber\\
&=&\int_{-\pi}^{\pi} \frac{\rmd \hat{m}}{2\pi}\rme^{\rmi\hat{m}M}\left(1+\rme^{-\rmi \hat{m}}\right)^{\sum_{\mu=1}^KN_\mu}={N\choose M}\label{eq:hyper-norm}
%&=&\int_{-\pi}^{\pi} \frac{\rmd \hat{m}}{2\pi}\rme^{\rmi\hat{m}M}\left(1+\rme^{-\rmi \hat{m}}\right)^{N}={N\choose M}
\end{eqnarray}

which completes the proof.

We note that  marginal of the hypergeometric distribution (<ref>) can be derived in a similar way as the sum in   (<ref>). In particular,  we consider, without loss of generality, the sum

\begin{eqnarray}
\sum_{N^\alpha_2=0}^{N_2}\cdots\sum_{N^\alpha_K=0}^{N_K}\delta_{M;\sum_{\mu=1}^K N_{\mu}^\alpha}\prod_{\mu=1}^K {N_\mu\choose N^\alpha_\mu}
&=&\int_{-\pi}^{\pi} \frac{\rmd \hat{m}}{2\pi}\rme^{\rmi\hat{m}M}{N_1\choose N^\alpha_1}\rme^{-\rmi\hat{m} N_{1}^\alpha}\prod_{\mu=2}^K\sum_{N^\alpha_\mu=0}^{N_\mu} {N_\mu\choose N^\alpha_\mu}\rme^{-\rmi\hat{m} N_{\mu}^\alpha}\nonumber\\
&&={N_1\choose N^\alpha_1}\int_{-\pi}^{\pi} \frac{\rmd \hat{m}}{2\pi}\rme^{\rmi\hat{m}(M-N_{1}^\alpha)}\left(1+\rme^{-\rmi \hat{m}}\right)^{\sum_{\mu=2}^KN_\mu}\nonumber\\
&&={N_1\choose N^\alpha_1}{N-N_1\choose M-N^\alpha_1}
\end{eqnarray}

and hence the marginal of  (<ref>) is given by

\begin{eqnarray}
\Prob\left(N_{\mu}^\alpha\vert N_{\mu}; M\right)&=&\frac{{N_\mu\choose N^\alpha_\mu}{N-N_\mu\choose M-N^\alpha_\mu}}{{N\choose M}}=\frac{{M\choose N^\alpha_\mu}{N-M\choose N_\mu-N^\alpha_\mu}}{{N\choose N_\mu}}\label{eq:hypergeom-univ}.
\end{eqnarray}

§.§ The probability of failure

In random partitions sampled from the probability distributions (<ref>)-(<ref>)  we are interested in   the event

\begin{eqnarray}
%\E(\A)&=&\sum_{\mu=1}^K\Ind\left[N_{\mu}^\alpha(\A)\geq \lfloor A N_{\mu}(\A)\rfloor+1\right]>0
\E&=&\sum_{\mu=1}^K\Ind\left[N_{\mu}^\alpha\geq \lfloor A N_{\mu}\rfloor+1\right]>0
\label{def:E},
\end{eqnarray}

i.e.  in at  least one committee the nodes of colour $\alpha$ exceed a fraction $A\in(0,1)$ of all nodes in the committee. We will call such event  failure and define the probability of failure

\begin{eqnarray}
\delta&=&\Prob\left(\E>0\right)\nonumber\\
\end{eqnarray}

We note that  event $\E=0$ is equivalent to the $\prod_{\mu=1}^K\Ind\left[N_{\mu}^\alpha\leq \lfloor AN_\mu\rfloor\right]=1$ and for  the probability of failure in random partitions  we obtain the following results.

For random partitions  sampled from the probability distribution (<ref>) when  $\Prob(\alpha\vert\mu)<Q(\mu)<1$, where $Q(\mu)=\frac{\lfloor A N_\mu\rfloor+1}{N_\mu}$,  the probability of failure  $\delta$ is bounded as follows

\begin{eqnarray}
1-\prod_{\mu=1}^K\left[1-\frac{\rme^{-N_\mu \mathrm{D}\left(Q(\mu)\vert\vert\Prob(\alpha\vert\mu)\right)}}{\sqrt{8N_\mu Q(\mu)\left(1-Q(\mu)\right)}}\right]\leq\delta\leq 1-\prod_{\mu=1}^K\left[1-\rme^{-N_\mu \mathrm{D}\left(Q(\mu)\vert\vert\Prob(\alpha\vert\mu)\right)}\right]\label{eq:lb-ub},
\end{eqnarray}

where $\mathrm{D}\left(Q\vert\vert P\right)$ with  $Q,P\in(0,1)$ is the Kullback$-$Leibler  (KL) divergence

\begin{eqnarray}
\mathrm{D}\left(Q\vert\vert P\right)&=&Q\log\frac{Q}{P}+(1-Q)\log\frac{1-Q}{1-P}
\end{eqnarray}

which is $0$  when $Q=P$ and is positive semi-definite when $Q\neq P$ <cit.>.

To show this we first, using the probability distribution (<ref>), define the probability[We use the definitions $\left\{N_{\mu}^\alpha\leq \lfloor AN_\mu\rfloor\right\}\equiv N_{1}^\alpha\leq \lfloor AN_1\rfloor,\ldots,N_{K}^\alpha\leq \lfloor AN_K\rfloor$ and $\{N_{\mu}\}\equiv N_{1},\ldots, N_{K}$.]

\begin{eqnarray}
\Prob\left(\left\{N_{\mu}^\alpha\leq \lfloor AN_\mu\rfloor\right\}\vert \left\{N_{\mu}\right\}\right)&=&\sum_{N_{1}^\alpha}\cdots\sum_{N_{K}^\alpha}\Prob\left(N_{1}^\alpha,\ldots, N_{K}^\alpha\vert N_{1},\ldots,N_{K}\right)\prod_{\mu=1}^K\Ind\left[N_{\mu}^\alpha\leq \lfloor AN_\mu\rfloor\right]
\end{eqnarray}

and consider the probability of failure

\begin{eqnarray}
\delta=1- \Prob\left(\left\{N_{\mu}^\alpha\leq \lfloor AN_\mu\rfloor\right\}\vert \left\{N_{\mu}\right\}\right)&=&1-\prod_{\mu=1}^K\sum_{N^\alpha_\mu=0}^{\lfloor A N_\mu\rfloor}\Prob^\alpha_\mu\left(N^\alpha_\mu\vert N_\mu \right)\nonumber\\
&=&1-\prod_{\mu=1}^K\left[1-\Prob(N^\alpha\geq \lfloor A N_\mu\rfloor+1\vert N_\mu)\right]\label{eq:delta-binom},
\end{eqnarray}

where we defined the probability

\begin{eqnarray}
\Prob(N^\alpha\geq \lfloor A N_\mu\rfloor+1\vert N_\mu)&=&\sum_{N^\alpha=\lfloor A N_\mu\rfloor+1}^{N_\mu}\Prob^\alpha_\mu\left(N^\alpha\vert N_\mu \right).
\end{eqnarray}

Second, the probability distribution   $\Prob^\alpha_\mu\left(N^\alpha\vert N_\mu \right)$, which was defined in (<ref>),  is the binomial    and hence it   can be bounded from the above

\begin{eqnarray}
&&\Prob(N^\alpha\geq \lfloor A N_\mu\rfloor+1\vert N_\mu)\leq \rme^{-N_\mu \mathrm{D}\left(Q(\mu)\vert\vert\Prob(\alpha\vert\mu)\right)}\label{eq:binom-tail-ub-1}
\end{eqnarray}

and from the below

\begin{eqnarray}
&&\Prob(N^\alpha\geq \lfloor A N_\mu\rfloor+1\vert N_\mu)
\geq \frac{\rme^{-N_\mu \mathrm{D}\left(Q(\mu)\vert\vert\Prob(\alpha\vert\mu)\right)}}{\sqrt{8N_\mu Q(\mu)\left(1-Q(\mu)\right)}}
\end{eqnarray}

for $\Prob(\alpha\vert\mu)<Q(\mu)<1$, where $Q(\mu)=\frac{\lfloor A N_\mu\rfloor+1}{N_\mu}$,
by the Lemma 4.7.2 in <cit.>. Using these bounds in (<ref>) gives us the lower and upper bound in (<ref>).

We note that a tighter upper bound in (<ref>)  can be obtained by using the recent result

\begin{eqnarray}
\Prob(N^\alpha\geq \lfloor A N_\mu\rfloor+1\vert N_\mu)\leq \frac{1}{1-r(\mu)}\frac{\rme^{-N_\mu \mathrm{D}\left(Q(\mu)\vert\vert\Prob(\alpha\vert\mu)\right)}}{\sqrt{2\pi Q(\mu)\left(1-Q(\mu)\right)N_\mu}},\label{eq:binom-tail-ub-2}
\end{eqnarray}

where $\Prob(\alpha\vert\mu)<Q(\mu)<1$, of  the Theorem 1 in <cit.>. Here the term $\frac{1}{1-r(\mu)}$, where $r(\mu)=\frac{\Prob(\alpha\vert\mu)\left(1-Q(\mu)\right)}{ Q(\mu)\left(1-\Prob(\alpha\vert\mu)\right)}$, is an  upper bound on the sum  $\sum_{k=0}^{\left(1-Q(\mu)\right)N_\mu}r^k(\mu)=(1-r^{\left(1-Q(\mu)\right)N_\mu+1}(\mu))/(1-r(\mu))$.

§.§.§ Saddle-point method

For random partitions generated by the probability distribution (<ref>), i.e. exactly $M$  nodes out of $N$ are of colour $\alpha$, the probability of failure is given by

\begin{eqnarray}
\delta&=&1-\Prob\left(\{N_{\mu}^\alpha\leq \lfloor AN_\mu\rfloor\}\vert \{N_\mu\}, M\right)\label{eq:delta-hyper},
\end{eqnarray}

where the probability

\begin{eqnarray}
\Prob\left(\{N_{\mu}^\alpha\leq \lfloor AN_\mu\rfloor\}\vert \{N_{\mu}\};M\right)
&=&\sum_{N^\alpha_1=0}^{N_1}\cdots\sum_{N^\alpha_K=0}^{N_K}\Prob\left(N_{1}^\alpha,\ldots, N_{K}^\alpha\vert N_{1},\ldots,N_{K}; M\right)\nonumber\\
&&\times\prod_{\mu=1}^K\Ind\left[N_{\mu}^\alpha\leq \lfloor AN_\mu\rfloor\right]\nonumber\\
&=&\frac{\sum_{N^\alpha_1=0}^{N_1}\cdots\sum_{N^\alpha_K=0}^{N_K}\delta_{M;\sum_{\mu=1}^K N_{\mu}^\alpha}\prod_{\mu=1}^K {N_\mu\choose N^\alpha_\mu}\Ind\left[N_{\mu}^\alpha\leq \lfloor AN_\mu\rfloor\right]}{{N\choose M}}\label{eq:1-delta}
\end{eqnarray}

follows from  the result (<ref>) for the distribution (<ref>).

We would like to obtain  a simpler  analytic expression for  $\delta$ but the challenge here is  in computing  the sums  in  (<ref>) efficiently. It is not clear how to do this for any $N$, $M$ and $K$, but in the limit $N\rightarrow\infty$ with  $N_\mu<\infty$ such that $N=\sum_{\mu=1}^K N_\mu$ and $M/N\in (0,1)$ we can obtain  the following result

\begin{eqnarray}
\Prob\left(\{N_{\mu}^\alpha\leq \lfloor AN_\mu\rfloor\}\vert \{N_\mu\}, M\right)&=&\!
\sqrt{\frac{
}  {\sum_{\mu=1}^K\left[\langle(N^\alpha)^2\rangle_{A,Q,N_\mu;}-\langle N^\alpha\rangle^2_{A,Q,N_\mu;}\right]  }}\rme^{N\Psi[Q]}\!+\!O(1/N)\label{eq:SP-Prob-N-large-Q},
\end{eqnarray}

where $P=M/N$ and we defined the function

\begin{eqnarray}
\Psi[Q]&=&D(P\vert\vert Q)+\frac{1}{N}\sum_{\mu=1}^K\log\sum_{N^\alpha=0}^{\lfloor AN_\mu\rfloor} {N_\mu\choose N^\alpha}\,Q^{N^\alpha}[1-Q]^{N_\mu-N^\alpha}\label{def:Psi-Q}
\end{eqnarray}

and average

\begin{eqnarray}
\langle f(N^\alpha)\rangle_{A,Q,N_\mu;}&=&\frac{\sum_{N^\alpha=0}^{\lfloor AN_\mu\rfloor} {N_\mu\choose N^\alpha}Q^{N^\alpha}[1-Q]^{N_\mu-N^\alpha}f(N^\alpha)}{\sum_{N^\alpha=0}^{\lfloor AN_\mu\rfloor} {N_\mu\choose N^\alpha}Q^{N^\alpha}[1-Q]^{N_\mu-N^\alpha}}
\end{eqnarray}

for any function $f(N^\alpha)$.  In above  $Q\in (0,1)$  is the solution of the equation

\begin{eqnarray}
P&=& \frac{1}{N}\sum_{\mu=1}^K
\langle N^\alpha\rangle_{A,Q,N_\mu;}\label{eq:SP-large-N-Q}
\end{eqnarray}

for  $P\leq A$.

In this work,  we will  present only a heuristic  argument that leads to the equation   (<ref>), but we envisage that a more rigorous proof of the latter is also possible. Our approach to computing (<ref>) is to use the saddle-point method of integration, which is quite often used in  statistical physics <cit.> and analytic combinatorics <cit.> to compute moment generating functions,  but first in order to apply  this method we need to represent the sums in  (<ref>) as an integral.  To this end, we rewrite the numerator in (<ref>) as follows

\begin{eqnarray}
&&\sum_{N^\alpha_1=0}^{N_1}\cdots\sum_{N^\alpha_K=0}^{N_K}\delta_{M;\sum_{\mu=1}^K N_{\mu}^\alpha}\prod_{\mu=1}^K {N_\mu\choose N^\alpha_\mu}\Ind\left[N_{\mu}^\alpha\leq \lfloor AN_\mu\rfloor\right]\nonumber\\
\frac{1}{2\pi\rmi}\oint_{\vert z\vert=1}\!\! z^{-M-1+\sum_{\mu=1}^KN_{\mu}^\alpha}\,\rmd z\prod_{\mu=1}^K {N_\mu\choose N^\alpha_\mu}\Ind\left[N_{\mu}^\alpha\leq \lfloor AN_\mu\rfloor\right]\nonumber\\
&&~~~=\frac{1}{2\pi\rmi}\oint_{\vert z\vert=1}\!\left\{
\prod_{\mu=1}^K\sum_{N^\alpha=0}^{N_\mu} {N_\mu\choose N^\alpha}\Ind\left[N^\alpha\leq \lfloor AN_\mu\rfloor\right]z^{N^\alpha}\right\}z^{-M-1}\rmd z\nonumber\\
&&~~~=\frac{1}{2\pi\rmi}\oint_{\vert z\vert=1}\!
\left\{\prod_{\mu=1}^K\phi_A(z\vert N_\mu)\right\}\,z^{-M-1}\rmd z,
%&&~~~=\frac{1}{2\pi\rmi}\oint_{\vert z\vert=1}\rmd z\,\rme^{N\Psi(z)},
\end{eqnarray}

where we used the integral representation   $\delta_{n;m}=\frac{1}{2\pi\rmi}\oint_{\vert z\vert=1} z^{-n-1+m}\,\rmd z$ and defined the function

\begin{eqnarray}
\phi_{A}(z\vert N_\mu)=\sum_{N^\alpha=0}^{\lfloor AN_\mu\rfloor} {N_\mu\choose N^\alpha}z^{N^\alpha}\label{def:phi_A}.
\end{eqnarray}

Second, the denominator

\begin{eqnarray}
{N\choose M}&=&\sum_{N^\alpha_1=0}^{N_1}\cdots\sum_{N^\alpha_K=0}^{N_K}\delta_{M;\sum_{\mu=1}^K N_{\mu}^\alpha}\prod_{\mu=1}^K {N_\mu\choose N^\alpha_\mu}\nonumber\\
\frac{1}{2\pi\rmi}\oint_{\vert z\vert=1}\!\! z^{-M-1+\sum_{\mu=1}^KN_{\mu}^\alpha}\,\rmd z\prod_{\mu=1}^K {N_\mu\choose N^\alpha_\mu}\nonumber\\
&=&\frac{1}{2\pi\rmi}\oint_{\vert z\vert=1}\!
\left\{\prod_{\mu=1}^K\phi_1(z\vert N_\mu)\right\}\,z^{-M-1}\rmd z
%&&~~~=\frac{1}{2\pi\rmi}\oint_{\vert z\vert=1}\rmd z\,\rme^{N\Psi(z)},
\end{eqnarray}

and hence

\begin{eqnarray}
\Prob\left(\{N_{\mu}^\alpha\leq \lfloor AN_\mu\rfloor\}\vert \{N_\mu\}, M\right)&=&\frac{\oint_{\vert z\vert=1}\!
\left\{\prod_{\mu=1}^K\phi_A(z\vert N_\mu)\right\}\,z^{-M-1}\rmd z}{\oint_{\vert z\vert=1}\!
\left\{\prod_{\mu=1}^K\phi_1(z\vert N_\mu)\right\}\,z^{-M-1}\rmd z}.
\end{eqnarray}

Let us  consider the scenario of $N\rightarrow\infty$ with  $N_\mu<\infty$ such that $N=\sum_{\mu=1}^K N_\mu$ and $0<M/N<1$. Then for the integral

\begin{eqnarray}
\oint_{\vert z\vert=1}\!
\left\{\prod_{\mu=1}^K\phi_A(z\vert N_\mu)\right\}\,z^{-M-1}\rmd z
&=&\oint_{\vert z\vert=1}\rmd z\,\rme^{N\Psi_{A}(z)-\log(z)},
\end{eqnarray}

where in above we defined  $P=M/N$ and

\begin{eqnarray}
\Psi_{A}(z)&=&-P\log(z) +\frac{1}{N}\sum_{\mu=1}^K\log\phi_A(z\vert N_\mu),%\label{def:Psi_A}
\end{eqnarray}

we can  try to use the saddle-point integration method <cit.>. Applying this method allows us to write

\begin{eqnarray}
\oint_{\vert z\vert=1}\!\!\rmd z\,\rme^{N\Psi_{A}(z)-\log(z)}
\end{eqnarray}

where in above we used the definition $\ddot{\Psi}_A(z)=\frac{\partial^2}{\partial z^2} \Psi_A(z)$ and $z_0(A)$ is the solution of the equation $\dot{\Psi}_A(z)=0$, which is given by

\begin{eqnarray}
P&=& \frac{1}{N}\sum_{\mu=1}^K
\frac{\sum_{N^\alpha=0}^{\lfloor AN_\mu\rfloor} {N_\mu\choose N^\alpha}z^{N^\alpha}N^\alpha}
{\sum_{N^\alpha=0}^{\lfloor AN_\mu\rfloor} {N_\mu\choose N^\alpha}z^{N^\alpha}}\label{eq:SP-large-N}.
\end{eqnarray}

Thus, for the probability (<ref>) we obtain the following expression

\begin{eqnarray}
\Prob\left(\{N_{\mu}^\alpha\leq \lfloor AN_\mu\rfloor\}\vert \{N_\mu\}, M\right)
\sqrt{\frac{\ddot{\Psi}_{1}(z_0(1))}{\ddot{\Psi}_{A}(z_0(A))}}
\rme^{N[\Psi_{A}(z_0(A))-\Psi_{1}(z_0(1))]}\label{eq:1-delta-SP-large-N}.
\end{eqnarray}

Let us now consider the equation (<ref>). In the latter $0<P<1$ and hence for $z>0$ we can set $z=Q/(1-Q)$, where $0<Q<1$, in this equation, giving us

\begin{eqnarray}
P&=& \frac{1}{N}\sum_{\mu=1}^K
\langle N^\alpha\rangle_{A,Q,N_\mu;}%\label{eq:SP-large-N-Q},
\end{eqnarray}

where we defined the average

\begin{eqnarray}
\langle f(N^\alpha)\rangle_{A,Q,N_\mu;}&=&\frac{\sum_{N^\alpha=0}^{\lfloor AN_\mu\rfloor} {N_\mu\choose N^\alpha}Q^{N^\alpha}[1-Q]^{N_\mu-N^\alpha}f(N^\alpha)}{\sum_{N^\alpha=0}^{\lfloor AN_\mu\rfloor} {N_\mu\choose N^\alpha}Q^{N^\alpha}[1-Q]^{N_\mu-N^\alpha}}.
\end{eqnarray}

Using  $N^\alpha\leq \lfloor AN_\mu\rfloor$ in the equation (<ref>)  gives us the inequality

\begin{eqnarray}
P&\leq& \frac{1}{N}\sum_{\mu=1}^K
\frac{\sum_{N^\alpha=0}^{\lfloor AN_\mu\rfloor} {N_\mu\choose N^\alpha}\,Q^{N^\alpha}[1-Q]^{N_\mu-N^\alpha}\lfloor AN_\mu\rfloor}
{\sum_{N^\alpha=0}^{\lfloor AN_\mu\rfloor} {N_\mu\choose N^\alpha}Q^{N^\alpha}[1-Q]^{N_\mu-N^\alpha}}\nonumber\\
&&~~~~~~~~~~=\frac{1}{N}\sum_{\mu=1}^K\lfloor AN_\mu\rfloor\leq A\label{eq:SP-large-N-Q-ineq}
\end{eqnarray}

and hence equation (<ref>) has a solution only for $P\leq A$.

Furthermore, for $A=1$  the $Q=P$ is the solution of the equation (<ref>)  giving us  $z_0(1)=P/(1-P)$. The  latter can be used to compute  the function

\begin{eqnarray}
\Psi_{1}(z_0(1))&=&-P\log(P/(1-P))-\log(1-P)+\frac{1}{N}\sum_{\mu=1}^K\log\sum_{N^\alpha=0}^{N_\mu} {N_\mu\choose N^\alpha}P^{N^\alpha}[1-P]^{N_\mu-N^\alpha}\nonumber\\
\end{eqnarray}

where $\mathcal{S}(P)=-P\log(P)-(1-P)\log(1-P) $

is Shannon's entropy. For $\Psi_{A}(z_0(A))$ with $z_0(A)=Q/(1-Q)$, where $Q$ is the solution of the equation (<ref>),  we obtain

\begin{eqnarray}
\Psi_{A}(z_0(A))&=&-P\log(Q/(1-Q))-\log(1-Q)\nonumber\\
&&+\frac{1}{N}\sum_{\mu=1}^K\log\sum_{N^\alpha=0}^{\lfloor AN_\mu\rfloor} {N_\mu\choose N^\alpha}\,Q^{N^\alpha}[1-Q]^{N_\mu-N^\alpha}
\end{eqnarray}

and hence the difference

\begin{eqnarray}
\Psi_{A}(z_0(A))-\Psi_{1}(z_0(1))&=&-P\log(Q/(1-Q))-\log(1-Q)\nonumber\\
&&~~~~~~~+\frac{1}{N}\sum_{\mu=1}^K\log\sum_{N^\alpha=0}^{\lfloor AN_\mu\rfloor} {N_\mu\choose N^\alpha}\,Q^{N^\alpha}[1-Q]^{N_\mu-N^\alpha}-\mathcal{S}(P)\nonumber\\
&=&D(P\vert\vert Q)+\frac{1}{N}\sum_{\mu=1}^K\log\sum_{N^\alpha=0}^{\lfloor AN_\mu\rfloor} {N_\mu\choose N^\alpha}\,Q^{N^\alpha}[1-Q]^{N_\mu-N^\alpha}.
\end{eqnarray}

Let us consider now the derivative

\begin{eqnarray}
\ddot{\Psi}_{A}(z)&=&\frac{P}{z^2} +\frac{1}{N}\sum_{\mu=1}^K\frac{\partial^2}{\partial z^2}\log\phi_A(z\vert N_\mu)\nonumber\\
&=&\frac{P}{z^2} +\frac{1}{N}\sum_{\mu=1}^K\left[\frac{\ddot{\phi}_A(z\vert N_\mu)}{\phi_A(z\vert N_\mu)}-\left\{\frac{\dot{\phi}_A(z\vert N_\mu)}{\phi_A(z\vert N_\mu)}\right\}^2\right]\label{eq:d2Psi},
\end{eqnarray}

\begin{eqnarray}
\dot{\phi}_{A}(z\vert N_\mu)=\sum_{N^\alpha=0}^{\lfloor AN_\mu\rfloor} {N_\mu\choose N^\alpha}z^{N^\alpha-1}N^\alpha\label{def:dphi}.
\end{eqnarray}

\begin{eqnarray}
\ddot{\phi}_{A}(z\vert N_\mu)=\sum_{N^\alpha=0}^{\lfloor AN_\mu\rfloor} {N_\mu\choose N^\alpha}z^{N^\alpha-2}N^\alpha(N^\alpha-1)\label{def:d2phi}.
\end{eqnarray}

For $z=Q/(1-Q)$, where $Q$ is a solution of the equation (<ref>), above gives us

\begin{eqnarray}
\ddot{\Psi}_{A}(z)&=&\left(\frac{1-Q}{Q}\right)^2\frac{1}{N}\sum_{\mu=1}^K\left[\langle(N^\alpha)^2\rangle_{A,Q,N_\mu;}-\langle N^\alpha\rangle^2_{A,Q,N_\mu;}\right]\label{eq:d2Psi-Q}
\end{eqnarray}

and for $z=P/(1-P)$ it gives us

\begin{eqnarray}
\ddot{\Psi}_{1}(z)&=&\left(\frac{1-P}{P}\right)^2\frac{1}{N}\sum_{\mu=1}^K\left[\langle(N^\alpha)^2\rangle_{1,P,N_\mu;}-\langle N^\alpha\rangle^2_{1,P,N_\mu;}\right]\nonumber\\
&=&\left(\frac{1-P}{P}\right)^2\frac{1}{N}\sum_{\mu=1}^KN_\mu P(1-P)=\frac{\left(1-P\right)^3}{P}\label{eq:d2Psi_1}.
\end{eqnarray}

Hence using all of the above results in (<ref>) gives us the equation (<ref>).

§.§.§ The union bound

The failure event (<ref>) is equivalent to the union

$$\cup_{\mu=1}^K\left\{N_{\mu}^\alpha(\A)\geq \lfloor AN_{\mu}(\A)\rfloor+1\right\}$$
and hence the probability of failure $\delta=\Prob\left(\cup_{\mu=1}^K\left\{N_{\mu}^\alpha\geq \lfloor AN_{\mu}\rfloor+1\right\}\right)$. The latter  can be exploited to derive the following

For random partitions  sampled from the probability distribution (<ref>) when  $\Prob(\alpha\vert\mu)<Q(\mu)<1$, where $Q(\mu)=\frac{\lfloor A N_\mu\rfloor+1}{N_\mu}$,  the probability of failure

\begin{eqnarray}
%\Prob\left(\cup_{\mu=1}^K\left\{N_{\mu}^\alpha\geq \lfloor AN_{\mu}\rfloor+1\right\}\right)
\delta&\leq&\sum_{\mu=1}^K \rme^{-N\Phi(\Prob(\alpha, \mu),Q(\mu))}\label{eq:Prob-U-ub},
\end{eqnarray}

\begin{eqnarray}
\Phi(\Prob(\alpha, \mu),Q(\mu))&=&-\log\left(\Prob(\mu)\,\rme^{-\mathrm{D}\left(Q(\mu)\vert\vert\Prob(\alpha\vert\mu)\right)}+1-\Prob(\mu)\right).\label{def:Phi}
\end{eqnarray}

First, by Boole's inequality, also known as  the union bound,  we have that

\begin{eqnarray}
\Prob\left(\cup_{\mu=1}^K\left\{N_{\mu}^\alpha\geq \lfloor AN_{\mu}(\A)\rfloor+1\right\}\right)
&\leq&\sum_{\mu=1}^K\Prob\left(N_{\mu}^\alpha\geq \lfloor AN_{\mu}\rfloor+1\right)\label{eq:Boole-ineq}
\end{eqnarray}

and hence the probability of failure

\begin{eqnarray}
\delta &\leq&\sum_{\mu=1}^K\Prob\left(N_{\mu}^\alpha\geq \lfloor AN_{\mu}\rfloor+1\right)\label{eq:Boole-ineq-delta}.
\end{eqnarray}

Second, using the result (<ref>) for the distribution (<ref>) we obtain the probability

\begin{eqnarray}
\Prob\left(N^\alpha_\mu\geq \lfloor AN_{\mu}\rfloor+1\right)&=&\sum_{N_\mu=0}^N\sum_{N^\alpha_\mu=\lfloor AN_{\mu}\rfloor+1}^{N_\mu}\Prob^\alpha\!\left(N_\mu,N^\alpha_\mu\vert N\right)\nonumber\\
&=&\sum_{N_\mu=0}^N\Prob_\mu\!\left(N_\mu\vert N\right)\sum_{N^\alpha_\mu=\lfloor AN_{\mu}\rfloor+1}^{N_\mu}\Prob^\alpha_\mu\!\left(N^\alpha_\mu\vert N_\mu \right),
\end{eqnarray}

where in above we used that

$\Prob^\alpha\!\left(N_\mu,N^\alpha_\mu\vert N\right)$, defined in  (<ref>), is the marginal of (<ref>).

Now the probability

\begin{eqnarray}
\Prob\left(N^\alpha_\mu\geq \lfloor AN_{\mu}\rfloor+1\vert N_{\mu}\right)&=&\sum_{N^\alpha_\mu=\lfloor AN_{\mu}\rfloor+1}^{N_\mu}\Prob^\alpha_\mu\!\left(N^\alpha_\mu\vert N_\mu \right)\leq \rme^{-N_\mu \mathrm{D}\left(Q(\mu)\vert\vert\Prob(\alpha\vert\mu)\right)}
\end{eqnarray}

by the Lemma 4.7.2 in <cit.> for $\Prob(\alpha\vert\mu)<Q(\mu)<1$, where $Q(\mu)=\frac{\lfloor AN_{\mu}\rfloor+1}{N_{\mu}}$, and hence we obtain

\begin{eqnarray}
\Prob\left(N^\alpha_\mu\geq \lfloor AN_{\mu}\rfloor+1\right)&\leq&\sum_{N_\mu=0}^N\Prob_\mu\!\left(N_\mu\vert N\right)\rme^{-N_\mu \mathrm{D}\left(Q(\mu)\vert\vert\Prob(\alpha\vert\mu)\right)}\nonumber\\
&&=\rme^{-N\Phi(\Prob(\alpha, \mu),Q(\mu))},
\end{eqnarray}

which can be used to bound the sum in (<ref>) and hence giving us the inequality (<ref>).

We note that a tighter, but slightly more complicated, upper bound on $\delta$ can be obtained if we use (<ref>) instead of (<ref>) in the proof. Furthermore, we obtained a less tight and slightly simpler upper bound in the following

For random partitions generated  by the probability distribution (<ref>) when  $\Prob(\alpha\vert\mu)<Q(\mu)<1$, where $Q(\mu)=\frac{\lfloor A N_\mu\rfloor+1}{N_\mu}$,  the probability of failure

\begin{eqnarray}
\delta&\leq&\sum_{\mu=1}^K \rme^{-N\Phi(\Prob(\alpha, \mu),Q(\mu))}\leq\sum_{\mu=1}^K \rme^{-N\Prob(\mu)\,\phi(\Prob(\alpha\vert \mu),Q(\mu))}\label{eq:Prob-U-ub-2},
\end{eqnarray}

where $\phi(\Prob(\alpha\vert \mu),Q(\mu))=1-\rme^{-\mathrm{D}\left(Q(\mu)\vert\vert\Prob(\alpha\vert\mu)\right)}$.

Using  $\log(x)\leq x-1$ in the function (<ref>) gives us

\begin{eqnarray}
-\Phi(\Prob(\alpha, \mu),Q(\mu))&\leq&\Prob(\mu)\left[\rme^{-\mathrm{D}\left(Q(\mu)\vert\vert\Prob(\alpha\vert\mu)\right)}-1\right]\nonumber\\
&&~~~~~~~~~~~~~~~~~~~~~~=-\Prob(\mu)\phi(\Prob(\alpha\vert \mu),Q(\mu))
\end{eqnarray}

and hence using above in (<ref>) gives us the second inequality in (<ref>).

Finally,  a slight modification of the above proof also gives us the following

For random partitions generated  by the probability distribution (<ref>) when  $\Prob(\alpha\vert\mu)<Q(\mu)<1$, where $Q(\mu)=\frac{\lfloor A N_\mu\rfloor+1}{N_\mu}$,  the probability of failure

\begin{eqnarray}
\delta
&\leq&\sum_{\mu=1}^K \rme^{-N_\mu \mathrm{D}\left(Q(\mu)\vert\vert\Prob(\alpha\vert\mu)\right)}.\label{eq:Prob-U-ub-3}
\end{eqnarray}

To show this we exploit that the marginal of the probability distribution (<ref>), i.e. the result for  (<ref>), is the binomial  (<ref>). Thus if we replace $\Prob_\mu\!\left(N_\mu\vert N\right)$ in the proof of Theorem <ref> by the $\delta_{N_\mu;\tilde{N}_\mu}$, where $\sum_{\mu=1}^K\tilde{N}_\mu=N$, we obtain (<ref>).

We note that for the hypergeometric distribution (<ref>)  the probability of failure

\begin{eqnarray}
\delta
&\leq&\sum_{\mu=1}^K \sum_{N^\alpha_\mu=\lfloor AN_{\mu}\rfloor+1}^{N_\mu}\Prob\left(N_{\mu}^\alpha\vert N_{\mu}; M\right)\label{eq:hyper-U-b-exact}\\
&&\leq \sum_{\mu=1}^K\rme^{-N_\mu \mathrm{D}\left(Q(\mu)\vert\vert M/N\right)}\label{eq:hyper-U-b},
\end{eqnarray}

where $M$ is the number of nodes of colour $\alpha$. The first inequality in above is an    application of (<ref>) with  the marginal (<ref>)  and the second
inequality is a consequence of  Hoeffding bound <cit.> <cit.>. The union bounds (<ref>), (<ref>) and (<ref>) suggest that for $K<\infty$ the probability of failure $\delta\rightarrow0$  if we assume that $N_\mu/N>0$ for all $\mu$ as $N\rightarrow\infty$.  However, it is easy to construct a partition for each of these bounds  such that the bound exceeds unity. Here it is interesting to compare the union bound in (<ref>) with the upper bound in (<ref>) which was derived using a different approach.  The latter is bounded above by unity,  but  the former can be above unity  suggesting that  (<ref>) is a looser bound on $\delta$ which is  confirmed by the following

For random partitions generated  by the probability distribution (<ref>) when  $\Prob(\alpha\vert\mu)<Q(\mu)<1$, where $Q(\mu)=\frac{\lfloor A N_\mu\rfloor+1}{N_\mu}$,  the probability of failure

\begin{eqnarray}
\delta&\leq& 1-\prod_{\mu=1}^K\left[1-\rme^{-N_\mu \mathrm{D}\left(Q(\mu)\vert\vert\Prob(\alpha\vert\mu)\right)}\right]
\leq\sum_{\mu=1}^K \rme^{-N_\mu \mathrm{D}\left(Q(\mu)\vert\vert\Prob(\alpha\vert\mu)\right)}.\label{eq:Prob-U-ub-4}
\end{eqnarray}

To show this we consider the difference

\begin{eqnarray}
\Delta_K&=& 1-\prod_{\mu=1}^K\left[1-W(\mu)\right]
-\sum_{\mu=1}^K W(\mu),\label{eq:ub-diff}
\end{eqnarray}

where we defined the “weight” $W(\mu)=\rme^{-N_\mu \mathrm{D}\left(Q(\mu)\vert\vert\Prob(\alpha\vert\mu)\right)}$. The latter, because of $\mathrm{D}\left(Q(\mu)\vert\vert\Prob(\alpha\vert\mu)\right)\geq 0$, belongs to the interval  $(0,1]$ for any finite $N_\mu$.
We note that $\Delta_1=0$ and $\Delta_2<0$. Let us assume that $\Delta_{K-1}\leq 0$ and consider $\Delta_{K}$ as follows

\begin{eqnarray}
\Delta_K&=& 1-\left[1-W(K)\right]\prod_{\mu=1}^{K-1}\left[1-W(\mu)\right]
-\sum_{\mu=1}^{K-1} W(\mu)-W(K)\nonumber\\
&=&\Delta_{K-1}-  W(K)\left\{1-\prod_{\mu=1}^{K-1}\left[1-W(\mu)\right]
\right\}.
\end{eqnarray}

Now from the $\prod_{\mu=1}^{K-1}\left[1-W(\mu)\right]\leq1$ and  $\Delta_{K-1}\leq0$  follows that $\Delta_{K}\leq0$ which, by induction on $K$, completes the proof.

§ APPLICATION

We consider $N$ nodes in the  blockchain network where a fraction of nodes, $P$,  is adversarial.  We assume that to improve its scalability, this network is split into $K$  shards (or committees). The latter allows the processing of all transactions, encoded  in the blockchain, in a distributed way. However, the security of the whole network can be only  guaranteed, with  probability $1-\delta$, if $P$ is not exceeding a certain threshold $A$ in each committee.    The probability of failure $\delta$ considered in section  <ref> corresponds to
either the case when the number of adversarial nodes  is $N\times P$ on average, where $\delta$ is given by the equation (<ref>) with $\Prob(\alpha\vert\mu)=P$,  or to the case when it is exactly $N\times P$, where $\delta$ is  given by the equation (<ref>) with $P=M/N$.  In the latter case, the probability $\delta$  was  computed, for  $N=nK$ nodes distributed into $K$ committees, only    by simulations <cit.>, and the former case, to the best of our knowledge, has not been considered. Here we consider both cases for the number of nodes $N=nK+r$, where $n\in\mathbb{N}$ and $r\in\{0,\ldots,K-1\}$,  with $n$ and $n+1$  nodes distributed, respectively,   into  $K-r$ and   $r$  committees.

The committee size $n$ as a function of the number of committees $K$ plotted for the probability of failure $\delta=10^{-3}$ when $A=1/3$ (fraction of a committee)  and $P=1/4$ (fraction of adversarial nodes). The  number of nodes $N=nK$ is increasing from left to right. The black solid  line is obtained by  solving  equation (<ref>), which assumes $N\times P$ adversarial nodes on average, numerically.  The red and blue solid lines  correspond to, respectively, the upper   and  lower bounds in (<ref>).  The red and black dashed lines  were obtained from, respectively,  the upper bound (<ref>) and asymptotic result (<ref>)  for (<ref>).  The latter assumes exactly $N\times P$ of adversarial nodes.

First, we use the exact equation (<ref>), the asymptotic result (<ref>)  for (<ref>), and the upper bound (<ref>)  to find the committee size $n$ given the  probability of failure $\delta$ and number of committees $K$. We find that $n$ computed from the probability (<ref>) is an upper bound on $n$ computed from the probability (<ref>) as can be seen in Figure <ref>. The latter  is consistent with  our observation, that the probability (<ref>) is an upper bound for (<ref>), in simulations as can be seen  in the Figures <ref> and <ref>.  Furthermore,  for $\Prob(\alpha\vert\mu)=P$ and  $N=nK$, using  the bounds in (<ref>), we obtain

\begin{eqnarray}
1-\left[1-\frac{\rme^{-n \mathrm{D}\left(Q_n\vert\vert P\right)}}{\sqrt{8n\,Q_n\left(1-Q_n\right)}}\right]^{K}\leq\delta\leq 1-\left[1-\rme^{-n \mathrm{D}\left(Q_n\vert\vert P\right)}\right]^{K}\label{eq:lb-ub-n},
\end{eqnarray}

where we have defined $Q_n=\frac{\lfloor An\rfloor+1}{n}$.   The above inequalities  can be used to obtain bounds on the committee size $n$, given the probability of failure $\delta$ and  a number of committees $K$. The upper bound

\begin{eqnarray}
n< \frac{-\log\left(1-\left(1-\delta\right)^{1/K}\right)}{\mathrm{D}\left(A\vert\vert P\right)} \label{eq:n-ub}
\end{eqnarray}

follows from the inequality

\begin{eqnarray}
1-\left[1-\rme^{-n \mathrm{D}\left(Q_n\vert\vert P\right)}\right]^{K}
< 1-\left[1-\rme^{-n \mathrm{D}\left(A\vert\vert P\right)}\right]^{K},
\end{eqnarray}

where to obtain above we used that $A<Q_n\leq A+1/n$ and   that $\mathrm{D}\left(P+\epsilon\vert\vert P\right)$ is monotonic increasing function of
$\epsilon$ when $2P-1<\epsilon\leq1-P$. Also the function

\begin{eqnarray}
\mathrm{D}\left(P+\epsilon\vert\vert P\right)+\frac{1}{2n}\log\left((P+\epsilon)(1-P-\epsilon)\right)
%\frac{\rme^{-n \mathrm{D}\left(P+\epsilon\vert\vert P\right)}}{\sqrt{8n\,P+\epsilon\left(1-P-\epsilon\right)}}
\end{eqnarray}

is monotonic increasing in
$\epsilon$ when  $2P-1<\epsilon<1/2-P$ and hence $f(Q_n)\leq f(A+1/n)\leq \tilde{f}(A)$, where $\tilde{f}(A)=\max_n f(A+1/n)$. Using the latter in the lower bound in (<ref>) gives us

\begin{eqnarray}
&&1-\left[1-\frac{\rme^{-n \tilde{f}(A)}}{\sqrt{8n}}\right]^{K}\leq1-\left[1-\frac{\rme^{-n \mathrm{D}\left(Q_n\vert\vert P\right)}}{\sqrt{8n\,Q_n\left(1-Q_n\right)}}\right]^{K}\leq\delta
\end{eqnarray}

and from above, using $\log(x)\geq 1-1/x$ for $x>0$, we obtain the lower bound

\begin{eqnarray}
\frac{1-\log\left(8\right)-
2\log\left(1-\left(1-\delta\right)^{1/K}\right)}{2\tilde{f}(A)+1}\leq n\label{eq:n-lb}.
\end{eqnarray}

Now for $K\rightarrow\infty$, with  $\delta\in(0,1)$, we have

\begin{eqnarray}
-\log\left(1-\left(1-\delta\right)^{1/K}\right)&=& -\log  \left( -\log  \left( 1-\delta \right)  \right) +\log  \left( K
\right)\nonumber\\
&&-{\frac {\log  \left( 1-\delta \right) }{2\,K}}-{\frac {
\log^2\!  \left( 1-\delta \right) }{24\,{K}^{2}}}\nonumber\\
\frac {  \log^4\!  \left( 1-\delta \right)}{2880\,{K}^{
\end{eqnarray}

and for $\delta\rightarrow0$, with $K<\infty$, we have

\begin{eqnarray}
-\log\left(1-\left(1-\delta\right)^{1/K}\right)&=&\log  \left( K \right)+\log  \left( 1/\delta \right) -\frac {  K-1
}{2\,K}\delta +O(\delta^2)\label{eq:small-delta-expansion}.
\end{eqnarray}

Thus both the upper bound in (<ref>) and the lower bound in (<ref>)  grow at most logarithmically in $K$  (or $1/\delta$) as  $K\rightarrow\infty$ (or as $\delta\rightarrow0$).   The latter suggests that to sustain the  same probability of failure $\delta$ (or the same number of committees $K$) the  committee size $n$ has to be increased   logarithmically with $K$ (or $1/\delta$) as can be seen in Figure <ref>.

The probability of failure, $\delta$,  as a function of the number of committees, $K$, computed for the parameters $A=1/3$ (fraction of a committee) and $P=1/4$ (fraction of adversarial or Byzantine nodes).
Left: The red  $+$ and $\times$ symbols are results of simulations, obtained for $N=10^3$, where $N=nK+r$, nodes over   $10^6$ random samples, which assume the  $N\times P$  adversarial nodes, respectively, on average and exactly.
The black solid line, going through the $+$ symbols,  connects exact values  computed numerically from  the equation (<ref>). The black  dashed line corresponds to the asymptotic result (<ref>) for (<ref>). The red dashed line  corresponds to  the  upper bound (<ref>). Right: The red dotted and blue solid lines correspond to, respectively, the upper and lower bounds in (<ref>). The upper bound in the latter was computed using (<ref>).

The probability of failure, $\delta$,  as a function of the number of committees, $K$, computed for the parameters $A=1/3$ (fraction of a committee) and $P=1/4$ (fraction of adversarial or Byzantine nodes).
Left: The red  $+$ and $\times$ symbols are results of simulations, obtained for $N=10^4$, where $N=nK+r$, nodes over   $10^6$ random samples, which assume the  $N\times P$  adversarial nodes, respectively, on average and exactly.
The black solid line, going through the $+$ symbols,  connects exact values  computed numerically from  the equation (<ref>).

The black  dashed line corresponds to the asymptotic result (<ref>) for (<ref>).The red dashed line  corresponds to  the  upper bound (<ref>). Right:

The red  dotted  and blue solid lines correspond to, respectively, the upper and lower bounds in (<ref>). The upper bound in the latter was computed using (<ref>).

Second, we test our analytic results  against  numerical experiments and we find, up to statistical variability and numerical accuracy, a good agreement  as can be seen in Figures <ref> and <ref>.   We also observe   that  the  probability   of failure (<ref>)  is   bounded above by the probability (<ref>). This is expected as  in the latter the number of adversarial nodes is a random number
and in the former, this number is  fixed.  However the difference between the probabilities  (<ref>) and (<ref>)
is vanishing (see Figures <ref>-<ref>) when  both  probabilities approach unity with increasing $K$.

Finally, we note that insights drawn  from  the above results can be used to design an algorithm  which for a given number of nodes $N$  finds the maximum the number of committees $K$ such that the probability of failure is less than (or equal) to  a given $\delta$. The latter will reduce the computational complexity in the  sharded blockchain, which is proportional to the size of a committee $n$,
without  compromising its safety <cit.>. The possibly simplest way to implement such an algorithm is to use  the probability  of failure (<ref>) and  $N=nK+r$ nodes with $n$ and $n+1$ nodes assigned, respectively, to the  $K-r$ and $r$ committees. The latter ensures that  for any $N$ the  optimization problem is essentially one-dimensional, where this  dimension is  $K$, and the former allows  the computation of a “current” probability of failure, which is  an elementary step  of  this optimization,  to be efficient.  We note that here we  assume that there are $N\times P$ adversarial nodes on average and using   this algorithm when there are  exactly $N\times P$ of adversarial   nodes  would give us  a larger committee size. However, the difference in committee sizes  between the latter and the former becomes  negligible   as $N$ is increasing as can be seen in  Figure <ref>. The description and  pseudocode of one  possible variant for  such an algorithm are  provided in Appendix <ref>.

Comparing analytic results of this work with typical  bounds from the  literature. Here the same data  as in the Figure <ref> is used.

Left: The red  $+$ and $\times$ symbols are results of simulations

The black solid line, going through the $+$ symbols,  connects exact values  computed numerically from  the equation (<ref>).

The black dashed line corresponds to the asymptotic result (<ref>) for (<ref>). The red dashed line corresponds to  the union bound <cit.>, i.e. the equation   (<ref>), which uses  hypergeometric distribution. The red solid line corresponds to the union bound which uses   binomial distribution <cit.> Right: The red  dotted  and blue solid lines correspond to, respectively, the upper and lower bounds in (<ref>). The upper bound in the latter was computed using (<ref>).

§ CONCLUSION AND FUTURE WORK

In this work, we have studied random partitions of networks. We introduced a very general probabilistic framework  and used this framework  to construct  probability distributions of  random partitions.  We showed that these distributions admit exact and explicit expressions which facilitated a study of the probability of failure. For the latter, we obtained exact expressions, bounds, and  asymptotic results.  For the  sharding of blockchains, these results offer significant  analytic  and algorithmic improvements,  but this work still leaves many questions open.

In particular,  we  have established  that  the probability of failure (<ref>) is  an  upper bound on  the probability  (<ref>) but this  was done numerically and we envisage that to show this  in a more rigorous way is also possible. The other question is the relation between the asymptotic result (<ref>)  for the probability of failure (<ref>) and the upper bound (<ref>). Here, it is surprising that this bound is very accurate  when the   number of committees $K$  is small but for larger $K$  it also approaches the asymptotic result which has quite a different functional form. We note that the bound (<ref>) uses univariate hypergeometric distribution which can be difficult to compute numerically and hence for practical applications  a  simpler bound,  but  much tighter than (<ref>), is more desirable.

The authors would like to thank the Nomos team for their invaluable assistance and very enlightening discussions that greatly enriched this work.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Ali et al(2019)]
authorpersonMuhammad Salek Ali,
personMassimo Vecchio, personMiguel Pincheira,
personKoustabh Dolui, personFabio Antonelli, and
personMubashir Husain Rehmani. year2019.
Applications of Blockchains in the Internet of
Things: A Comprehensive Survey.
journalIEEE Communications Surveys & Tutorials
volume21, number2 (year2019),

authorpersonRobert B Ash.
booktitleInformation theory.
publisherDover Publications, addressNew York.

authorpersonAlex Baczkowski.
booktitleFundamentals: What’s the Deal With
Rotating Committees?
Aleph Zero.

Retrieved Feb 19, 2023 from

[Blasch et al(2019)]
authorpersonErik Blasch, personRonghua Xu,
personYu Chen, personGenshe Chen, and
personDan Shen. year2019.
Blockchain Methods for Trusted Avionics Systems.
In booktitle2019 IEEE National Aerospace and Electronics
Conference (NAECON). pages192–199.

[Buterin et al(2020)]
authorpersonVitalik Buterin, personDiego
Hernandez, personThor Kamphefner, personKhiem Pham,
personZhi Qiao, personDanny Ryan,
personJuhyeok Sin, personYing Wang, and
personYan X Zhang. year2020.
titleCombining GHOST and Casper.

[Cao et al(2016)]
authorpersonTien-Dung Cao, personTran-Vu
Pham, personQuang-Hieu Vu, personHong-Linh Truong,
personDuc-Hung Le, and personSchahram Dustdar.
MARSA: A marketplace for realtime human sensing
journalACM Transactions on Internet Technology
(TOIT) volume16, number3 (year2016),

authorpersonV. Chvátal.
The tail of the hypergeometric distribution.
journalDiscrete Mathematics volume25,
number3 (year1979), pages285–287.

[Cover and Thomas(2012)]
authorpersonThomas M Cover and personJoy A
Thomas. year2012.
booktitleElements of information theory.
publisherJohn Wiley & Sons, addressNew York.

[Dang et al(2019)]
authorpersonHung Dang, personTien Tuan Anh
Dinh, personDumitrel Loghin, personEe-Chien Chang,
personQian Lin, and personBeng Chin Ooi.
Towards scaling blockchain systems via sharding.
In booktitleProceedings of the 2019 international conference
on management of data. publisherAssociation for Computing
Machinery, addressNew York, pages123–140.

[El-Hasnony et al(2021)]
authorpersonIbrahim M El-Hasnony,
personReham R Mostafa, personMohamed Elhoseny, and
personSherif I Barakat. year2021.
Leveraging mist and fog for big data analytics in
IoT environment.
journalTransactions on Emerging Telecommunications
Technologies volume32, number7
(year2021), pagese4057.

authorpersonMV Fedoryuk.
booktitleThe saddle-point method.
publisherNauka, addressMoscow.

authorpersonGuido Carlo Ferrante.
Bounds on Binomial Tails With Applications.
journalIEEE Transactions on Information Theory
volume67, number12 (year2021),

[Fischer et al(1985)]
authorpersonMichael J. Fischer,
personNancy A. Lynch, and personMichael S.
Paterson. year1985.
Impossibility of Distributed Consensus with One
Faulty Process.
journalJ. ACM volume32,
number2 (dateApril year1985),

[Flajolet and Sedgewick(2009)]
authorpersonPhilippe Flajolet and
personRobert Sedgewick. year2009.
booktitleAnalytic combinatorics.
publisherCambridge University Press,

[Fraga-Lamas and Fernández-Caramés(2019)]
authorpersonPaula Fraga-Lamas and
personTiago M Fernández-Caramés.
A review on blockchain technologies for an advanced
and cyber-resilient automotive industry.
journalIEEE access  volume7
(year2019), pages17578–17598.

[Garcia Lopez et al(2015)]
authorpersonPedro Garcia Lopez,
personAlberto Montresor, personDick Epema,
personAnwitaman Datta, personTeruo Higashino,
personAdriana Iamnitchi, personMarinho Barcellos,
personPascal Felber, and personEtienne Riviere.
Edge-Centric Computing: Vision and Challenges.
journalSIGCOMM Comput. Commun. Rev.
volume45, number5 (datesep
year2015), pages37–42.

[Guo et al(2020)]
authorpersonYangrui Guo, personQiandong
Yang, personHui Zhou, personWeiQiang Lu, and
personSheng Zeng. year2020.
titleSyetem and Methods for Selection and Utilizing a
Committee of Validator Nodes in a Distributed System.
howpublishedCypherium Blockchain.

[Hafid et al(2020a)]
authorpersonAbdelatif Hafid,
personAbdelhakim Senhaji Hafid, and personMustapha
Samih. year2020a.
A novel methodology-based joint hypergeometric
distribution to analyze the security of sharded blockchains.
journalIEEE Access  volume8
(year2020), pages179389–179399.

[Hafid et al(2020b)]
authorpersonAbdelatif Hafid,
personAbdelhakim Senhaji Hafid, and personMustapha
Samih. year2020b.
Scaling blockchains: A comprehensive survey.
journalIEEE Access  volume8
(year2020), pages125244–125262.

authorpersonWassily Hoeffding.
Probability Inequalities for Sums of Bounded Random
journalJ. Amer. Statist. Assoc.
volume58, number301 (year1963),

[Jalalzai et al(5555)]
authorpersonM. Jalalzai, personC. Feng,
personC. Busch, personG. Richard III, and
personJ. Niu. year5555.
The Hermes BFT for Blockchains.
journalIEEE Transactions on Dependable and Secure
Computing number01 (datesep year5555),

[Jalalzai et al(2019)]
authorpersonM. M. Jalalzai, personC.
Busch, and personG. G. Richard.
Proteus: A Scalable BFT Consensus Protocol for
Blockchains. In booktitle2019 IEEE International Conference
on Blockchain (Blockchain). pages308–313.

[Jalalzai et al(2020)]
authorpersonMohammad M. Jalalzai,
personJianyu Niu, personChen Feng, and
personFangyu Gai. year2020.
titleFast-HotStuff: A Fast and Resilient HotStuff

[Kang et al(2018)]
authorpersonJiawen Kang, personRong Yu,
personXumin Huang, and personYan Zhang.
Privacy-Preserved Pseudonym Scheme for Fog
Computing Supported Internet of Vehicles.
journalIEEE Transactions on Intelligent
Transportation Systems  volume19 (year2018),

[Khodadadi et al(2015)]
authorpersonFarzad Khodadadi,
personRodrigo N Calheiros, and personRajkumar
Buyya. year2015.
A data-centric framework for development and
deployment of internet of things applications in clouds. In
booktitle2015 IEEE Tenth International Conference on
Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP).
IEEE, pages1–6.

[Kokoris-Kogias et al(2018)]
authorpersonEleftherios Kokoris-Kogias,
personPhilipp Jovanovic, personLinus Gasser,
personNicolas Gailly, personEwa Syta, and
personBryan Ford. year2018.
Omniledger: A secure, scale-out, decentralized
ledger via sharding. In booktitle2018 IEEE Symposium on
Security and Privacy (SP). IEEE, pages583–598.

[Lamport et al(1982)]
authorpersonLeslie Lamport, personRobert
Shostak, and personMarshall Pease.
The Byzantine Generals Problem.
journalACM Trans. Program. Lang. Syst.
volume4, number3 (dateJuly
year1982), pages382–401.

[Li et al(2017)]
authorpersonXin Li, personHuazhe Wang,
personYe Yu, and personChen Qian.
An IoT data communication framework for
authenticity and integrity. In booktitleProceedings of the
Second International Conference on Internet-of-Things Design and
Implementation. pages159–170.

[Luu et al(2016)]
authorpersonLoi Luu, personViswesh
Narayanan, personChaodong Zheng, personKunal Baweja,
personSeth Gilbert, and personPrateek Saxena.
A Secure Sharding Protocol For Open Blockchains.
In booktitleProceedings of the 2016 ACM SIGSAC Conference on
Computer and Communications Security (Vienna, Austria)
(seriesCCS '16). publisherACM,
addressNew York, NY, USA, pages17–30.

[Michelin et al(2018)]
authorpersonRegio A Michelin, personAli
Dorri, personMarco Steger, personRoben C Lunardi,
personSalil S Kanhere, personRaja Jurdak, and
personAvelino F Zorzo. year2018.
SpeedyChain: A framework for decoupling data from
blockchain for smart cities. In booktitleProceedings of the
15th EAI international conference on mobile and ubiquitous systems:
Computing, networking and services. pages145–154.

[Nikouei et al(2018)]
authorpersonSeyed Yahya Nikouei,
personRonghua Xu, personDeeraj Nagothu,
personYu Chen, personAlexander Aved, and
personErik Blasch. year2018.
Real-Time Index Authentication for Event-Oriented
Surveillance Video Query using Blockchain. In booktitle2018
IEEE International Smart Cities Conference (ISC2). pages1–8.

authorpersonHidetoshi Nishimori.
booktitleStatistical physics of spin glasses and
information processing: an introduction. Vol. volume111.
publisherOxford University Press,

[Salimitari et al(2020)]
authorpersonMehrdad Salimitari, personMainak
Chatterjee, and personYaser P. Fallah.
A survey on consensus methods in blockchain for
resource-constrained IoT networks.
journalInternet of Things  volume11
(year2020), pages100212.

[Tennakoon and Gramoli(2022)]
authorpersonDeepal Tennakoon and
personVincent Gramoli. year2022.
Dynamic blockchain sharding. In
booktitle5th International Symposium on Foundations and
Applications of Blockchain 2022 (FAB 2022). Schloss
Dagstuhl-Leibniz-Zentrum für Informatik.

[Vasconcelos et al(2019)]
authorpersonDR Vasconcelos, personRMC
Andrade, personValdenir Severino, and personJN De
Souza. year2019.
Cloud, fog, or mist in IoT? That is the question.
journalACM Transactions on Internet Technology
(TOIT) volume19, number2 (year2019),

[Xu et al(2023)]
authorpersonRonghua Xu, personDeeraj
Nagothu, and personYu Chen. year2023.
booktitleECOM: Epoch Randomness-Based Consensus
Committee Configuration for IoT Blockchains.
publisherSpringer International Publishing,
addressCham, pages135–154.

[Xu et al(2019a)]
authorpersonRonghua Xu, personSeyed Yahya
Nikouei, personYu Chen, personErik Blasch, and
personAlexander Aved. year2019a.
BlendMAS: A Blockchain-Enabled Decentralized
Microservices Architecture for Smart Public Safety. In
booktitle2019 IEEE International Conference on Blockchain
(Blockchain). pages564–571.

[Xu et al(2019b)]
authorpersonRonghua Xu, personSeyed Yahya
Nikouei, personYu Chen, personErik Blasch, and
personAlexander Aved. year2019b.
BlendMAS: A Blockchain-Enabled Decentralized
Microservices Architecture for Smart Public Safety. In
booktitle2019 IEEE International Conference on Blockchain
(Blockchain). pages564–571.

[Yin et al(2018)]
authorpersonMaofan Yin, personDahlia
Malkhi, personMichael K Reiter, personGuy Golan
Gueta, and personIttai Abraham.
Hotstuff: Bft consensus in the lens of blockchain.
journalarXiv preprint arXiv:1803.05069

[Zamani et al(2018)]
authorpersonMahdi Zamani, personMahnush
Movahedi, and personMariana Raykova.
Rapidchain: Scaling blockchain via full sharding.
In booktitleProceedings of the 2018 ACM SIGSAC conference on
computer and communications security. pages931–948.

[Žarko et al(2014)]
authorpersonIvana Podnar Žarko,
personKrešimir Pripužić, personMartin
Serrano, and personManfred Hauswirth.
Iot data management methods and optimisation
algorithms for mobile publish/subscribe services in cloud environments. In
booktitle2014 European conference on networks and
communications (EuCNC). IEEE, pages1–5.

[Zhang et al(2022)]
authorpersonMengqian Zhang, personJichen
Li, personZhaohua Chen, personHongyin Chen, and
personXiaotie Deng. year2022.
An Efficient and Robust Committee Structure for
Sharding Blockchain.
journalIEEE Transactions on Cloud Computing

§ DESCRIPTION  OF  THE ALGORITHM

Here we describe the algorithm which given the number of nodes $N$, assumed fraction of adversarial nodes  $P$, a fraction of a committee $A$ and the probability of failure $\delta$ computes the maximum number of committees $K$ and corresponding committee sizes. The algorithm computes  the RHS of  (<ref>) for the
$N=nK+r$ nodes where  the  $n$ and $n+1$ nodes are assigned, respectively, to the  $K-r$ and $r$ committees. Initially, all $N$ nodes are in one committee, and in subsequent iterations, the number of committees $K$ is increased by one until the probability  (<ref>) is equal to  or less than $\delta$. The pseudocode for the latter is provided below.

Comment/*  */

The algorithm to compute minimal sizes of committees resilient to $\delta$ failure rate.

$N$, $\delta$, $A$, $P$;
$K$, $n$, $r$, $\mathrm{Prob}$;
$K \gets 1$
$n \gets N$
$r \gets 0$

$\mathrm{Prob} \gets 0$
Save $K$, $n$, $r$ and $\mathrm{Prob}$.
$K_{-1}\gets K$
$n_{-1}\gets n$
$r_{-1}\gets r$
$Prob_{-1}\gets Prob$
Compute next $K$.

$K\gets K+1$
Compute remainder, r, and quotient, n when N is divided by K.
$r\gets rem(N,K)$
$n\gets quot(N,K)$
Compute CDF of the Binomial(n,P) and Binomial(n+1,P).
$\mathrm{Prob}_0\gets\Prob(X\leq \lfloor An\rfloor\,\vert n,P)$
$\mathrm{Prob}_1\gets\Prob(X\leq \lfloor A(n+1)\rfloor\,\vert n+1,P)$
Compute the probability of failure.
$Prob\gets 1-\mathrm{Prob}_0^{K-r}\mathrm{Prob}_1^r$

Compute CDF of the Binomial(n,P).
$\mathrm{Prob}_0\gets\Prob(X\leq \lfloor An\rfloor\,\vert n,P)$
Compute the probability of failure.
$Prob\gets 1-\mathrm{Prob}_0^{K}$

$K \gets K_{-1}$
$n \gets n_{-1}$
$r \gets r_{-1}$
$Prob\gets \mathrm{Prob}_{-1}$


# Effect of the resonant ac-drive on the spin-dependent recombination of
polaron pairs: Relation to organic magnetoresistance

M. E. Raikh  Department of Physics and Astronomy, University of Utah, Salt
Lake City, UT 84112

###### Abstract

The origin of magnetoresistance is bipolar organic materials is the influence
of magnetic field on the dynamics of recombination within localized electron-
hole pairs. Recombination from the $S$ spin-state of the pair in preceded by
the beatings between the states $S$ and $T_{0}$. Period of the beating is set
by the the random hyperfine field. For the case when recombination time from
$S$ is shorter than the period, we demonstrate that a weak resonant ac drive,
which couples $T_{0}$ to $T_{+}$ and $T_{-}$ affects dramatically the
recombination dynamics and, thus, the current A distinctive characteristics of
the effect is that the current versus the drive amplitude exhibits a maximum.

##  I Introduction

In the pioneering paper Ref. Frankevich,  it was first proposed that
sensitivity of the resistance of certain organic materials to a weak magnetic
field is due to spin-dependent recombination within polaron pairs. Roughly
speaking, while formation of a pair in each of the four possible spin states
$S$, $T_{0}$, $T_{+}$, and $T_{-}$, occurs with equal probabilities, they
recombine predominantly from $S$. As a result, the $S-T$ dynamics ($S-T$
beatings) affects the net recombination rate, which, in turn, determines the
current. On the other hand, the $S-T$ dynamics (see the classical paper Ref.
classical, ) is governed by the ratio of the applied magnetic field to the
hyperfine field. If both pair-partners have the same charge, recombination
should be replaced by the bipolaron formation.VardenyUltrasmall  In the later
studies (see e.g. Refs. OMAR1, ; OMAR2, ; OMAR3, ; OMAR4, ; Roundy1, ;
Roundy2, ) the scenario of Ref. Frankevich,  was confirmed experimentally. A
conclusive experimental evidence that hyperfine magnetic fields play a crucial
role in magnetic field response of organic semiconductors was reported in Ref.
5,  on the basis of comparison the data on hydrogenated (with higher hyperfine
fields) and deuterated (with lower hyperfine fields) samples.

It is clear that subjecting a pair to a resonant ac drive can flip the spin of
one of the pair-partners and, thus, affect the $S-T$ beatings. This idea was
proposed in Refs. Robust, ; Roundy,  and confirmed experimentally in Refs.
Experiment, ,Experiment1, ,Boehme+Lupton, . A peculiar feature of the
analytical theory Ref. Roundy,  is that it predicted a non-monotonic
dependence of magnetoresistance on the drive amplitude, $B_{1}$. This behavior
reflects a delicate balance between two processes. Firstly, without drive, the
only triplet state coupled to $S$ is $T_{0}$. In other words, it cannot
recombine from $T_{+}$ or $T_{-}$, which we call the trapping configurations.
Weak drive couples $T_{+}$ and $T_{-}$ to $T_{0}$, thus, effectively coupling
them to $S$ and allowing recombination from these states. This leads to the
enhancement of current. On the other hand, strong drive leads to the formation
of a new mode of spin dynamicsRoundy , namely, $T_{+}-T_{-}$. This mode is
orthogonal to $T_{0}$, and, thus, it is decoupled from $S$. Possibility to be
trapped in $T_{+}-T_{-}$ leads to the slowing of recombination and,
correspondingly, to the decrease of current upon increasing of drive.

The theory of Ref. Roundy,  was based on the assumption that the $S-T$
asymmetry of the pair is strong. Typical value of this asymmetry is $\gamma
b_{0}$, where $\gamma$ is the gyromagnetic ratio, while $b_{0}$ is the
magnitude of the hyperfine field. The criterion of a strong asymmetry reads
$\gamma b_{0}\tau\gg 1$, where $\tau$ is the recombination time from $S$.
Physically, this criterion implies that the pair undergoes many, $\sim\gamma
b_{0}\tau$, $S-T_{0}$ beatings before it recombines. In the opposite limit,
$\gamma b_{0}\tau\ll 1$, there are no $S-T_{0}$ beatings. Instead, the pair
recombines almost instantly after it finds itself in $S$. In this limit it is
not clear whether the ac drive can affect the current. It is this limit that
is studied in the present paper. We employ the same maximally simplified
transport model as in Refs. Roundy1, ; Roundy2, .

Figure 1: (Color online) (a) Illustration of the transport model. Current
passage through a bipolar device involves recombination of the localized
electron (red) and localized hole (blue), which are assembled on the
neighboring sites; (b) Spin dynamics of a resonantly driven pair preceding
recombination from $S$. The dynamics involves $S-T_{0}$ beatings and the Rabi
oscillations between $T_{0}$ and two other triplet components.

##  II Transport model

For concreteness we assume that the transport is due to recombination of
electron-hole pairs. As illustrated in Fig. 1, electron and hole are assembled
at neighboring sites and start precessing in the respective magnetic fields,
${\bm{B}}+{\bm{b}_{e}}$ and ${\bm{B}}+{\bm{b}_{h}}$, where ${\bm{b}_{e}}$ and
${\bm{b}_{h}}$ are the electron and hole hyperfine fields. All four initial
spin configurations of a pair have the same probability. After some time, the
pair either recombines or gets disassembled depending on which process takes
less time. The key simplifying assumption adopted in Refs. Roundy1, ; Roundy2,
is that assembly and disassembly of a pair takes the time, $\tau_{D}$, much
longer than $\tau$. Under this assumption, the passage of current proceeds in
cycles. The magnitude of current is related to $\langle t\rangle$ which is the
average cycle duration, see e.g. Ref. von, , as

$I=\frac{1}{\langle t\rangle}.$ (1)

Obviously, the ac drive, $B_{1}$, affects only the precession stage of the
current passage. The effect of drive is most pronounced when
$|{\bm{b}}_{e}|,|{\bm{b}}_{h}|<<B$. Then the resonant frequency is related to
$B$ as, $\omega=\gamma B$. The above condition allows to neglect the
transverse components of hyperfine fields and to employ the rotating wave
approximation.

##  III Spin dynamics with fast recombination

We start from the standard Hamiltonian of an electron-hole pair driven with
frequency $\omega=\gamma B$

$\\!{\hat{H}}=\omega_{e}{\hat{S}}_{e}^{z}+\omega_{h}{\hat{S}}_{h}^{z}+2\Omega_{R}\left({\hat{S}}_{e}^{x}+{\hat{S}}_{h}^{x}\right)\cos\omega
t,$

where $\Omega_{R}=\gamma B_{1}$ is the Rabi frequency, ${\hat{S}}_{e}$ and
${\hat{S}}_{h}$ are the spin operators of electron and hole, respectively. The
frequencies $\omega_{e}$ and $\omega_{h}$ are expressed via the
$z$-projections of the hyperfine fields $b_{e}^{z}$, $b_{h}^{z}$ as

$\omega_{e}=\omega+\gamma b_{e}^{z},\hskip 11.38109pt\omega_{h}=\omega+\gamma
b_{h}^{z}.$ (2)

Denote with $A_{T_{+}}$, $A_{T_{-}}$, $A_{T_{0}}$, and $A_{S}$ the amplitudes
of four spin states of the pair. With account of recombination from $S$, the
amplitudes of the states satisfy the system of equations

$\displaystyle i\frac{\partial A_{T_{+}}}{\partial
t}=\left(\omega+\delta\right)A_{T_{+}}+\frac{\Omega_{R}}{2^{1/2}}A_{T_{0}}\cos\omega
t,$ (3) $\displaystyle i\frac{\partial A_{T_{-}}}{\partial
t}=-\left(\omega+\delta\right)A_{T_{-}}+\frac{\Omega_{R}}{2^{1/2}}A_{T_{0}}\cos\omega
t,$ (4) $\displaystyle i\frac{\partial A_{T_{0}}}{\partial
t}=\delta_{0}A_{S}+\frac{\Omega_{R}}{2^{1/2}}(A_{T_{+}}+A_{T_{-}})\cos\omega
t,$ (5) $\displaystyle i\Bigl{(}\frac{\partial A_{S}}{\partial
t}+\frac{A_{S}}{\tau}\Bigr{)}=\delta_{0}A_{T_{0}},$ (6)

where $\delta_{0}$ and $\delta$ are defined as

$\delta_{0}=\frac{1}{2}\left(\omega_{e}-\omega_{h}\right),\hskip
8.53581pt\delta=\frac{1}{2}\left(\omega_{e}+\omega_{h}-2\omega\right).$ (7)

Within the rotating wave approximation $\cos\omega t$ in the first equation of
the system is replaced by $\frac{1}{2}e^{-i\omega t}$, while in the second
equation it is replaced by $\frac{1}{2}e^{i\omega t}$. Switching to “rotated”
system is achieved by introducing new variables

$\displaystyle A_{T_{-}}=a_{T_{-}}e^{-i(\chi-\omega)t},\hskip
8.53581ptA_{T_{+}}=a_{T_{+}}e^{-i(\chi+\omega)t},$ (8) $\displaystyle
A_{T_{0}}=a_{T_{0}}e^{-i\chi t},\hskip 8.53581ptA_{S}=a_{S}e^{-i\chi t}.$ (9)

Then the system reduces to the following four algebraic equations

$\displaystyle(\chi-\delta)a_{T_{-}}=\frac{\Omega_{R}}{2^{1/2}}a_{T_{0}},\hskip
5.69054pt(\chi+\delta)a_{T_{+}}=\frac{\Omega_{R}}{2^{1/2}}a_{T_{0}},$ (10)
$\displaystyle\chi
a_{T_{0}}=-\delta_{0}a_{S}+\frac{\Omega_{R}}{2^{1/2}}(a_{T_{-}}+a_{T_{+}}),$
$\displaystyle\left(\chi+\frac{i}{\tau}\right)a_{S}=-\delta_{0}a_{T_{0}},$
(11)

As discussed above, in the absence of drive, spin dynamics of the system
reduces to the $S-T$ beating with a frequency $\delta_{0}$, which is a measure
of the hyperfine-induced spin asymmetry of the pair. Indeed, upon setting
$\Omega_{R}=0$ in the system Eqs. (10), (III) it yields two frequencies,
$\pm\delta_{0}$. Subjecting the system to the ac drive, involves the states
$T_{+}$ and $T_{-}$ into the spin dynamics leading to the formation of two
more modes. The frequencies of all four modes satisfy the following algebraic
equation, which follows from Eqs. (10), (III)

$\chi\Bigl{(}\chi+\frac{i}{\tau}\Bigr{)}\Bigl{(}\chi^{2}-\delta^{2}-\Omega_{R}^{2}\Bigr{)}=\delta_{0}^{2}\Bigl{(}\chi^{2}-\delta^{2}\Bigr{)}.$
(12)

Unlike Ref. Roundy, , we will analyze the eigenvalues of the system Eqs. (10),
(III) in the limit of fast recombination
$\tau^{-1}\gg\delta_{0},\delta,\Omega_{R}$. One consequence of the fast
recombination is that Eq. (12) has a solution $\chi=-\frac{i}{\tau}$
corresponding to the decaying state $S$. Then the other three solutions for
which $|\chi|\ll\tau^{-1}$ satisfy the cubic equation which emerges upon
neglecting $\chi$ in the second bracket

$\chi^{3}-\Bigl{(}\delta^{2}+\Omega_{R}^{2}\Bigr{)}\chi=-i\delta_{0}^{2}\tau\Bigl{(}\chi^{2}-\delta^{2}\Bigr{)}.$
(13)

Another consequence of $\tau^{-1}$ being bigger than other parameters in Eq.
(12) is that one of three brackets in the left-hand side of Eq. (13) is small.
Thus, in the limit $\tau\rightarrow 0$ the three eigenvalues are

$\tilde{\chi}_{T_{0}}=0,\hskip
5.69054pt\tilde{\chi}_{\pm}=\pm(\delta^{2}+\Omega_{R}^{2})^{1/2}.$ (14)

Figure 2: (Color online) Schematic illustration of the eigenvalues of Eq. (12)
in the regime of fast recombination. The width, $\tau^{-1}$, of the eigenstate
$S$ is much bigger than the widths of $T_{0}$, $T_{+}$, $T_{-}$ eigenstates.

Naturally, the zero-order eigenvalues Eq. (14) do not capture the decay of
$T_{0}$ and $T_{\pm}$ eigenmodes. This is because we neglected the right-hand
side in Eq. (13) containing the recombination time. To capture the decay of
eigenmodes, we substitute the zero-order $\tilde{\chi}$ values into the right-
hand side, set $\chi=\tilde{\chi}+\delta\chi$ in the left-hand side, and
expand the left-hand side with respect to $\delta\chi$. This yields

$\delta\chi=-i\delta_{0}^{2}\tau\left(\frac{\tilde{\chi}^{2}-\delta^{2}}{3\tilde{\chi}^{2}-\delta^{2}-\Omega_{R}^{2}}\right)$
(15)

Using Eq. (14), we find the following imaginary parts of slow-decaying modes

$\delta\chi_{T_{0}}=-i\delta_{0}^{2}\tau\left(\frac{\delta^{2}}{\delta^{2}+\Omega_{R}^{2}}\right),$
(16)
$\delta\chi_{\pm}=-i\delta_{0}^{2}\tau\left(\frac{\Omega_{R}^{2}}{2\delta^{2}+2\Omega_{R}^{2}}\right).$
(17)

By virtue of the small parameter $\delta_{0}\tau\ll 1$ the widths of the
triplet eigenmodes is much smaller than $\tau^{-1}$, the width of the singlet
eigenmode, as illustrated in Fig. 2. From Eqs. (16), (17) we conclude that

$\delta\chi_{T_{0}}+\delta\chi_{+}+\delta\chi_{-}=-i\delta_{0}^{2}\tau,$ (18)

i.e. the sum of the decay rates of weakly decaying modes is independent of
drive. The main point though is that the current is determined by the average
trapping time, while contribution to the trapping time from each mode is
proportional to the inverse decay rate. Using Eqs. (16), (17) we can express
the average duration of a cycle as follows

$\langle
t\rangle-\tau_{D}=\sum_{i}\frac{1}{4\text{Im}~{}\chi_{i}}=\frac{\tau}{4}+\frac{\delta^{2}+\Omega_{R}^{2}}{4\delta_{0}^{2}\tau}\left[\frac{4}{\Omega_{R}^{2}}+\frac{1}{\delta^{2}}\right].$
(19)

The right-hand side of Eq. (19) can be presented in the form

$\frac{\tau}{4}+\frac{1}{4\delta_{0}^{2}\tau}\left[\frac{4\delta^{2}}{\Omega_{R}^{2}}+\frac{\Omega_{R}^{2}}{\delta^{2}}+5\right].$
(20)

This form suggests that the period of the cycle and, thus, the inverse current
as a function of drive has a minimum at $\Omega_{R}=2^{1/2}\delta$. Recall,
that the parameter $\delta$, defined by Eq. (7), has the meaning of the
combined detuning of the pair.

In principle, the term $\tau$ in Eq. (19) also contains a $\Omega_{R}^{2}$
correction. To calculate this correction we recast Eq. (12) in the form

$\chi+\frac{i}{\tau}=\frac{\delta_{0}^{2}(\chi^{2}-\delta^{2})}{\chi(\chi^{2}-\delta^{2}-\Omega_{R}^{2})}.$
(21)

Substituting the zero-order result, $\chi=-\frac{i}{\tau}$, into the right-
hand side, we get a corrected expression for the imaginary eigenvalue

$\chi_{S}=-\frac{i}{\tau}\left[1-\frac{\delta_{0}^{2}\tau^{2}(1+\delta^{2}\tau^{2})}{1+(\delta^{2}+\Omega_{R}^{2})\tau^{2}}\right].$
(22)

It follows from Eq. (22) that the magnitude of $\Omega_{R}$-dependent
correction to the decay time of the $S$-mode is $\sim\delta_{0}^{2}\tau^{3}$,
which is much smaller than the remaining terms in Eq. (20) by virtue of the
small parameter $\delta_{0}\tau\ll 1.$

##  IV Incorporating exchange

Next question we address is how the exchange interaction between electron and
hole affects the current through the resonantly driven pair. For a standard
exchange Hamiltonian

${\hat{H}}_{ex}=-J{\bf{\hat{S}}}_{e}\cdot{\bf{\hat{S}}}_{h}$ (23)

the system Eq. (10) is modified as follows. In equations for $T_{0}$,
$T_{\pm}$ the eigenvalue $\chi$ is replaced by
$\bigl{(}\chi+\frac{J}{2}\bigr{)}$, while in equation for $S$ it is replaced
by $\bigl{(}\chi-\frac{J}{2}\bigr{)}$. Then in the limit of fast recombination
Eq. (13) takes the form

$\displaystyle\left(\chi+\frac{J}{2}\right)^{3}-\left(\delta^{2}+\Omega_{R}^{2}\right)\left(\chi+\frac{J}{2}\right)$
$\displaystyle=-i\delta_{0}^{2}\tau\left[\left(\chi+\frac{J}{2}\right)^{2}-\delta^{2}\right].$
(24)

From the form of Eq. (IV) we conclude that incorporating exchange shifts the
eigenvalues by $J$ but leaves their imaginary parts, responsible for the
current, unchanged.

##  V Averaging over the hyperfine fields

Averaging over the hyperfine fields acting on electron and hole reduces to the
averaging of Eq. (20) over parameters $\delta$ and $\delta_{0}$, which are
statistically independent and Gauss-distributed. Prior to performing the
averaging, we recast the expressions Eqs. (1) and (20) in the form

$I(\Omega_{R})=\frac{\Omega_{R}^{2}\tau}{a\Omega_{R}^{4}+b\Omega_{R}^{2}+c},$
(25)

where the parameters $a$, $b$, and $c$ are expressed via the following
averages

$\displaystyle
a=\frac{1}{4}\Big{\langle}\frac{1}{\delta^{2}\delta_{0}^{2}}\Big{\rangle},$
(26) $\displaystyle
b=\tau\biggl{(}\tau_{D}+\frac{\tau}{4}\biggr{)}+\frac{5}{4}\Big{\langle}\frac{1}{\delta_{0}^{2}}\Big{\rangle},$
(27) $\displaystyle
c=\Big{\langle}\frac{\delta^{2}}{\delta_{0}^{2}}\Big{\rangle}.$ (28)

Note, that all three parameters diverge in the limit of small $\delta$,
$\delta_{0}$. These divergences should be cut at
$\delta,\delta_{0}\sim\tau_{D}^{-1}$, i.e. at inverse assembly time of the
pair. The portion of such small $\delta,\delta_{0}$ is $(\tau_{D}\gamma
b_{0})^{-1}$, where $\gamma b_{0}$ is the r.m.s. detuning of the pair
partners. With this in mind, we get the following expressions for the
parameters $a$, $b$, and $c$

$a=\frac{1}{4}\left(\frac{\tau_{D}}{\gamma
b_{0}}\right)^{2},~{}~{}b=\frac{5}{4}\left(\frac{\tau_{D}}{\gamma
b_{0}}\right),~{}~{}c=\gamma b_{0}\tau_{D}.$ (29)

It is instructive to present the final result Eq. (25) in terms of
dimensionless Rabi frequency defined as

${\tilde{\Omega}_{R}}=\Omega_{R}\frac{\tau_{D}^{1/4}}{(\gamma b_{0})^{3/4}}.$
(30)

Then Eq. (25) takes the form

$I(\Omega_{R})=\frac{\tau(\gamma
b_{0})^{1/2}}{\tau_{D}^{3/2}\left[\frac{1}{4}{\tilde{\Omega}_{R}}^{2}+{\tilde{\Omega}_{R}}^{-2}+\frac{5}{4}(\gamma
b_{0}\tau_{D})^{-1/2}\right]}.$ (31)

The fact that within the adopted transport model the assembly time,
$\tau_{D}$, exceeds the precession time, $\tau_{D}\gg(\gamma b_{0})^{-1}$. One
consequence of this assumption is the third term in the denominator of Eq.
(31) is smaller than one, i.e. the the minimum is deep. Another nontrivial
consequence of a long assembly time is that the position
$\tilde{\Omega}_{R}\sim 1$ of maximum of $I(\Omega_{R})$ corresponds to the
Rabi frequency parametrically smaller than the broadening, $\gamma b_{0}$, due
to hyperfine fields.

In Eq. (2) we assumed that the driving frequency, $\omega$, exactly matches
the Zeeman splitting, $\gamma B$. In fact, in the experiment of Ref. Robust,
the sensitivity of current to the ac drive was observed in the sizable
interval of $B$. The result of averaging over $\delta$ depends on the detuning

$\Delta=\omega-\gamma B.$ (32)

In the case when the detuning is big, $\Delta\gg\gamma b_{0}$, one has to
replace $\delta$ by $\Delta$ on Eq. (26) and to perform averaging over
$\delta$. The result reads

$I(\Omega_{R})=\frac{4\gamma
b_{0}\tau}{\tau_{D}\left[\frac{\Omega_{R}^{2}}{\Delta^{2}}+\frac{4\Delta^{2}}{\Omega_{R}^{2}}+5\right]}.$
(33)

##  VI Discussion

(1). Our main result is Eq. (20) for the time, $\langle t\rangle$, as a
function of the drive amplitude, $\Omega_{R}=\gamma B_{1}$. The meaning of
$\langle t\rangle$ is the time it takes for a spin pair to assemble and either
recombine or disassemble. Our main finding is that, in the regime of fast
recombination, $\langle t\rangle$, exhibits a minimum. Thus, the current
$I=\langle t\rangle^{-1}$ versus $\Omega_{R}$ exhibits a maximum in agreement
with slow-recombination theory.Roundy  It should be emphasized that the faster
is recombination, the smaller is the current. This is because fast
recombination from $S$ ensures more efficient trapping in each of the triplet
states.

(2). We have incorporated decay into the system Eq. (10) for the amplitudes of
four states of the spin-pair. Rigorous approach implies incorporation of the
decay into the stochastic Liouville equation for the spin density matrix. With
four spin states involved, the size of the density matrix is $16\times 16$.
However, the eigenvalues of this matrix can be cast in the form
$\chi_{i}-\chi_{j}^{*}$, where $\chi_{i}$ are the roots of the fourth-order
algebraic equation Eq. (12). Equivalence of the description adopted in the
present paper and the density matrix-based description was demonstrated in
Refs. Roundy1, ; Shinar, . Roughly speaking, our description applies when the
eigenvectors of the $4\times 4$ system for the amplitudes are approximately
orthogonal to each other. In our case, approximate orthogonality of
eigenvectors is insured by the fact that one eigenvector is mostly of $S$-type
with small (of the order of $\delta_{0}\tau$) admixture of $T$-states, while
other eigenstates are mostly $T$ with small admixture of $S$

(3). Consideration in the present paper pertains to organic semiconductors
since the spin-orbit coupling in carbon-based materials is weak. The residual
spin-orbit interaction renormalizes the difference, $\Delta g$, of the Landé
factors of the pair partners. In strong external field the $S-T_{0}$ splitting
caused by $\Delta g$ exceeds the hyperfine-induced splitting, $\delta_{0}$,
defined by Eq. (7). In Ref. deltaG,  it was demonstrated experimentally that
this $\Delta g$-mechanism is at work in the field $B\sim 8T$.

(4). As it was mentioned in the Introduction, the underlying mechanism of the
sensitivity of current through the organic material to the magnetic field is
the $S-T_{0}$ beating preceding the recombination from $S$. Change of the
external field affects this beating. Naturally, recombination causes the
broadening of both $S$ and $T_{0}$ levels. Importantly, this broadening is
quite different in the limits of the slow, $\gamma b_{0}\tau\gg 1$, and fast
$\gamma b_{0}\tau\ll 1$ recombination. In the first limit both $S$ and $T_{0}$
have equal widths, $\frac{1}{2\tau}$. In the second limit of the fast
recombination the width of $S$ remains $\frac{1}{2\tau}$, while the level
$T_{0}$ narrows dramatically and becomes $\gamma^{2}b_{0}^{2}\tau$, as it is
illustrated in Fig. 2. In this regard, the key message of the present paper,
is that, with fast recombination, a narrow level $T_{0}$ can be engaged into
the Rabi oscillations between $T_{0}$ and $T_{+}$, $T_{-}$ by a weak ac drive.
Certain confirmation that this scenario is realistic comes from the fact that
these Rabi oscillations can be ”seen” experimentally by means of the pulsed
EDMR technique, see e.g. Refs. Boehme+Lips, ; Boehme+Lupton+Rabi, ; HighB_0, ;
Saam, ; Glenn, . Within this technique, the change, $\delta\sigma$, in the
conductivity of the sample is measured upon application of a pulse of variable
duration. Then the Rabi oscillations show up in the dependence of
$\delta\sigma$ on the pulse duration.

## References

  * (1) E. L. Frankevich, A. A. Lymarev, I. Sokolik, F. E. Karasz, S. Blmstengel, R. H. Baughman, and H. H. Hörhold, “Polaron-pair generation in poly(phenylene vinylenes),” Phys. Rev. B 46, 9320 (1992).
  * (2) K. Schulten and P. G. Wolynes, ”Semiclassical description of electron spin motion in radicals including the effect of electron hopping,” J. Chem. Phys. 68, 3292 (1978).
  * (3) Experimental evidence that the spin pairs can consist both of opposite-charge carriers (in bipolar devices) and the like-charge carriers (in unipolar devices) can be found in T. D. Nguyen, B. R. Gautam, E. Ehrenfreund, and Z. V. Vardeny, ”Magnetoconductance Response in Unipolar and Bipolar Organic Diodes at Ultrasmall Fields,” Phys. Rev. Lett. 105, 166804 (2010).
  * (4) Ö. Mermer, G. Veeraraghavan, T. L. Francis, Y. Sheng, D. T. Nguyen, M. Wohlgenannt, A. Köhler, M. K. Al-Suti, and M. S. Khan, “Large magnetoresistance in nonmagnetic $\pi$-conjugated semiconductor thin film devices,” Phys. Rev. B 72, 205202 (2005).
  * (5) S. P. Kersten, A. J. Schellekens, B. Koopmans, and P. A. Bobbert, ”Magnetic-Field Dependence of the Electroluminescence of Organic Light-Emitting Diodes: A Competition between Exciton Formation and Spin Mixing,” Phys. Rev. Lett. 106, 197402 (2011).
  * (6) W. Wagemans, A. J. Schellekens, M. Kemper, F. L. Bloom, P. A. Bobbert, and B. Koopmans, ”Spin-Spin Interactions in Organic Magnetoresistance Probed by Angle-Dependent Measurements,” Phys. Rev. Lett. 106, 196802 (2011).
  * (7) N. J. Harmon and M. E. Flatté, ”Spin-Flip Induced Magnetoresistance in Positionally Disordered Organic Solids,” Phys. Rev. Lett. 108, 186602 (2012); ”Semiclassical theory of magnetoresistance in positionally-disordered organic semiconductors,” Phys. Rev. B 85, 075204 (2012); ”Effects of spin-spin interactions on magnetoresistance in disordered organic semiconductors,” Phys. Rev. B 85, 245213 (2012).
  * (8) R. C. Roundy and M. E. Raikh, “Slow dynamics of spin pairs in a random hyperfine field: Role of inequivalence of electrons and holes in organic magnetoresistance,” Phys. Rev. B 87, 195206 (2013).
  * (9) R. C. Roundy, Z. V. Vardeny, and M. E. Raikh, “Organic magnetoresistance near saturation: Mesoscopic effects in small devices,” Phys. Rev. B 88, 075207 (2013).
  * (10) T. D. Nguyen, G. H. Markosian, F. Wang, L. Wojcik, X. G. Li, E. Ehrenfreund, and Z. V. Vardeny, ”Isotope effect in spin response of $\pi$-conjugated polymer films and devices,” Nature Mater. 9, 345 (2010).
  * (11) W. J. Baker, K. Ambal, D. P. Waters, R. Baarda, H. Morishita, K. van Schooten, D. R. McCamey, J.M. Lupton, and C. Boehme, ”Robust absolute magnetometry with organic thin-film devices,” Nat. Commun. 3, 898 (2012).
  * (12) R. C. Roundy and M. E. Raikh, “Organic magnetoresistance under resonant ac drive,” Phys. Rev. B 88, 125206 (2013).
  * (13) D. P. Waters, G. Joshi, M. Kavand, M. E. Limes, H. Malissa, P. L. Burn, J. M. Lupton, and C. Boehme, “The spin-Dicke effect in OLED magnetoresistance,” Nat. Physics 11, 910 (2015).
  * (14) S. Jamali, G. Joshi, H. Malissa, J. M. Lupton and C. Boehme, ”Monolithic OLED-Microwire Devices for Ultrastrong Magnetic Resonant Excitation,” Nano Lett. 17, 4648 (2017).
  * (15) T. H. Tennahewa, S. Hosseinzadeh, S. I. Atwood, H. Popli, H. Malissa, J. M. Lupton, and Boehme, ”Spin relaxation dynamics of radical-pair processes at low magnetic fields,” arXiv:2207.07086.
  * (16) J. Koch, M. E. Raikh, and F. von Oppen, ”Full Counting Statistics of Strongly Non-Ohmic Transport through Single Molecules,” Phys. Rev. Lett. 95, 056801 (2005).
  * (17) V. V. Mkhitaryan, D. Danilović, C. Hippola, M. E. Raikh, and J. Shinar, ”Comparative analysis of magnetic resonance in the polaron pair recombination and the triplet exciton-polaron quenching models,” Phys. Rev. B 97, 035402 (2018).
  * (18) High-Field Magnetoresistance of Organic Semiconductors G. Joshi, M. Y. Teferi, R. Miller, S. Jamali, M. Groesbeck, J. van Tol, R. McLaughlin, Z. V. Vardeny, J. M. Lupton, H. Malissa, and C. Boehme, ”High-Field Magnetoresistance of Organic Semiconductors,” Phys. Rev. Applied 10, 024008 (2018).
  * (19) C. Boehme and K. Lips, ”Theory of time-domain measurement of spin-dependent recombination with pulsed electrically detected magnetic resonance,” Phys. Rev. B 68, 245105 (2003).
  * (20) D. R. McCamey, K. J. van Schooten, W. J. Baker, S.-Y. Lee, S.-Y. Paik, J. M. Lupton, and C. Boehme, ”Hyperfine-Field-Mediated Spin Beating in Electrostatically Bound Charge Carrier Pairs,” Phys. Rev. Lett. 104, 017601 (2010).
  * (21) W. J. Baker, D. R. McCamey, K. J. van Schooten, J. M. Lupton, and C. Boehme, ”Differentiation between polaron-pair and triplet-exciton polaron spin-dependent mechanisms in organic light-emitting diodes by coherent spin beating” Phys. Rev. B 84, 165205 (2011).
  * (22) M. E. Limes, J. Wang, W. J. Baker, S.-Y. Lee, B. Saam, and C. Boehme, ”Numerical study of spin-dependent transition rates within pairs of dipolar and exchange coupled spins with $s=1/2$ during magnetic resonant excitation,” Phys. Rev. B 87, 165204 (2013).
  * (23) R. Glenn, W. J. Baker, C. Boehme, and M. E. Raikh, ”Analytical description of spin-Rabi oscillation controlled electronic transitions rates between weakly coupled pairs of paramagnetic states with $S=1/2$,” Phys. Rev. B 87, 155208 (2013).