Distributed Algorithms that Solve Boolean Equations with Local and Differential Privacies

Hongsheng Qi, Bo Li, Rui-Juan Jing, Lei Wang, Alexandre Proutière, Guodong Shi

Abstract

This paper proposes distributed algorithms for solving systems of Boolean equations over a network where each node holds a private local equation. The objective is to compute the exact set of global solutions without nodes exchanging their private equations. The approach involves "lifting" discrete Boolean equations into linear algebraic equations in a high-dimensional space, which are then solved using distributed linear algebraic equation (DistributedLAE) solvers. We prove that with random initializations, the exact solution set is recovered with high probability. Furthermore, we integrate differential privacy via the Laplace mechanism and provide a method for distributedly verifying satisfiability.

Introduction

Boolean equations are fundamental to computer science, underpinning fields such as circuit design, cryptography, and gene regulatory network modeling. Solving a system of these equations—a variation of the Boolean Satisfiability (SAT) problem—typically requires a central processor with access to all constraints. However, in decentralized networks like IoT clusters or multi-agent systems, privacy concerns often prevent nodes from sharing their local data.

This research addresses the challenge of finding a global solution that satisfies all local constraints under three strict requirements: local privacy (no direct exchange of equations), decentralized computation (neighbor-only communication), and differential privacy (mathematical guarantees against eavesdropping).

Methodology

The proposed framework utilizes a three-stage pipeline to bridge the gap between discrete logic and distributed continuous optimization.

Boolean Matricization (The "Lifting" Trick)

Each node first converts its Boolean equation into a linear algebraic equation. By using a basis of Boolean vectors to represent the $2^m$ possible states of $m$ variables, the problem is "lifted" from a discrete search space into a high-dimensional Euclidean space. This transformation allows Boolean logic to be handled via linear algebra.

Commutative diagram illustrating the lifting of a Boolean function $g$ to a linear mapping $M_g$.

As illustrated in the figure above, the Boolean function $g(x)$ is mapped to a linear transformation $M_g$ acting on the lifted vector representations $\delta_{2^m}^{\lfloor x \rfloor}$. This mapping ensures that the discrete logic is preserved within the continuous linear subspace.

Distributed Projection Consensus

Once lifted, the network employs a DistributedLAE solver. Nodes maintain a local state and update it by projecting it onto their own solution space and then averaging it with their neighbors' states. By repeating this process with multiple random initializations ($2^m + 1$ times), the nodes collectively map out the entire affine subspace of solutions. The authors prove that if initial values are i.i.d. selected from a uniform distribution in a high-dimensional cube, the entire solution set can be reconstructed with high probability.

After identifying the continuous subspace, each node locally executes a specialized search algorithm to "pull" the discrete Boolean solutions out of the continuous space, effectively reversing the lifting process.

Privacy and Verification

To ensure differential privacy, the authors integrate the Laplace Mechanism, injecting calculated noise into the consensus steps. They derive an explicit noise level required to ensure the algorithm is $\epsilon$-differentially private, revealing a clear tradeoff: higher privacy requires more iterations ($T$) or rounds ($K$) to maintain accuracy.

Additionally, the paper introduces a method for Distributed Verification. If a system is unsatisfiable, the nodes' states will converge to different limits, providing a definitive signal that no global solution exists.

Key Results and Discussion

  • Exactness: The algorithm is proven to return the exact set of Boolean solutions with high probability for solvable systems.
  • Complexity: The computational complexity is approximately $O(2^{3m} + 2^{2m}n)$, where $m$ is the number of variables and $n$ is the number of nodes.
  • Robustness: Numerical simulations demonstrate that the algorithm remains functional even with moderate levels of injected noise, though accuracy naturally improves as noise decreases.

Limitations and Future Work

The primary limitation is the "curse of dimensionality." Because the vectors grow at a rate of $2^m$, the algorithm becomes computationally and communicationally expensive as the number of variables increases. Future research may explore sparse representations or compression techniques to mitigate this overhead. Additionally, extending the work to find "least squares" approximate solutions for over-determined systems remains an open area for exploration.

Summary updated

Abstract

In this paper, we propose distributed algorithms that solve a system of Boolean equations over a network, where each node in the network possesses only one Boolean equation from the system. The Boolean equation assigned at any particular node is a {\em private} equation known to this node only, and the nodes aim to compute the exact set of solutions to the system without exchanging their local equations. We show that each private Boolean equation can be locally lifted to a linear algebraic equation under a basis of Boolean vectors, leading to a network linear equation that is distributedly solvable using existing distributed linear equation algorithms as a subroutine. A number of exact or approximate solutions to the induced linear equation are then computed at each node from different initial values. The solutions to the original Boolean equations are eventually computed locally via a Boolean vector search algorithm. We prove that given solvable Boolean equations, when the initial values of the nodes for the distributed linear equation solving step are i.i.d selected according to a uniform distribution in a high-dimensional cube, our algorithms return the exact solution set of the Boolean equations at each node with high probability. Furthermore, we present an algorithm for distributed verification of the satisfiability of Boolean equations, and prove its correctness. Finally, we show that by utilizing linear equation solvers with differential privacy to replace the in-network computing routines, the overall distributed Boolean equation algorithms can be made differentially private. Under the standard Laplace mechanism, we prove an explicit level of noises that can be injected in the linear equation steps for ensuring a prescribed level of differential privacy.
BibTeX
@misc{qi2020distributed,
  author = {Hongsheng Qi and Bo Li and Rui-Juan Jing and Lei Wang and Alexandre Proutière and Guodong Shi},
  title = {{Distributed Algorithms that Solve Boolean Equations with Local and Differential Privacies}},
  year = {2020},
  eprint = {2002.08064},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2002.08064},
}
Figure