
\section*{Acknowledgements}

	
\input{main.bbl}	
	

	

\section{Analysis}\label{sec:analysis}

In this section, we derive an analysis of the recovery operation of \ac{MET} \acp{IBLT}. For that, we elaborate on \ac{MET} density evolution \cite{richardson2002multi} which provides a general framework to analyze the performance of \ac{LDPC} code ensembles on a variety of communication channels. The obtained results can be exploited for the design of \ac{MET} \acp{IBLT}.


\ac{MET} density evolution is an asymptotic analysis tool that  provides  the \emph{average} probability of a key-value pair being present in the output list of the recovery operation, where the average is taken over an ensemble of bipartite graphs. In the case of LDPC codes, density evolution analyzes the average performance of a code ensemble, but in practice one single graph of the ensemble (i.e. one code) is selected. Here, one could possibly choose a code whose performance  deviates from the ensemble average. In our case, even while fixing the \ac{IBLT} parameters and hash functions, different graphs are obtained by inserting different sets $\S$ into the \ac{IBLT}. Thus, one does experience an average performance simply by working with different (data) sets.


\subsection{MET IBLT description}
Recalling Section~\ref{sec:IBLT}, we associate to each cell node a node type $i \in \{1,2,\ldots,d_c\}$. Cell nodes of the same type may have \textit{different degrees}. We introduce the edge oriented degree distribution polynomial for cell nodes of type $i$
\begin{align} \label{eq:rhoi}
\rho_{i}(\mathrm{x})&=\sum_{k=1} \rho_{i,k} \mathrm{x}^{k-1}   
\end{align}
with coefficients $\rho_{i,k}$ being edge fractions obtained as the number of edges emanating from cell nodes of type $i$ of degree $k$ divided by all edges emanating from cell nodes of type $i$. As we will shortly see, $\rho_{i}(\mathrm{x})$ is induced by the node degree and type distributions of the data nodes.

Each data node is associated with a data node type  $j \in \{1,2,\ldots,d_d\}$. We use a $d_c \times d_d$  degree matrix $\bm{D}=[\a_{i,j}]$ to  describe the connectivity between the different types of data and cell nodes, where $\a_{i,j}$ corresponds to the number of edges connecting a data node of type $j$  to type $i$ cell nodes (recall Section~\ref{sec:IBLT}). 
Considering only edges connected to cell nodes of type $i$ (row $i$ of $\bm{D}$), we define the expected data node degree $\bar{\a}_i$ from the perspective of a cell node of type $i$ as
\begin{align}\label{eq:analysis:avg_degree}
    \bar{\a}_i  & = \sum_{j=1}^{d_d} p_j \a_{i,j}. 
\end{align}
Likewise, for each cell node type $i$, we denote by  $\lambda_{i,j}$ the fraction of edges connected to data nodes of type $j$, 
  $ {\lambda}_{i,j} = \frac{ p_j \a_{i,j}}{\bar{\a}_i}$.
Hence, ${\bm \lambda_i}=[{\lambda}_{i,j}],$ $j \in \{1,2,\ldots,d_d\}$ gives an edge oriented data node degree distribution considering only edges connected to type $i$ cell nodes (and ignoring all other edges). 
\begin{example}\label{ex:MET1}
Consider the degree matrix $\bm{D}=\begin{bmatrix}    2    & 0 &    1\\
     2  &   3   &  3\end{bmatrix}$ and the probability vector $\bm p=\begin{bmatrix}    0.25    & 0.25 &    0.5\end{bmatrix}$. We have three different data node types and two different cell node types. With probability $1/2$ a data node is of type three while with probability $1/4$ it is of type one or two, respectively. The average data node degrees from the cell node perspective are $\bar{\a}_1= 1.00$ and $\bar{\a}_2=2.75$. Further, the data node edge-oriented degree distributions from the cell node perspective are ${\bm \lambda}_1=\begin{bmatrix} 0.50   &      0   & 0.50\end{bmatrix}$ and ${\bm \lambda}_2=\begin{bmatrix}  0.18  &  0.27 &   0.55\end{bmatrix}$.
\end{example}
\begin{example}\label{ex:MET4}
	Assume a \ac{MET} \ac{IBLT} with the parameters from Example~\ref{ex:MET1}. In addition, let $n=4$, $m=5$, and $m_1=2$, $m_2=3$. Figure~\ref{fig:MET_IBLT} exemplifies a bipartite graph with such parameters.\footnote{The connections are data dependent and are chosen at will in this example, respecting the type constraints.}
\end{example}
\begin{figure}[t]
    \centering
    \input{./figs/MET_IBLT}
    \caption{Bipartite graph example of a \ac{MET} \ac{IBLT} with $n=4$ data nodes 
    and $m=5$ cell nodes of different types.}
    \label{fig:MET_IBLT}
\end{figure}


\subsection{Load threshold computation}
\begin{definition}[Load]
Let the  {load} $\eta=n/m$, $n<m$, be the ratio between the number of key-value pairs and cells used to store those, i.e., the length of the \ac{IBLT}.
\end{definition}

Let us consider the regime for which $n$ and $m$ go to infinity. We are interested in the maximum load, the so-called load threshold $\eta^{\star}$ of a \ac{MET} \ac{IBLT} ensemble, such that recovery is successful {with high probability}. 
In the context of \ac{LDPC} codes, the threshold of code ensembles with peeling decoding is analyzed via \textit{density evolution} \cite{luby1998analysis,richardson2001design} which restates the peeling decoder as an \textit{equivalent} iterative message passing algorithm where nodes pass messages along the edges to their neighbors. The messages exchanged by the nodes can be either an \textit{erasure}, i.e., we do not know the corresponding key-value pair yet, or a \textit{non-erasure}, meaning that key-value pair is known.


Let us denote by $\pcn{\iota}$ the (average) probability that the message sent from a cell node of type $i$ over an edge at the $\iota$-th iteration is an erasure,  and by $\pvnavg{\iota}$ the (average) probability that the message sent from a data node to a cell node of type $j$ over an edge at the $\iota$-th iteration is an erasure. 
\ac{MET} density evolution allows to iteratively determine $\pcn{\iota}$ and $\pvnavg{\iota}$, and thereby determine the load threshold. 


As a first step in our analysis, we need  the edge perspective degree distribution for cell nodes of type $i$ in the limit when $m\rightarrow \infty$. As shown in \cite{Liva2011}, it is
\begin{align} \label{eq:rho_partial}
     {\rho}_i(\mathrm{x})=e^{- \frac{\eta}  {f_i} \,  \bar{\a}_i \, (1-\mathrm{x}) }
\end{align}
where $f_i\triangleq m_i/m$ is the fraction  of cell nodes of type $i$ and $\frac{\eta}  {f_i}$ is the load for the $m_i$ cell nodes of type $i$.
The message sent by a cell node of type $i$ will only be a non-erasure if all other incoming messages are  non-erasures, i.e.,
\begin{align}
   \pcn{\iota} & ={1- {\rho}_i\left(1- \pvnavg{\iota}\right)} 
   =1-e^{ - \frac{\eta}{f_i} \bar{\a}_i  \pvnavg{\iota}} .
   \label{eq:de_cn_met}
\end{align}
Let $\pvn{\iota}$ be the erasure probability for messages sent from a type-$j$ data node to a type-$i$ cell node at the $\iota$-th iteration. The message sent by a data node will only be an erasure if all other incoming messages are erasures, i.e.,
\begin{align}\label{eq:de_vn_met}
    \pvn{\iota} &= \prod_{k=1}^{d_c} \left( {\pcni{k}{\iota-1}}\right)^{b_{k,j}}
\end{align}
where $b_{k,j}=\a_{k,j}$ if $k \neq i$ else $b_{k,j}=\max(0,\a_{k,j}-1)$. Hence, the average erasure probability  at the input of a cell node of type $i$ at the $\iota$-th iteration $\pvnavg{\iota}$ is given by
\begin{align} \label{eq:de_vn_avg_met}
    \pvnavg{\iota} &= \sum_{j=1}^{d_d} {\lambda}_{i,j}   \pvn{\iota}.
\end{align}

By initially setting $\pvnavg{0} =1$ for the $0$-th iteration, and iteratively computing~\eqref{eq:de_cn_met},\eqref{eq:de_vn_met},\eqref{eq:de_vn_avg_met} it is possible to derive the probability that the messages passed along the edges of the graph are erasures as the number of iterations $\iota$ grows.

Let us define by $\gamma_j^{(\iota)}$ the probability that a data node of type $j$ is erased at the end of the $j$-th iteration. We have, 
\begin{align} \label{eq:de_app_met}
     \gamma_j^{(\iota)} &= \prod_{i=1}^{d_c} \left( \pcn{\iota} \right) ^{\a_{i,j}}.
\end{align}
The load threshold of a \ac{MET} \ac{IBLT} ensemble can be formally defined in terms of $\gamma_j^{(\iota)}$ as follows.
\begin{definition}[Load threshold] \label{def:load_threshold}
The load threshold $\eta^{\star}$ is the largest value of $\eta$ such that $\gamma_j^{(\iota)}\rightarrow 0$ for all $j\in \{1,2,\ldots, d_d\}$ when $m\rightarrow \infty$ and $\iota \rightarrow \infty$.
\end{definition}


\subsection{Numerical Examples}\label{sec:anal_num_res}
We report load thresholds complemented by finite-length simulations of the probability $P_e$ that a randomly chosen key-value pair is not present in the output list of the recovery operation. For illustration purposes, we consider two different \ac{MET} \ac{IBLT} designs with different load thresholds $\eta^{\star}$. 

\begin{example}
Consider a design $E_1$ with $3$ different data and cell node types, $d_d=d_c=3$,
a probability vector $\bm{p}=[ 0.2, 0.2, 0.6]$, $\bm{m} = [m/3, m/3, m/3]$, 
 and  a degree matrix 
\[\bm{D}=\begin{bmatrix}
     1  &  2  &  1\\
     2  &  1  &  1 \\
     1  &  2  &  1\end{bmatrix}.\] 
     %
     We obtain  $\eta^{\star} = 0.815$.
\end{example}
\begin{example}
For design $E_2$, we have $d_d=4$, $d_c=2$, $\bm{p}=[0.046, 0.427, 0.398, 0.129]$, $\bm{m} = [m/2, m/2]$, and 
\[\bm{D}=\begin{bmatrix}
     6  & 3 & 1 & 4\\
     14  & 0 & 2 & 6\end{bmatrix}.\]
      We obtain  $\eta^{\star} = 0.935$.
\end{example}

Fig.~\ref{fig:thres_sim} depicts $P_e$ as a function of $\eta=n/m$ for  different $m$ considering both \ac{MET} \acp{IBLT} designs $E_1$ and $E_2$. Observe that for increasing $m$, $P_e$ shows a sharp drop at $\eta \approx \eta^{\star}$ where the load threshold $\eta^{\star}$ is indicated by a vertical line. Coarsely speaking, for large $m$ one can store approximately $\eta^{\star} m$ key-value pairs in the \ac{MET} \ac{IBLT} and recover each of them with high probability. Obviously, design $E_2$ allows storing more key-value pairs than design $E_1$ in an \ac{IBLT} of a given size $m$ (for $m$ large enough).
\begin{figure}[t!]
    \centering
    \includegraphics[width=0.6\columnwidth]{./figs/MET_thres.pdf}
    \caption{Probability of unsuccessful recovery of a  key-value pair, $P_e$, as a function of $\eta$ for two different \ac{MET} \ac{IBLT} designs and different values of $m$.}
    \label{fig:thres_sim}
\end{figure}

\section{Discussion}\label{sec:conclusions}

In this paper, we have presented a  novel set reconciliation algorithm whose performance can approach that of \acf{CPI} but with  much lower complexity.
The proposed scheme can be seen as an evolution of difference digest \cite{eppstein:2011} where we introduce two major modifications.
The first one is the concept of (and analysis of) \ac{MET} \acp{IBLT}, a generalization of the \ac{IBLT} data structure, in which one allows for different types of \ac{IBLT} cells as well as key-value pairs.
The second innovation is the digital-fountain-like protocol, meaning that the number of \ac{IBLT} cells to be exchanged is not a priori fixed. Instead, one can incrementally transmit as many cells as necessary, and new cells can in principle be generated on the fly.  

The novel scheme presents two advantages compared to difference digest. 
The first one is that it is not necessary to estimate the (cardinality of the) set difference, which usually requires an additional communication round and introduces a substantial overhead.
The second one is that we only have to transmit as many cells as necessary, instead of having to oversize the \ac{IBLT} to cope with errors in the estimate of the set difference.


The proposed scheme combines the low complexity of difference digest and the efficiency of \ac{CPI}, and could thus represent an appealing solution to many data synchronization problems in  practical distributed systems.
A first possible application is  the reconciliation of large databases, an example of which is mempool synchronization in the Bitcoin network \cite{bovskov2022gensync}. 
Another important application could be remote file synchronization \cite{agarwal2006bandwidth, yan2008algorithms, Gentili2015}. 

{There are a number of interesting possible extensions to this work. 
A first interesting aspect is the extension of the proposed scheme to a multi-party set reconciliation setting, as proposed for standard \acp{IBLT} in \cite{MitzenmacherP18}.
Another interesting extension could be considering a related broadcasting setting in which a parent node holds a set $\S_P$ and multiple child nodes hold sets $\S_{C_1}$, $\S_{C_2}$, etc. In this setting the set difference between $\S_{C_i}$ and  $\S_P$ can be different for different $i$. The goal could be for the parent node to convey its set $\S_P$ efficiently to the children nodes by transmitting \ac{IBLT} cells over a broadcast channel. By relying on the proposed rate flexible constructions, a child node with a small set difference with respect to the parent node would obtain $\S_P$ faster than a child node with a larger set difference.
This extension could have applications in settings in which a parent node maintains a database 
and multiple child nodes maintain a local copy of the database.
}





\section{\acl{MET} \aclp{IBLT}}\label{sec:IBLT}

\vspace{-4mm}
\subsection{Definitions}
We first introduce a few definitions.
\begin{definition}[Key-value pair]
A key-value pair $z$ is a data structure composed of two fields, a key $x$  of length $\nu$ bits and a value $y$ of length {$\kappa$, where typically $\kappa\gg \nu$ bits}. The key $x$ is obtained as a function of $y$, $x=g (y)$ where the mapping is many to one.\footnote{This means that key collisions are in principle possible. However, by choosing $\nu$ to be large enough, one can make the key-collision probability small enough for practical applications.} 
\end{definition}
\vspace{-2mm}
\begin{definition}[Cell]
A cell $c$ is a data structure containing two different fields, \emph{data}\xspace and  \emph{count}\xspace where:
\begin{itemize}
    \item \emph{data}\xspace=(\emph{data}\xspace.x, \emph{data}\xspace.y) is a bit string of length $\nu+\kappa$. 
    The bit strings \emph{data}\xspace.x and \emph{data}\xspace.y contain, respectively, the  binary \text{XOR}\xspace of the keys and values that have been mapped to the cell.
    \item \emph{count}\xspace is an integer. It contains the number of key-value pairs that have been mapped to this cell (see \ref{sec:MET_description}).
\end{itemize}
\end{definition}
\vspace{-4mm}
\begin{definition}[IBLT]\label{def:IBLT}
{An \acf{IBLT}  is a data structure that is used to represent a set of key-value pairs. Formally, it consists of an array of $m$ cells $\bm{c}={c_1, \dots, c_m}$ and it is specified by the choice of several hash functions, that specify how key-value pairs are mapped into the \ac{IBLT} cells.} 
\end{definition}

{ \acp{IBLT} support multiple operations, such as the insertion and deletion of key-value pairs, as well as listing all inserted key-value pairs (with high probability).}
{For simplicity, and being consistent with other works in the literature, we will sometimes use $\bm{c}$ to refer to the \ac{IBLT}, thus assuming an implicit knowledge of the hash functions that specify the \ac{IBLT}. Furthermore, we will sometimes say that we `transmit and \ac{IBLT}' when we actually mean that we transmit the array of cells $\bm{c}$ and assume knowledge of the hash functions.}

\vspace{-2mm}
\begin{definition}[MET IBLT]\label{def:METIBLT}
{A \acf{MET} \ac{IBLT} is a generalization of an \ac{IBLT} that assigns different labels or types to key-value pairs and cells. }
\end{definition}
\vspace{-2mm}
{The  introduction of types allows imposing very specific constraints on the mapping of key-value pairs to cells. In Section~\ref{sec:design} we will highlight the advantages of \ac{MET} \acp{IBLT} used for set reconciliation compared to unstructured \acp{IBLT} (which can be seen as a \ac{MET} \ac{IBLT} with one single key-value pair type and one single cell type).}


\vspace{-5mm}
\subsection{MET IBLT Description} \label{sec:MET_description}
We assign to each cell and key-value pair a label referred to as type which will play a role {in how the mapping of key-value pairs into cells is done}. Let $d_c$ be the number of different cell types, $m_i$, $i \in \{1,2,\ldots,d_c\}$ be the number of cells of type $i$, and $m=\sum_i m_i$ be the length (number of cells) of the \ac{MET} \ac{IBLT}. For convenience, we assume that the cells are ordered according to their type, so that cells $c_1, c_2, \dots, c_{m_1}$ are of type 1, cells $c_{m_1+1}, c_{m_1+2}, \dots, c_{m_1+m_2}$  are of type 2, and so forth. 

Further, let the total number of different key-value pair types be $d_d$. The type of a key-value pair $z$ is determined by applying a hash function $h_{\dnp}(z.x)$ to the key $z.x$, where $h_{\dnp}(z.x)=j$ maps an input  $z.x \in \{0,1\}^{\nu}$ to an output $j \in \{1,2,\dots,d_d\}$. This hash function 
is parameterized by the probability vector ${\bm{p}=[p_j]}$. 
The vectors $[1,2,...,d_d]$ and $\bm{p}$ describe a \ac{p.m.f.}, the so-called \emph{type distribution}. 
 In particular, under the assumption that the input $z.x$ is uniformly distributed, the output of $h_{\dnp}(z.x)$ samples the type distribution.

The mapping of a key-value pair of type $j$ to cells of type $i$ is achieved through the hash function $H_{\bm{m},\bm{d}_j}(\cdot)$. It is parameterized by $\bm{m}=[m_1, m_2, \dots, m_{d_c}]$ and $\bm{\a}_j=[\a_{1,j}, \a_{2,j}, \dots, \a_{d_c,j}]$ and is used to sample at random $\a_{i,j}$ cells of type $i$ into which the key-value pair of type $j$ is mapped. The function outputs a vector $\jv=H_{\bm{m},\bm{d}_j}(z.x)$ of length $\sum_{i=1}^{d_c} \a_{i,j}$, which contains $\a_{i,j}$ indices of cells of type $i$ (where the indices are between $1+\sum_{k=1}^{i-1} m_k$ and $\sum_{k=1}^{i} m_k$).
\begin{example}[Hash function $H_{\bm{m},\bm{d}_j}$] \label{example:hash}
    Assume $\bm{m}=[2, 3, 5]$ and $\bm{\a}_j=[1, 1, 2]$. 
    We have $m_1=2$ cells of type 1, $m_2=3$ cells of type 2 and  $m_3=5$ cells of type 3. 
    Hence, indices $1$ and $2$ are associated to cells of type 1. 
    Indices $3,4$ and $5$ are associated to cells of type 2, and indices $6,7,8,9$ and $10$ are associated with cells of type 3.
    The hash function returns {4 indices in total, }one index associated with a cell of type 1, one index associated with a cell of type 2, and two indices associated with cells of type 3.
    %
    For a first key $x_1$, the hash function $H_{\bm{m},\bm{d}_j}(x_1)$ may return  $H_{\bm{m},\bm{d}_j}(x_1)=[ 1, 4, 7, 9]$. For a second key $x_2$, the hash function $H_{\bm{m},\bm{d}_j}(x_2)$ may return  $H_{\bm{m},\bm{d}_j}(x_2)=[ 2, 3, 6, 7]$.
\end{example}



\ac{MET} \acp{IBLT} support different operations that are discussed in more detail in the next sections:
\begin{itemize}
	\item Initialize$()$. This operation sets the different fields  of all the cells in the \ac{IBLT} to zero (see Algorithm~\ref{alg:init}).
	\item Insert$(z)$. The insertion operation \emph{adds} the key-value pair $z$ to the \ac{IBLT} following certain mapping rules (see Algorithm~\ref{alg:insert}).
	\item Delete$(z)$. The deletion operation \emph{removes} the key-value pair $z$ from the \ac{IBLT} (see Algorithm~\ref{alg:deletion}).
	\item Recover$()$. This operation aims at listing our all key-value pairs stored in the \ac{IBLT}. If this operation provides the full list of key-value pairs in the \ac{IBLT}, we say it succeeds, else it fails (see Algorithm~\ref{alg:list}).
\end{itemize}

\begin{figure}

\begin{minipage}{0.475\textwidth}
	\vspace{-13mm}
\begin{algorithm}[H]
	\small
	\caption{Initialization}\label{alg:init}
	\begin{algorithmic}
		\vspace{-1.5mm}
		\Procedure{Initialize$()$}{}
		\For {i = $1,2,\dots, m$} 
		\State $c_{ { i } }.\emph{count}\xspace =0$
		\State $c_{ { i } }.\emph{data}\xspace =\bm{0}$
		
		\EndFor
		\EndProcedure
	\end{algorithmic}
\end{algorithm}
\end{minipage}\hfill
\begin{minipage}{0.475\textwidth}
\begin{algorithm}[H]
			\small
			\caption{Insertion}\label{alg:insert}
			\begin{algorithmic}[H]
				\vspace{-1.5mm}
				\Procedure{Insert$(z)$}{}
				\State $i \gets h_{\dnp}(z.x)$
				\State $ \jv \gets H_{\bm{m},\bm{d}_j}(z.x)$
		        \For {k = $1,2,\dots, \text{length}(\jv)$} 
		            \State $c_{ \jvi{ k } }.\emph{count}\xspace = c_{ \jvi{ k } }.\emph{count}\xspace +1$
		            \State $c_{ \jvi{ k } }.\emph{data}\xspace =\text{XOR}\xspace \left( c_{ \jvi{ k } }. \emph{data}\xspace, \,  z \right)$
		            \EndFor
				\EndProcedure
			\end{algorithmic}
		\end{algorithm}
\end{minipage}
\begin{minipage}{0.475\textwidth}
	\vspace{-13mm}
	\begin{algorithm}[H]
			\small
			\caption{Deletion}\label{alg:deletion}
			\begin{algorithmic}
				\vspace{-1.5mm}
				\Procedure{Delete$(z)$}{}
			    \State $i \gets h_{\dnp}(z.x)$
				\State $ \jv \gets H_{\bm{m},\bm{d}_j}(z.x)$
		        \For {k = $1,2,\dots, \text{length}(\jv)$} 
		            \State $c_{ \jvi{ k } }.\emph{count}\xspace = c_{ \jvi{ k } }.\emph{count}\xspace -1$
		            \State $c_{ \jvi{ k } }.\emph{data}\xspace =\text{XOR}\xspace \left( c_{ \jvi{ k } }. \emph{data}\xspace, \,  z \right)$
		            \EndFor
			\EndProcedure
			\end{algorithmic}
		\end{algorithm}
\end{minipage}\hfill
\begin{minipage}{0.475\textwidth}
\begin{algorithm}[H]
	\small
	\caption{Recovery}\label{alg:list}
	\begin{algorithmic}
		\vspace{-1.5mm}
		\Procedure{Recover$()$}{}
		
		\While {$\exists i \in [1, m] | c_{i}.\emph{count}\xspace = 1  $} 
		\State add $z=c_{i}.\emph{data}\xspace$ to the output list
		\State call Delete $(z)$
		\EndWhile
		\EndProcedure
	\end{algorithmic}
\end{algorithm}
\end{minipage}
\vspace{-4mm}
\end{figure}

\subsection{Insertion of  a set $\S$ into a \acs{MET} \acs{IBLT}}
We consider now the insertion of a set $\S=\{z_1, z_2, \dots, z_n\}$ of $n$ elements (key-value pairs) into a \ac{MET}  \ac{IBLT}, that has been previously initialized to zero  following Algorithm~\ref{alg:init}. The elements of $\S$ are successively inserted  into the \ac{IBLT} as described by Algorithm~\ref{alg:insert}: first, every  element $z=(x,y)$ is assigned a data node type $j= h_{\dnp}(z.x)$. Next, the hash function $H_{\bm{m},\bm{d}_j}(z.x)$ is used to obtain a vector $\jv$ that contains the indices of the cells into which $z$ is to be mapped, i.e., those cells whose  \emph{data}\xspace field is \text{XOR}\xspace-ed with $z$. The respective $\emph{count}\xspace$ fields are increased by one. 



\subsection{Recovery of the set $\S$}

The recovery operation is a low complexity algorithm that aims at inverting the \ac{IBLT}, i.e., its goal is recovering all the key-value pairs that have been inserted in the \ac{IBLT}.
Algorithm~\ref{alg:list} describes the simplest form of recovery operation.  
This algorithm consists of seeking for cells with \emph{count}\xspace field equal to one. Such cells contain a single element $z$ of $\S$, which can be directly obtained from their \emph{data}\xspace field. Thus, one can extract the element $z$ and append it to the output list.
After that, one deletes $z$ from the \ac{IBLT} by calling Delete$(z)$, which effectively removes $z$ from all the cells in which it had been mapped and reduces the count fields by one. 
This process is repeated until no more cells with \emph{count}\xspace equal to one can be found. Recovery succeeds if at the end all $m$ cells of the \ac{IBLT} have  \emph{count}\xspace field  equal to zero. 
If some cells have a non-zero count,  recovery fails. 


As identified in \cite{mitzenmacher:2012}, the recovery operation is an instance of \textit{peeling decoding} \cite{luby1998analysis}. 
Peeling decoding is best understood considering a graph representation of an \ac{IBLT}. In particular, we may represent an \ac{IBLT} with $m$ cells in which a set $\S$ of $n$ elements (key-value pairs) have been inserted as a bipartite (or Tanner) graph $\mathcal{G}=(\mathcal{Z} \cup \mathcal{C}, \mathcal{E})$ composed of a set of $n$ data nodes $\mathcal{Z}$, a set of $m$ cell nodes $\mathcal{C}$ and a set of edges $\mathcal{E}$. 
As the names indicate, data nodes represent key-value pairs and cell nodes represent cells of the \ac{IBLT}. 
A data node $\mathtt{z}_i \in \mathcal{Z}$ and a cell node $\mathtt{c}_h \in \mathcal{C}$ are connected by an edge if and only if  $z_i=(x_i,y_i)$ is mapped into cell $c_h$. 
A  data node $\mathtt{z}$ and a cell node $\mathtt{c}$ are said to be neighbors if they are connected by an edge. We use the shorthand $\mathcal{N}(\mathtt{c})$ or $\mathcal{N}(\mathtt{z})$ to denote the set of all neighbors of a cell node $\mathtt{c}$ or a data node $\mathtt{z}$. The degree of a node is given by the number of edges connected to the node. Thus, the degree of a cell node equals the $\emph{count}\xspace$ field of the cell it represents.

\vspace{-3mm}
\begin{example}[Graph representation]
Fig.~\ref{fig:graph_repr} shows the graph representation of an \ac{IBLT} with $m=4$ cells in which $n=3$ pairs have been inserted. 
Key-value pair $z_1$ is mapped into cells $c_1$ and $c_4$, key-value pair $z_2$ is mapped into cells $c_1$ and $c_2$ and key-value pair $z_3$ is mapped into cells $c_2$ and $c_4$. 
Thus, we have $\emph{count}\xspace= 2$ at cells $c_1, c_2$ and $c_4$, and  $\emph{count}\xspace= 0$ in $c_3$.

In the graph representation of the \ac{IBLT}, each key-value pair $z$ is represented by a data node $\mathtt{z}$, shown as a circle in the figure. 
Each cell $c$ is represented by a cell node $\mathtt{c}$, shown as a square.  
An edge connects a data node $\mathtt{z}_i$ to a cell node $\mathtt{c}_h$ if and only if  $z_i$ is mapped into cell $c_h$. For example, $\mathtt{z}_1$ is connected to $\mathtt{c}_1$ and $\mathtt{c}_4$.
We can also observe how the degree of a cell node $\mathtt{c}$ (the number of edges attached to it) equals the $\emph{count}\xspace$ field of the cell it represents. Thus, cell nodes $\mathtt{c}_1, \mathtt{c}_2$, and $\mathtt{c}_4$ have degree 2, whereas $\mathtt{c}_3$ has degree zero.

\begin{figure}[t!]
    \centering
    \includegraphics{./figs/graph_representation}
    \caption{Graph representation of an \ac{IBLT}. The data nodes $\mathtt{z}$ are represented by circles and the cell nodes $\mathtt{c}$ by squares. An edge connects a data node $\mathtt{z}_i$ to a cell node $\mathtt{c}_h$ if and only if  $z_i$ is mapped into cell $c_h$. The degree of a cell node $\mathtt{c}$ equals the $\emph{count}\xspace$ field of the cell it represents}
    \label{fig:graph_repr}
\end{figure}
\end{example}
\vspace{-3mm}


Recovery of $\S$ can be represented as a peeling process on a bipartite graph. In particular, whenever a cell node $\mathtt{c}$ of degree one is present, its only neighbor $\mathcal{N}(\mathtt{c})=\mathtt{z}$ is determined. The key-value pair $z$ which is represented by the data node $\mathtt{z}$ is added to the output list. Next, the retrieved key-value pair is deleted from  the \ac{IBLT} which translates into the removal of all edges attached to its associated data node. 
This process is repeated until no more cell nodes of degree one are present. At this stage, if all cell nodes are of degree zero, recovery succeeded and all key-value pairs are present in the output list. Otherwise, if some cell nodes of degree larger than zero are present, recovery fails, and the output list will not contain all key-value pairs.
A particular aspect worth noting is that the graph structure is unknown to the decoder, and is revealed only during the decoding process (see Example~\ref{example:peeling}).  

\begin{example}[Peeling decoding] \label{example:peeling}
	
The different steps of the peeling process are shown in Figure~\ref{fig:graph_peeling}. Figure~\ref{fig_l_0} shows the bipartite graph representation of an \ac{IBLT} before the peeling process starts. We observe that  the \ac{IBLT} has  $m=5$ cells and it stores  $n=4$  key-value pairs. 
However, at this stage, the depicted bipartite graph is \textit{unknown} to the decoder since it does not have any knowledge about $\S$. The decoder is only aware of the $m$ cell nodes. For this reason, the data nodes, as well as the edges, are shown in gray. The graph structure will be revealed successively as the recovery operation progresses, and it will only be completely known if decoding succeeds. Otherwise, a part of the graph will remain hidden.
We can  see that cell node $\mathtt{c}_3$ has degree $1$, and thus its associated \ac{IBLT} cell $c_3$ has count $1$.  The recovery operation retrieves the only key-value pair that has been mapped to cell $c_3$, i.e., data node $z_2$, which is added to the output list of the recovery operation. Afterwards, $z_2$ is deleted from the \ac{IBLT}. In the graph representation, this translates to revealing the only neighbor of cell node $\mathtt{c}_3$, data node $\mathtt{z}_2$ (now shown in black), and deleting all edges attached to it, as shown in Figure~\ref{fig_l_1}. As a consequence, the degree of $\mathtt{c}_1$ becomes one. 
In the next step, as shown in Figure~\ref{fig_l_2}, the only neighbor of $\mathtt{c}_1$, $\mathtt{z}_1$, is revealed and all edges attached to it are removed. This reduces the degree from  $\mathtt{c}_4$ from $2$ to $1$.
Then, data node $\mathtt{z}_4$ is revealed since it is the only neighbor of $\mathtt{c}_4$. After all edges attached to $\mathtt{z}_4$ are removed, as shown in Figure~\ref{fig_l_3},  we have two cell nodes of degree $1$, namely $\mathtt{c}_2$ and $\mathtt{c}_5$, both of which have as only neighbor $\mathtt{z}_3$.
In the last step shown in Figure~\ref{fig_l_4}, first $\mathtt{z}_3$ is revealed as the only neighbor of  $\mathtt{c}_2$. Finally, all edges attached to $\mathtt{z}_3$ are erased from the graph. In this example, the recovery operation succeeded and set $\S$ was completely recovered.
\end{example}



\begin{figure}[t!]


	\subfloat[$\ell=0$]{
		\includegraphics[width=0.33\columnwidth]{figs/ltgraph_iterative_0}
		
		\label{fig_l_0}
	}
	\subfloat[$\ell=1$]{
		\includegraphics[width=0.33\columnwidth]{figs/ltgraph_iterative_1}
		\label{fig_l_1}
	}

	\subfloat[$\ell=2$]{
		\includegraphics[width=0.33\columnwidth]{figs/ltgraph_iterative_2}
		\label{fig_l_2}
	}

    \begin{center}
	\subfloat[$\ell=3$]{
		\includegraphics[width=0.33\columnwidth]{figs/ltgraph_iterative_3}
		\label{fig_l_3}
	}	



	\subfloat[$\ell=4$]{
			\includegraphics[width=0.33\columnwidth]{figs/ltgraph_iterative_4}			
			\label{fig_l_4}
	}
	\end{center}


	\caption{Peeling process on the graph representation of an \ac{IBLT} with $n=4$ key-value pairs and $m=5$ cells. The index $\ell$ is used to denote the different steps of the recovery process.}
	\label{fig:graph_peeling}
\end{figure}
\vspace{-3mm}


\section{Set Reconciliation Protocol} \label{sec:setrec_prot}

In this section, we explain how \acp{IBLT} can be used for set reconciliation and describe a set reconciliation protocol, referred to as rate-compatible protocol~ which relies on the presented \ac{MET} \acp{IBLT}.
\subsection{Set Reconciliation with \acp{IBLT}}

Following \cite{eppstein:2011}, let us first illustrate how \acp{IBLT} can be used for set reconciliation.
{First, hosts $A$ and $B$ insert all the elements of their sets $\S_A$ and $\S_B$ into the \acp{IBLT}  $\iblt{A}$ and  $\iblt{B}$, respectively. The mapping rules for both \acp{IBLT} $\iblt{A}$ and  $\iblt{B}$ are the same and are agreed upon beforehand by the hosts. Then, host $A$ sends $\iblt{A}$ to host $B$ who creates a so-called difference \ac{IBLT} $\iblt{\Delta}$. This is done by subtracting all the cells of  $\iblt{A}$ from those of $\iblt{B}$ applying Algorithm~\ref{alg:subtract} (which simply subtracts the \emph{count}\xspace field of the two cells, and xors the \emph{data}\xspace field).}

We make the following observations regarding the difference \ac{IBLT}, $\iblt{\Delta}$:
 \begin{itemize}
 	\item The elements in $\S_A \cap \S_B$, the intersection of $\S_A$ and $\S_B$, are not present in the difference \ac{IBLT} $\iblt{\Delta}$ (it is as if they had been first inserted and then deleted). 
    \item { The elements in  the set difference, $\Delta = \S_A \cup \S_B \setminus \S_A \cap \S_B$} are still present in the \ac{IBLT}. In particular:
    \begin{itemize}
        \item  The elements in $\S_B \setminus \{\S_A \cap \S_B\}$, those present in $\S_B$ but not in $\S_A$, have been inserted into $\iblt{\Delta}$ (and they have not been yet deleted).
 	      \item  The elements in $\S_A \setminus \{\S_A \cap \S_B\}$, those present in $\S_A$ but not in $\S_B$, have been deleted from  $\iblt{\Delta}$, without having been inserted before.
    \end{itemize}
 	  \item {Thus, if we represent the difference \ac{IBLT} as a bipartite graph, we obtain a graph with $m$ cell nodes, and  $\delta = |\Delta|$ data nodes (only the elements of the set difference $\Delta$ are present). Furthermore, the degree and connectivity of the remaining data nodes is preserved compared to the bipartite graph of the \acp{IBLT} of host $A$ and/or $B$ (see Example~\ref{example:diff_iblt}). } 
 \end{itemize} 

\begin{example}[Difference \ac{IBLT}] \label{example:diff_iblt}

For ease of illustration, we consider an irregular \ac{IBLT} with $5$ cells in which  host $A$ has the set $\S_A=\{z_1, z_2, z_3\}$, whereas host $B$ has $\S_B=\{z_3, z_4 \}$, hence the set difference is $\Delta =\{ z_1,  z_2, z_4 \}$.
Figs.~\ref{fig:protb_iblt_a} and \ref{fig:protb_iblt_b}, show the bipartite representation of $\iblt{A}$ and $\iblt{B}$ respectively, as well as the values stored in the cells of the \acp{IBLT}.
{The bipartite graph associated to $\iblt{\Delta}$, which is obtained by subtracting all  cells of $\iblt{A}$ from those of $\iblt{B}$, is shown in see Fig.~\ref{fig:protb_iblt_Delta}}. Observe that there are no edges connected to the elements in the intersection of the sets, ${\S_A \cap \S_B} =\{ z_3\}$. 


For illustration purposes, solid edges are attached to elements that are only in $\S_B$ , i.e., in $\S_B \setminus \S_A \cap \S_B$. 
Whenever a data node is connected to a cell node by a solid edge, the $\emph{count}\xspace$ field in the associated \ac{IBLT} cell will be increased by one. Dashed edges are attached to elements that are only in $\S_A$ , i.e., in $\S_A \setminus \S_A \cap \S_B$. 
Whenever a data node is connected to a cell node using a dashed edge, the $\emph{count}\xspace$ field in the associated IBLT cell will be decreased by one. By counting the number of solid and dashed edges we can derive the $\emph{count}\xspace$ field associated with each cell in $\iblt{\Delta}$.
Note however that  the \emph{count}\xspace of the cells in $\iblt{\Delta}$ no longer coincides with the degree of the associated cell nodes. For example, observing Fig.~\ref{fig:protb_iblt_Delta} we can see that in cell $c_3$ we have $\emph{count}\xspace=0$, although actually, its associated cell node has degree $2$, i.e., we have $\emph{data}\xspace = c_2+c_4$. 


	
\begin{figure}[t!]
		\centering
	
		\subfloat[$\iblt{A}$]{
			\includegraphics[width=0.5\columnwidth]{figs/graph_representation_diff_A.pdf}		
			\label{fig:protb_iblt_a}
		}		
		\subfloat[$\iblt{B}$]{
			\includegraphics[width=0.5\columnwidth]{figs/graph_representation_diff_B.pdf}
			\label{fig:protb_iblt_b}
		}
		
		\subfloat[$\iblt{\Delta}$]{
			\includegraphics[width=0.5\columnwidth]{figs/graph_representation_diff.pdf}
			\label{fig:protb_iblt_Delta}
		}
		
		\caption{ Example of graph representation of the \acp{IBLT} generated locally by each of the hosts. The local \ac{IBLT} of host A (transmitter), $\iblt{A}$, is shown in (a), and that of B, $\iblt{B}$, is shown in (b).}
		\label{fig:protoB_0}
\end{figure}
\end{example}


In order to be able to recover the set difference   $\Delta= (\S_A \cup \S_B) \setminus (\S_A \cap \S_B)$ from $\iblt{\Delta}$, the recovery algorithm must be altered  to deal with elements that have been deleted from the \ac{IBLT} without having been previously inserted. 
Let us recall that the (standard) recovery algorithm (Algorithm~\ref{alg:list}) searches for cells with $\emph{count}\xspace=1$, because in such cells a single set element has been inserted, and thus it can be directly recovered from the $\emph{data}\xspace$ field. 
However, the modified recovery algorithm  (Algorithm~\ref{alg:listm}) needs also to account for elements that have been deleted from the IBLT without having been previously inserted (elements in $\S_A \setminus \{\S_A \cap \S_B\}$).
In particular, the modified recovery algorithm has to search for cells in which a single element has been \emph{inserted or deleted}. 
Following \cite{eppstein:2011}, we will refer to such cells as \emph{pure}. When a cell is pure, the $\emph{data}\xspace$ field of the cell contains a copy of  the single element that has been inserted/deleted. 
\begin{example}[Purity]
If we go back to the example shown in Fig.~\ref{fig:protb_iblt_Delta}, we can see how cell $c_1$ has \emph{count}\xspace=-1, but it is not pure, since 3 key-value pairs have been mapped into it, $c_1$, $c_2$ and $c_4$. In contrast, cells $c_2$ and $c_4$, which have respectively \emph{count}\xspace -1 and 1, are pure since only one key-value pair has been mapped into them.
\end{example}

An issue consists in detecting pure cells, keeping in mind that the decoder only has access to the \ac{IBLT} cells and the mapping rules, but the graph structure is \emph{hidden}.
It is easy to see how $\emph{count}\xspace=\pm1$ is a necessary but not sufficient condition for a cell to be pure. Thus, altering the recovery algorithm to search for  cells with $\emph{count}\xspace=\pm 1$ is not sufficient.
In order to  distinguish pure cells, one can rely on the fact that the keys are obtained from the values by using a function $g(\cdot)$, \cite{eppstein:2011}. Hence, in addition to checking whether $\emph{count}\xspace= \pm1$, we also check if the key $z.x$ is valid, i.e., whether $z.x = g(z.y)$ (see Algorithm~\ref{alg:checkp}). \footnote{In fact the condition $z.x = g(z.y)$ renders the count field in the cells unnecessary for set reconciliation applications. Still, we keep it in our discussion for the  sake of clarity.} 
Note however that the function $g(\cdot)$ is a many-to-one mapping. Thus, this purity check may return true for an impure cell (see Section~\ref{sec:fail}).

Relying on this probabilistic purity check, it is possible to define a modified recovery algorithm (see Algorithm~\ref{alg:listm}) to recover the set difference from the difference \ac{IBLT} $\iblt{\Delta}$. This algorithm searches for pure cells. Whenever a pure cell is found, the only element mapped in the cell is added to the output list, and then this element is removed from the \ac{IBLT}. This is achieved by either deleting it from the \ac{IBLT} in case we have $\emph{count}\xspace = 1$ or adding it to the \ac{IBLT} in case we have $\emph{count}\xspace = -1$.

\vspace{-4mm}
\begin{example}[Modified Recovery]
Let us consider modified recovery applied to the difference \ac{IBLT} shown in Fig.~\ref{fig:protb_iblt_Delta}. For simplicity, we assume here that the purity check is perfect. Under This assumption, cell $c_2$, which has \emph{count}\xspace=-1 can be determined to be pure, allowing to recover $z_1$, which is removed from the \ac{IBLT} by relying on the addition operation. Similarly, cell $c_4$ is also found to be pure. This allows recovering $z_4$, which is removed from the \ac{IBLT} by calling the delete operation since we had \emph{count}\xspace=1 in $c_4$. Finally, $z_2$ can be recovered from either $c_1$ or $c_3$.
\end{example}

\vspace{-2mm}




\begin{figure}
	\centering
		\scalebox{0.9}{
	\begin{minipage}{0.49\textwidth}
		\vspace{-4.75mm}
		\begin{algorithm}[H]
			\small
			\caption{Cell Subtraction }\label{alg:subtract}
			\begin{algorithmic}
				\vspace{-1.5mm}
				\Procedure{$c^\dagger=$  Subtract($c$, $c^\prime$) }{}
				\State $c^\dagger$.\emph{count}\xspace =$c$.\emph{count}\xspace -$c^\prime$.\emph{count}\xspace
				\State $c^\dagger$.\emph{data}\xspace =\text{XOR}\xspace($c$.\emph{data}\xspace ,$c^\prime$.\emph{data}\xspace )
				\EndProcedure
			\end{algorithmic}
		\end{algorithm}
	\end{minipage}
	}
	\scalebox{0.9}{
\begin{minipage}{0.49\textwidth}


	\begin{algorithm}[H]
		\small
		\caption{Check Purity}\label{alg:checkp}
		\begin{algorithmic}
			\vspace{-1.5mm}
			\Procedure{$b$=IsPure$(z)$}{}			
			\If{$z.x = g(z.y)$}
			\State $b=\text{true}$
			\Else
			\State $b=\text{false}$
			\EndIf
			\EndProcedure
		\end{algorithmic}
	\end{algorithm}
\end{minipage}
}

\scalebox{0.9}{
\begin{minipage}{0.6\textwidth}


	\begin{algorithm}[H]
		\small
		\caption{Modified Recovery}\label{alg:listm}
		\begin{algorithmic}
			\vspace{-1.5mm}
			\Procedure{Recover$()$}{}			
			\While {$\exists i \in [1, m] \mid  c_{i}.\emph{count}\xspace = \pm 1~\&~ \text{IsPure}\xspace(c_{i}.\emph{data}\xspace)= \text{true}$} 
			\State add $z=c_{i}.\emph{data}\xspace$ to the output list
			\If{$c_{i}.\emph{count}\xspace =  1$}
			\State call Delete $(z)$
			\Else
			\State call Insert $(z)$
			\EndIf
			\EndWhile
			\EndProcedure
		\end{algorithmic}
	\end{algorithm}
\end{minipage}
}
\end{figure}


\vspace{-5mm}
\subsection{Rate Compatible Set Reconciliation Protocol}\label{sec:prot_def}
We propose a novel rate-compatible protocol~ that relies on \ac{MET} \acp{IBLT}.
Consider a set reconciliation setting with two hosts, $A$ and $B$, which possess  sets $\S_A$ and $\S_B$, respectively. The hosts communicate with each other through a data network in order to reconcile their sets, and it is assumed that the protocol parameters, i.e., the parameters that define the \acp{IBLT} known to both parties. The protocol follows the following steps:


\begin{enumerate}
	\item Hosts $A$ and $B$ initialize to zero a \ac{MET} \ac{IBLT} of length $m$ cells, with $d_c$ different cell types and $d_d$ key-value pair types.
	%
	Next, each host inserts all the elements of its set into the \ac{MET} \ac{IBLT}.
	%
	The thus obtained \acp{IBLT} of $A$ and $B$ will be denoted $\iblt{A}$ and $\iblt{B}$, respectively. 
	%
	We assume that the cells of $\iblt{A}$ and $\iblt{B}$ are ordered according to their type so that the first $m_1$ cells correspond to cells of type 1, followed by $m_2$ cells of type 2, and so on.

	\item Host $A$ starts sending the cells of its \ac{IBLT} $\iblt{A}$ one by one, starting with cell $c_1$, followed by $c_2$, and so on. Host $B$ creates an empty array of \ac{IBLT} cells $\iblt{\Delta_0}$. 
	%
	\item When receiving the $i$-th cell of $\iblt{A}$, host $B$ subtracts it from the $i$-th cell of its local \ac{IBLT} $\iblt{B}$ (see Algorithm~\ref{alg:subtract}),   and it appends the  resulting cell to the difference \ac{IBLT}  $\iblt{\Delta_{i-1}}$ to obtain $\iblt{\Delta_i}$. The cell subtraction operation consists of subtracting the $\emph{count}\xspace$ fields of the cells and \text{XOR}\xspace-ing the $\emph{data}\xspace$ fields.
	
	\item Host $B$ runs a modified recovery algorithm on $\iblt{\Delta_i}$ which, if successful, yields at its output the set difference $\Delta$ between $\S_A$ and $\S_B$ (see Algorithm~\ref{alg:listm}).
	
	\item If set reconciliation succeeds, host $B$ sends an acknowledgment to host $A$. 
	Otherwise, host $B$ does not send any acknowledgment, and host $A$ continues sending \ac{IBLT} cells. 
	
	\item If recovery is still unsuccessful after all $m$ cells have been transmitted, a failure is declared. 
\end{enumerate}

We make the following observations. First, when the protocol succeeds, only host $B$ is aware of the set difference. This is a common assumption in set reconciliation protocols. If necessary, host $B$ can then transmit a message to host $A$ to convey the set difference. 
Second, the protocol will fail if  recovery is still unsuccessful after exchanging all $m$ cells. However, as illustrated in Section~\ref{sec:design}, one of the advantages of relying on \ac{MET} \acp{IBLT} is that this allows designing \acp{IBLT} in which $m$ may grow on-demand, allowing in principle to generate an unlimited number of cells so that reconciliation is eventually successful.

\begin{example} [Protocol] \label{example:prot}

{Figs.~\ref{fig:protb_iblt_a_ratecomp} and \ref{fig:protb_iblt_b_ratecomp} show the graphical representation of the local \acp{IBLT} of host $A$ and $B$ ($\iblt{A}$ and $\iblt{B}$), respectively. Both bipartite graphs have a total of ${m=4}$ \ac{IBLT} cell nodes, out of which 2 are of type 1 and 2 of type 2, i.e., $m_1=m_2=2$. Furthermore, we have $\bm{D}^T=\begin{bmatrix} 1 &1 \end{bmatrix}$, i.e., there is a single data node type. 
We have $\S_A=\{ z_1, z_2, z_3 \}$ and $\S_B=\{ z_2, z_3, z_4 \}$. Thus we have that the set difference is $\Delta=\{ z_1, z_4 \}$.}


According to the rate-compatible protocol~ host $A$  sends its local \ac{IBLT} cells one-by-one to host $B$. After receiving the $i$-th cell, host $B$ subtracts it from the $i$-th cell of its local IBLT. The thus obtained difference \ac{IBLT} is denoted $\iblt{\Delta_i}$. After that, host $B$ attempts to recover the set difference by running the modified recovery algorithm, which amounts to a peeling operation on the graph representation of $\iblt{\Delta_i}$. Figs.~\ref{fig:protb_iblt_delta_1}, \ref{fig:protb_iblt_delta_2} and \ref{fig:protb_iblt_delta_3} show the graph representation of $\iblt{\Delta_i}$, for $i \in \{1,2,3\}$. {Note that the bipartite graph is provided for illustration purposes only. At the beginning it is hidden to host $B$ and is successively revealed during the recovery operation.} In particular, host $B$ attempts set reconciliation by inverting $\iblt{\Delta_i}$, i.e., by carrying out the modified recovery operation (Algorithm~\ref{alg:listm}), relying only on the $i$ cells it has so far received, and treating \ac{IBLT} cells $i+1$ onwards as if they had been erased. For this reason, when representing $\iblt{\Delta_i}$ we mark cell nodes $\mathtt{c}_{i+1}, \mathtt{c}_{i+2}, \dots$ in gray.

Observe that reconciliation is not successful after exchanging the first \ac{IBLT} cell, since $\mathtt{c}_1$ is empty in $\iblt{\Delta}$ (and all other cells are still erased).
Similarly, after having exchanged 2 cells, reconciliation is still unsuccessful, since $\mathtt{c}_2$ is not pure.
Finally, reconciliation is successful after having exchanged 3 cells. In particular, cell $\mathtt{c}_3$ is pure, allowing to recover $\mathtt{z}_1$, which is then removed from the \ac{IBLT}. This renders cell $\mathtt{c}_2$ pure, allowing to recover $\mathtt{z}_4$.
Since set reconciliation is successful on $\iblt{\Delta_3}$, host $B$ sends an acknowledgment to host $A$, and the reconciliation protocol finalizes. Cell $\mathtt{c}_4$ is in this case never exchanged.

	\begin{figure}[t!]
	\centering
	
			\subfloat[$\iblt{A}$]{
				\includegraphics[width=0.33\columnwidth]{figs/Set_rec_IBLT_A.pdf}
				\label{fig:protb_iblt_a_ratecomp}
			}
		
			\subfloat[$\iblt{B}$]{
				\includegraphics[width=0.33\columnwidth]{figs/Set_rec_IBLT_B.pdf}
				\label{fig:protb_iblt_b_ratecomp}
			}	
	
	
			\subfloat[$\iblt{\Delta_1}$]{
				\includegraphics[width=0.33\columnwidth]{figs/Set_rec_IBLT_Delta_1_v2.pdf}
				\label{fig:protb_iblt_delta_1}
			}
   
				\begin{center}   
		
			\subfloat[$\iblt{\Delta_2}$]{
				\includegraphics[width=0.33\columnwidth]{figs/Set_rec_IBLT_Delta_2_v2.pdf}
				\label{fig:protb_iblt_delta_2}
			}	
		
			\subfloat[$\iblt{\Delta_3}$]{
				\includegraphics[width=0.3\columnwidth]{figs/Set_rec_IBLT_Delta_3_v2.pdf}
				\label{fig:protb_iblt_delta_3}
			}	
		\end{center}
		
	
		\caption{Set reconciliation example. Figs. (a), (b) show  the graph representation of $\iblt{A}$ and $\iblt{B}$. Figs (c), (d) and (e) show the graph representation of  $\iblt{\Delta_i}$ , $i=1,2,3$, i.e., after having exchanged 1, 2 and 3 cells respectively. The cell nodes shown in gray represent \ac{IBLT} cells which have not yet been exchanged and are thus treated as if they were punctured (or erased).}
		\label{fig:protoB}
	\end{figure}

\end{example}


{The set reconciliation protocol described above has the advantage of exhibiting a low complexity, since it relies on the modified recovery operation, which is equivalent to a peeling operation applied to the graph representation of the difference \ac{IBLT}. One could argue that this is suboptimal, since host $B$ is actually not making use of his knowledge of $\S_B$. In fact, it is possible to improve the performance of the modified recovery operation (peeling) by relying on the knowledge of $\S_B$. For example, whenever the modified recovery operation (peeling) gets stuck because there are no pure cells, one could try to delete different elements of $\S_B$ with the hope that they are in $\Delta$ and that their deletion generates some extra pure cells allowing modified recovery (peeling). Such an approach was proposed in \cite{gabrys2014set} and it was shown that it can improve performance at the cost of an increased complexity.
}


\subsection{Reconciliation Failures}\label{sec:fail}

In the protocol described above, there are two types of events that can lead to undetected failures. 
The first type of failure is associated with the purity check (see Algorithm~\ref{alg:checkp}) returning true for a cell that is not pure.
When this happens, an \emph{erroneous} key-value pair will be added to the output list of the recovery algorithm.
Furthermore, the removal of this erroneous key-value pair from the \ac{IBLT} will corrupt a number of cells. 
With high probability, these corrupted cells will lead the receiver (host $B$) to believe that there are still some key-value pairs that have not been recovered, and the set reconciliation will run until all the $m$ cells have been exchanged, declaring then a reconciliation failure. Note that in case one use a \ac{MET} \ac{IBLT} in which the number of cells can grow unbounded, the protocol would then run forever.
Under the assumption that $g(x)$ returns a random number between 1 and $2^\kappa$, we have that the purity check of an impure cell fails with probability $2^{-\kappa}$.
Assuming a total of $m$ cells, a set difference of $\d$, and an average data node degree $\bar d$, the number of different purity checks that have to be carried out on impure cells can be upper bounded as $m+ \d \bar d$. Thus, we have that the probability of this type of failure can be upper bounded by $ (m+ \d \bar d) 2^{-\kappa}$. Hence, by choosing $\kappa$ to be large enough, this probability can be made arbitrarily small. 

The other source of failure of the protocol is the fact that host $B$ may mistakenly determine that all key-value pairs have been recovered, this not being the case. This happens when, after having exchanged $i$ cells, the modified recovery (peeling decoding) of $\iblt{\Delta_i}$  leads to an empty \ac{IBLT}, however, there are one or more key-value pairs that have not yet been recovered.
These yet unrecovered key-value pairs are not mapped to any of the first  $i$ cells, i.e., they have no edges to any of the first $i$ cell nodes. Thus, there is no way for $B$ to detect the existence of these unrecovered key-value pairs. 
The best way of dealing with this second type of failure is to never terminate the protocol before having exchanged at least $m_1$ cells, i.e., all the cells of type $1$. Assuming that $\a_{1,j}>0 \, \forall j$, this effectively solves the problem, since in this case all key-value pairs will be mapped at least to one of the first $m_1$ cells.

\subsection{Protocol Variants}\label{sec:implementation}

From a practical viewpoint, it might be of interest to change the insertion (encoding) and recovery (decoding) of \ac{MET} \acp{IBLT} in Section~\ref{sec:IBLT}. It is not necessary to generate all $m$ cells and to recover all $m$ cells at once. Rather, encoding and decoding can proceed in rounds similar to rate-compatible coding schemes (see e.g., \cite{HKM04}). We may define an encoding index vector $[i_0=0,i_1,i_2,...]$ of positive integers $0<i_{1}<i_2 ...$. In encoding round $\ell$ the encoder may generate $i_{\ell}-i_{\ell-1}$ additional cell nodes. We may for instance choose $i_{\ell}-i_{\ell-1}=m_{\ell}$. 
Likewise, we may define a decoding index vector $[j_0=0,j_1,j_2,...]$ of non-zero integers $0<j_{1}<j_2 ...$. Once $j_{\ell}$ cells are received, the decoder performs round $\ell$ of decoding. If the decoding attempt fails it waits for additional $j_{\ell+1}-j_{\ell}$ cells and retries again. For instance, we may choose $j_{\ell+1}-j_{\ell}=1 ~\forall \ell$, i.e., we attempt decoding once receiving a cell. 

\section{Introduction}\label{sec:Intro}

\vspace{-2mm}
\subsection{Motivation and Problem Description}\label{sec:setup}
Set reconciliation problems arise frequently in distributed systems 
with multiple copies of data across different nodes. Examples are redundant distributed databases, such as Amazon's Dynamo \cite{decandia2007dynamo} or Apache Cassandra \cite{cassandra}, in which multiple copies of the same database are stored in multiple data centers (nodes). Whenever a new entry is added to or deleted from the database, the change is propagated to all the nodes in the system. However, this may fail in some situations, for instance when some of the nodes are unavailable due to a hardware failure, or when communication is impaired by network congestion. The task of restoring the consistency among different copies of the database can be cast as a set reconciliation problem.
Set reconciliation protocols also find applications in distributed storage systems or remote file synchronization. In the simplest configuration one has two copies of a file at different network locations. At some point, one of the copies is updated, and one would like to update the other copy while transmitting as little data as possible to the remote network location. This problem can be converted to a set reconciliation problem by relying on tools from graph theory \cite{agarwal2006bandwidth}. 
Set reconciliation protocols can also be applied in gossip spreading protocols \cite{MitzenmacherP18}. Recently, similar techniques have been proposed to address the problem of block propagation in a cryptocurrency network \cite{Ozisik2019}, as well as to synchronize the \emph{mempools}\footnote{A mempool is a database of pending Bitcoin transactions, which have not yet been written into the Blockchain.} of nodes in the Bitcoin network \cite{bovskov2022gensync}.%

In its simplest form, the set reconciliation problem can be described as follows. Two hosts $A$ and $B$ possess (possibly) different sets, $\S_A$ and $\S_B$, respectively. The goal is to determine the set difference $\Delta$ between  the two sets, i.e.,  the set of elements that are present in the union of $\S_A$ and $\S_B$,  but not in their intersection, $\Delta= (\S_A \cup \S_B) \setminus (\S_A \cap \S_B)$. In order to reconcile the sets, $A$ and $B$ exchange information  and perform certain computations. Thereby, both communication complexity (overhead) and computational (time) complexity shall be kept as small as possible. 
Intuitively, when the set difference $\d$ is large, $A$ and $B$ may simply exchange their sets. However, this solution turns out to be highly sub-optimal when the set difference $\d$ is small when more sophisticated algorithms can be applied to reduce communication complexity. 

A common approach to set reconciliation (and other similar problems) is the use of log-files. The prerequisite here is the existence of  a so-called prior context between the parties involved in the protocol, i.e. host $A$ and $B$. In our setting, this translates to the assumption  that  sets $\S_A$ and $\S_B$ were synchronized (i.e., identical) at a previous point in time $\tau$. After that, both hosts keep track respectively of all the changes applied to  $\S_A$ and $\S_B$ in a so-called log-file that is stored locally. After $d$ units of time have elapsed, i.e., at time $\tau + d$, the two sets can be reconciled relying on  the log-files.
While being simple, the use of log-files becomes inefficient when the network connectivity is bad, the storage medium unreliable, or when changes to the sets $\S_A$ and $\S_B$ happen very frequently. Finally, these schemes do not scale well in multi-party settings (when one aims at synchronizing more than 2 sets), given that they require the existence of prior context between all pairs of nodes. Our focus instead will be on context-free set reconciliation.


\subsection{Related Works}

Fundamental limits for one-way set reconciliation, i.e., {when one single communication message is allowed}, were studied in \cite{Karpovsky2003}. When the elements in $\S_A$ and $\S_B$ are $\ell$ bit vectors, i.e., $\S_A, \S_B\subset \{0,1\}^\ell$, 
and assuming that  an upper bound $t$ to the set difference $\d=|\Delta|$ is known, i.e., $\d \leq t$, exact set reconciliation requires transmitting $\sim t \ell$ bits. In contrast, when no upper bound is known, exact set reconciliation requires transmitting the whole set. 
Given an upper bound $t$ to the set difference $\d$,  set reconciliation can be carried out relying on  a binary code of length $2^\ell$ which can correct  $t$ errors. This solution is shown to have an optimal communication complexity when using a perfect code \cite{Karpovsky2003}. However, it requires working with a code of length $2^\ell$ which turns out to be impractical for the values of $\ell$ required in most applications. 

In \cite{Minsky2003} a scheme based on \acf{CPI} was proposed which achieves nearly optimal communication complexity. In particular, when an upper bound $t$ to the set difference $\d$ is known, exact set reconciliation is possible with communication complexity  $\sim t\ell$ and time complexity $\mathcal{O}(t^3)$. 
When an upper bound to $\d$ is not known, \cite{Minsky2003} proposes an approximate\footnote{By approximate it is meant that the scheme may fail, so that the parties wrongly believe that their sets are reconciled, but they are actually not. In practice, the scheme can be designed to make this failure probability arbitrarily low, at the cost of an increase in the communication cost.} set reconciliation scheme. In this case, the scheme requires an additional feedback message and is thus, strictly speaking, no longer a one-way reconciliation protocol. Instead, we have a reconciliation scheme that requires one round of communication. This approximate scheme has communication complexity $\sim \d\ell$ and time complexity $\mathcal{O}(\d^4)$.

In \cite{eppstein:2011}  a low-complexity approximate set reconciliation scheme based on  \acfp{IBLT} was proposed, which also requires one communication round.
In brief, an \ac{IBLT} \cite{goodrich:2011} is a probabilistic data structure that  supports the insertion and deletion of set elements, as well as listing of all the elements contained in the \ac{IBLT}, provided that the number of elements in the \ac{IBLT} is not too large (a formalization of these concepts follows in Section~\ref{sec:IBLT}). From a data structure point of view, an \ac{IBLT} can be broken down into cells, which have size $\sim \ell +\log{\ell}$. 
When an upper bound to the set difference is known, the communication complexity was shown to be $\sim c \, t (\ell+\log \ell)$, where $c\approx 1.22$, and the time complexity to be $\mathcal{O}(t (\ell + \log \ell ))$ \cite{goodrich:2011}. 

\ac{IBLT}-based set reconciliation requires inverting an \ac{IBLT}, an operation which is, in essence, identical to erasure decoding \cite{Eli54}. As such, different \ac{IBLT} designs have been proposed in literature, which are akin to different erasure code designs.
The original construction in \cite{eppstein:2011} relies on \emph{regular} \acfp{IBLT} in which each set element is mapped into the same number of  \ac{IBLT} cells. By moving to \emph{irregular}  \acp{IBLT} it is possible to improve the constant $c$. In particular, it was first shown in \cite{rink2013mixed} how $c=1.09$ can be achieved, by relying on irregular \acp{IBLT} with two different degrees. In \cite{lazaro21:iblt} a density evolution analysis of irregular \ac{IBLT} was presented which allows  computing $c$ and thus optimizing the irregular \ac{IBLT}. Furthermore, relying on results for random access protocols \cite{narayanan2012iterative}, it was argued that \acp{IBLT} with constants $c$ arbitrarily close to $1$ can be found.  

A shortcoming of \ac{IBLT}-based set reconciliation \cite{eppstein:2011} is the fact that it requires knowledge of an upper bound $t$ to the set difference. 
In most cases, rather than an upper bound to $\d$, an (imperfect) estimate of $\d$ is available, denoted by $\hat{\d}$. Obtaining this estimate usually requires  an additional communication round  between the hosts,  which represents an additional overhead \cite{eppstein:2011}. In practice, the set difference estimate $\hat{\d}$ can substantially differ from the actual set difference $\d$. Intuitively, an over-estimation ($\hat{\d} > \d$) results in an over-sizing of the \ac{IBLT} and thus in an unnecessarily high communication cost, whereas an under-estimation ($\hat{\d} < \d$) results in  a high probability of failure of the set reconciliation algorithm. To reduce the probability of a failure, \cite{eppstein:2011} considers an over-sizing of the \ac{IBLT}. Additionally, a larger \ac{IBLT} can be sent upon a failure, attempting  set reconciliation using only this second \ac{IBLT}. This approach is clearly inefficient since it discards the first exchanged \ac{IBLT}. This inefficiency was identified in \cite{Ozisik2019}, where it was proposed to use the two \acp{IBLT} to reconcile the sets, reducing the communication cost.

{Additionally, other works in literature have proposed approximate set reconciliation protocols based on so-called approximate set membership data structures. In \cite{Skjegstad2011} a low-complexity  multi-round protocol based on the exchange of Bloom filters was proposed. Protocols based on the exchange of counting Bloom filters and Cuckoo filters were proposed in  \cite{Guo2013} and \cite{Luo2019}, respectively.
In \cite{kruber2020approximate} approximate set reconciliation protocols based on the exchanged of hash lists, Bloom filters and Merkle trees were proposed and compared.
For a comparison of the different set reconciliation protocols in different practical settings, we refer the reader to \cite{bovskov2022gensync}.}

\vspace{-6mm}
\subsection{Contribution}

\vspace{-2mm}
In this work, we introduce a novel approach to \ac{IBLT}-based set reconciliation. In contrast to previous works, our approach does not require an upper bound to (or an estimate of) the set difference $\d$. Our work borrows ideas from digital fountain codes \cite{byers02:fountain}. In particular, we let the transmitter (say host $A$) send the cells of the \ac{IBLT} one by one. After receiving some cells, the receiver (host $B$) can attempt to reconcile the sets. If set reconciliation fails, the receiver simply waits for more cells and re-attempts set reconciliation. When set reconciliation is successful, the receiver (host $B$) sends an acknowledgment to the transmitter so that it stops sending cells. 
This approach spares the overhead necessary for set difference estimation which is considerable, especially when the set difference is small \cite{eppstein:2011}. %
To fully exploit the advantages of our approach, we introduce a novel \ac{IBLT} structure which we term \acf{MET} \ac{IBLT}. This novel data structure borrows ideas from rate-compatible codes, in particular from \ac{MET} \ac{LDPC} codes \cite{richardson2002multi}.
The main advantage of the adoption of a \ac{MET} structure is that it allows increasing on demand the number of \ac{IBLT} cells while 
still being able to list all the elements inserted in the \ac{IBLT} with high probability. This is akin to the feature of rate-compatible codes of operating close to capacity at multiple code rates.

The remaining of the paper is structured as follows. In Section~\ref{sec:IBLT} we introduce the basics of \ac{MET} \acp{IBLT}. In Section~\ref{sec:analysis} we
develop an analysis in order to assess the communication efficiency of \ac{MET} \acp{IBLT}. We develop a flexible set reconciliation protocol using \ac{MET} \acp{IBLT} in Section~\ref{sec:setrec_prot} followed by a design example in Section~\ref{sec:design} together with simulation results. Section~\ref{sec:conclusions} provides a  discussion of the contribution.





 


\section{MET IBLT Design}\label{sec:design}

The rate-compatible protocol~ in Section~\ref{sec:setrec_prot} requires a suitable \ac{MET} \ac{IBLT} design that provides good performance for a wide range of set differences $\d$, considering that $\d$ is not (perfectly) known a priori. A simple solution would be to perform an \ac{IBLT} design for large $\d$  by relying on the results of Section~\ref{sec:analysis} (i.e., we choose an \ac{IBLT} with $\eta^{\star}$ close to one). However, when $\d$ is small, there is no guarantee that this scheme will work with reasonable communication complexity, i.e., that it will be efficient.
To illustrate why this is the case, let us consider a $k$-regular \acp{IBLT} of length $m$. We focus on the graphical representation of the difference \ac{IBLT} $\iblt{\Delta_{h}}$ after $h$ cells have been exchanged. Let us now consider a key-value pair node associated with the set difference $\Delta$. The probability that this node has no edges attached to any of the first $h$ cell nodes can be approximated as 
\begin{align}\label{eq:dec_failure}
  \left( \frac{m-h}{m} \right)^k.
\end{align}
Note that the expression in~\eqref{eq:dec_failure} yields a lower bound on the probability of recovery failure $P_e$. For fixed $k$, e.g., $k=3$, this probability is high, unless $\ell$ is  close to $m$ (see also \cite[Section~6]{Shokrollahi2009} for a more detailed discussion). 
Thus, we expect the rate-compatible protocol~ to perform poorly when employing standard \acp{IBLT}. This is illustrated by some simulation results in Section~\ref{sec:numres}. The issue can be overcome by  \ac{MET} \acp{IBLT}. In particular, we can choose $m_1$ to be small, and forbid the protocol to terminate before having exchanged $m_1$ cells. This ensures that every key-value pair in $\Delta$ is mapped to a cell of type $1$.


\subsection{Design Example}

Consider a \ac{MET} \ac{IBLT} design in which the number of cells of type $i$ is $m_i= 2^{i-1} m_1$.
We use the tools in Section~\ref{sec:analysis} to predict the asymptotic performance of the \ac{MET} \ac{IBLT}.
For simplicity, we set $d_d=3$, and consider a degree matrix in the form
     \[
    
    
    
    
    
    
    
    
    
     \bm{D}^\text{T}=
     \begin{bmatrix}
	\a_{1,1}  & \a_{2,1} & \a_{3,1} & \a_{4,1} & \a_{5,1} & \cdots & \a_{5,1} \\
	\a_{1,2}  & \a_{2,2} & \a_{3,2} & \a_{4,2} & \a_{5,2} & \cdots & \a_{5,2} \\
	\a_{1,3}  & \a_{2,3} & \a_{3,3} & \a_{4,3} & \a_{5,3} & \cdots & \a_{5,3} 
\end{bmatrix}
       \]
where the fifth and successive rows are equal to the fourth row. This yields a design in which a potentially unlimited number of cell types $d_c$ can be generated\footnote{Strictly speaking, the analysis presented in Section~\ref{sec:analysis} only applies to the case in which the number of cell types $d_c$ is constant, but, in practice, this does not hinder us from allowing the number of cell types to grow on demand.}.
Let us now denote by $\eta^{\star}_i$ be the load threshold of the \ac{MET} \ac{IBLT} when considering only the first $\sum_{j=1}^{i} m_j$ cells.
The parameters of this design,  $\bm p$ and $\bm{D}$, are determined by relying on a multi-target optimization. In particular, we choose  $\bm p$ and $\bm{D}$, to maximize the minimum among $\eta^{\star}_i$,
$[ \bm p, \bm{D} ] = \underset{\bm p, \bm{D}}{\arg \max} \left( \min_{i} \eta^{\star}_i \right) .
$
An approximate solution to this optimization problem was obtained by relying on simulated annealing \cite{kirkpatrick1983optimization}, an optimization algorithm to approximate the global optimum of a given function. For the current design example we set $ i\in \{1, 2, \dots, 8\}$. Additionally, we introduce the constraint $\a_{i,j}\leq 5\, \forall i,j$ in order to limit complexity.\footnote{By removing the constraint our optimization algorithm yields only slightly higher thresholds.} The optimization yields

\[
\bm p=[ 0.1959, 0.1904, 0.6137], \text{and }
\bm{D}^\text{T}=\begin{bmatrix}
	3  & 1 & 1 & 1 & 1 & \cdots & 1 \\
	4  & 4 & 4 & 4 & 5 & \cdots & 5 \\
	2  & 1 & 1 & 1 & 1 & \cdots & 1 
\end{bmatrix}
     \]
and the load thresholds obtained are
\begin{align}
    \bm{\eta}^{\star}= [ & 0.7948,    0.7837,    0.7882,    0.8025, 
               0.8042,    0.7967,    0.7895, 0.7856 ]. 
\end{align}
Although we only consider the first $8$ cell types in our optimization, the resulting \ac{MET} \ac{IBLT} still retains a good performance when additional cell types are included by replicating the last row $\bm{D}$. In particular, we have $\eta^{\star}_9=0.7842$, $\eta^{\star}_{10}=0.7837 $ and $\eta^{\star}_{i}= 0.7830$ for $i\geq 11$.

\begin{remark}
This multi-target optimization  only  considers the performance at intermediate points in which all the cells of type $i$ have been received. In the Appendix, we introduce an extension of the analysis in Section~\ref{sec:analysis} that allows deriving  the load threshold of a \ac{MET} \ac{IBLT} which also considers the case where only a fraction of cells of a certain type has been received.
\end{remark}

\vspace{-7mm}
\subsection{Simulation Setup}
We consider a setup with two hosts, $A$ and $B$, who want to reconcile their sets $\S_A$ and $\S_B$ by communicating over a data network without having any knowledge about the set difference $\d$.
We apply the set reconciliation protocol of Section~\ref{sec:prot_def} with a \ac{MET} \ac{IBLT} from Section~\ref{sec:design} and compare the performance with two other schemes available in literature, difference digest \cite{eppstein:2011} and \acf{CPI} \cite{Minsky2003}.

Difference digest \cite{eppstein:2011} is an \ac{IBLT}-based set reconciliation algorithm that relies on the use of regular \acp{IBLT}. In contrast to the other two schemes, difference digest requires an estimate of the set difference, which is computed in an initial communication round, in which host $B$ sends to host $A$ a data structure known as strata estimator which is used to obtain an estimate $\hat{\d}$ of the set difference size $\d$. 
Host $A$ then calculates a worst-case set difference size $t=c\cdot \hat{\d}$, where $c$ is chosen so that $t>d$ with high probability (e.g., $0.99$). Next, host $A$ creates an \ac{IBLT} of size $m$, where $m$ is chosen so that the recovery operation is successful with high probability (e.g., probability $0.99$) when $t$ key-value pairs are inserted  in the \ac{IBLT}. After that, host $A$ inserts its set $\S_A$ in the \ac{IBLT} $\iblt{A}$ and sends it to host $B$. 
Host $B$ then also inserts his set $\S_B$ in an \ac{IBLT} $\iblt{B}$ of size $m$ and then computes the difference \ac{IBLT} by subtracting the cells of $\iblt{B}$ and $\iblt{A}$, which yields the \ac{IBLT} $\iblt{\Delta}$ that also has length $m$. Next, host $B$ attempts to recover the set difference $\Delta$ by applying a  modified recovery operation (see Algorithm~\ref{alg:listm}). If recovery is successful, set reconciliation succeeds, otherwise, we will simply assume that set reconciliation is declared as unsuccessful.\footnote{In \cite{eppstein:2011} it was actually proposed to reattempt reconciliation by employing \acp{IBLT} of length $2m$. By allowing difference digest to simply fail we will be penalizing slightly the two other schemes, which in principle always continue until reconciliation is successful.}

The second scheme, \ac{CPI}, makes use of the characteristic polynomial of a set. Consider a set  $\S=\{ z_1, z_2, ..., z_n \}$ where the elements $z_i$ are chosen from $\mathcal{U}=\{0,1\}^\ell$. The characteristic polynomial of set $\S$ over the finite field $\mathsf{F}_q$ with $q>2^{\ell}$ is defined as
\[
\mathcal{X}_{\S}(Z) = (Z-z_1) (Z-z_2) \dots (Z-z_n)
\]
where one relies on an {injective} mapping of elements of $\mathcal{U}$ to $\mathsf{F}_q$.
The key principle behind \ac{CPI} is that given $n$ evaluations of $\mathcal{X}_{\S}(Z)$ it is possible to recover the set $\S$ since its elements correspond to the zeros of the characteristic polynomial  $\mathcal{X}_{\S}(Z)$. 
As we sketch next, \ac{CPI} can be also operated in a rateless fashion \cite{Minsky2003} to minimize the communication cost and does not require an estimate of the set difference.
First of all, host $A$ chooses a list of evaluation points  $r_1, r_2, \dots$ at which it will evaluate the characteristic polynomial of its set.\footnote{in particular, the evaluations points $r_1, r_2, \dots$ are chosen among those elements of $\mathsf{F}_q$ to which no element of $\mathcal{U}$ is mapped.}
Next, host $A$ continuously evaluates the characteristic polynomial of his set $\S_A$, $\mathcal{X}_{\S_A}(Z)$, at  the  evaluation points, $r_1, r_2, \dots$ and sends the evaluations $\mathcal{X}_{\S_A}(r_1)$, $\mathcal{X}_{\S_A}(r_2),\dots$ to host $B$, and it does so until it receives an acknowledgment from host $B$ which indicates that reconciliation was successful. Thereby, host $B$ continuously attempts to recover the set difference $\Delta$, by evaluating the ratio of two characteristic polynomials ${ \mathcal{X}_{\S_A}(r_i) } / { \mathcal{X}_{\S_B}(r_i)}$. 
For a set difference of $\d$ this protocol has overall complexity $\mathcal{O}(d^4)$  \cite{Minsky2003}. 

\vspace{-5mm}
\subsection{Simulation Results}\label{sec:numres}
We compare the performance of the three schemes in terms of communication cost, i.e., in terms of the amount of data, measured in bits, that needs to be exchanged.
For illustration purposes, we consider the setup from \cite{eppstein:2011} in which the cardinality of the  $\S_A$ and $\S_B$ is $10^5$ and the set elements are chosen from $\mathcal{U}=\{0,1\}^{32}$. Following \cite{eppstein:2011}, we allocate a total of $12$ bytes for each \ac{IBLT} cell: $4$ bytes for the $\emph{count}\xspace$ field and $8$ bytes for the $\emph{data}\xspace$ field ($4$ bytes for the key and $4$ bytes for the value). 
For difference digest we use the same configuration as in \cite{eppstein:2011}, thus in the initial communication round to estimate the set difference, we employ a hybrid strata estimator with 7 strata, each with 80 cells per \ac{IBLT}, and a min-wise estimator with 2160 hashes. Hence, the resulting strata estimator (the data structure used to estimate the set difference) has a total size of $15$ kB.
In the second communication round in which the actual set reconciliation takes place, we use a degree-$3$ regular \ac{IBLT}.
For \ac{CPI}, we use a configuration in which every evaluation point takes $10$ bytes\footnote{We operate on a finite field with $2^{40}$ Hence we need $5$ bytes to specify the point at which we evaluate the polynomial and another $5$ bytes for the evaluation of the polynomial.}. Finally, for the rate-compatible protocol~ we  use $12$ bytes for each \ac{IBLT} cell, the same as in difference digest, and the \ac{MET} \ac{IBLT} parameters reported in Section~\ref{sec:design}.

Fig.~\ref{fig:comparison} shows the communication cost, i.e., the total amount of transmitted data needed for set reconciliation for the three schemes. For difference digest, the figure also reports the total data transmission without considering the strata estimator (which takes exactly $15$ kB in our example).
For the rate-compatible protocol~ we show two performance curves. The first one uses the \ac{MET} \ac{IBLT} design described in Section~\ref{sec:design} setting $m_1=50$. The second one uses a 3 regular distribution with $m=10^4$.

Observe that the rate-compatible protocol~ when using a \ac{MET} \ac{IBLT} has only a slightly higher communication cost than the more complex \ac{CPI} scheme, and it clearly outperforms difference digest. This can be attributed to two different effects. The first one is the presence of an initial communication round to estimate the set difference in difference digest. This inefficiency dominates the performance for small $\d$ since in this case the size of the strata estimator is much larger than the actual data that has to be exchanged to reconcile the sets.
The second one is the rate-compatible nature of the protocol which allows transmitting \ac{IBLT} cells incrementally. %

 The performance of the rate-compatible protocol~ when using a degree 3 regular \ac{IBLT} is also depicted. Observe that the performance is very poor compared to the \ac{MET} \ac{IBLT} design. This is  due to the presence of key-value pairs which are not mapped to the first cells exchanged (see discussion in Section~\ref{sec:design}) and hence cannot be recovered upon reception of those cells.

	\begin{figure} [t!]
		\centering
		\includegraphics[width=0.6\columnwidth]{figs/comparison_diff_digest_CPI_rateless_zoom_log.pdf}
	
	
		\caption{Data transmission required to reconcile sets with $10^5$ elements as a function of the set difference $\d$. The solid line with circle markers represents the data transmitted by difference digest \cite{eppstein:2011}, including the strata estimator necessary to estimate the set difference. The gray dashed line with square markers represents the data transmitted by difference digest ignoring the size of the strata estimator for the computation of the communication cost. 
		The dash-dotted with diamond markers represents the CPI scheme in \cite{Minsky2003}. Finally, the  densely dotted lines with x and pentagon markers represent the rate-compatible protocol~ introduced in this paper using a \ac{MET} \ac{IBLT} and a 3-regular \ac{IBLT}.}
		\label{fig:comparison}
	\end{figure}







