论文标题
用于求解线性方程分布式系统的私人和有限的算法
A Private and Finite-Time Algorithm for Solving a Distributed System of Linear Equations
论文作者
论文摘要
本文研究了一个线性方程式系统，称为$ ax = b $，该系统是水平分区的（$ a $ a $ and $ b $），并存储在连接固定有向图的$ m $设备的网络上。我们设计了一种快速分布式算法，用于求解这种分区的线性方程系统，此外，它可以保护本地数据的隐私性免受网络中大多数$τ$节点损坏的诚实但充满好心的对手。首先，我们提出了泰坦，私人有限时间平均共识算法，用于解决定向图上的一般平均共识问题，同时保护私人本地数据的统计隐私范围，以免受诚实却令人讨厌的对手的影响。其次，我们提出了一个分布式的线性系统求解器，该求解器涉及每个代理/设备根据本地私人数据计算更新的代理/设备，然后使用Titan使用私有聚合。最后，我们在有限的回合中显示了求解器与最小二乘解决方案的融合，以及本地线性方程的统计隐私对诚实但热情的对手的统计隐私，前提是该图具有较弱的顶点连接性至少为$τ+1 $。我们执行数值实验来验证我们的主张，并通过比较计算，通信和记忆成本来比较我们的解决方案与最新方法。
This paper studies a system of linear equations, denoted as $Ax = b$, which is horizontally partitioned (rows in $A$ and $b$) and stored over a network of $m$ devices connected in a fixed directed graph. We design a fast distributed algorithm for solving such a partitioned system of linear equations, that additionally, protects the privacy of local data against an honest-but-curious adversary that corrupts at most $τ$ nodes in the network. First, we present TITAN, privaTe fInite Time Average coNsensus algorithm, for solving a general average consensus problem over directed graphs, while protecting statistical privacy of private local data against an honest-but-curious adversary. Second, we propose a distributed linear system solver that involves each agent/devices computing an update based on local private data, followed by private aggregation using TITAN. Finally, we show convergence of our solver to the least squares solution in finite rounds along with statistical privacy of local linear equations against an honest-but-curious adversary provided the graph has weak vertex-connectivity of at least $τ+1$. We perform numerical experiments to validate our claims and compare our solution to the state-of-the-art methods by comparing computation, communication and memory costs.
