论文标题
协作优化的弹性：冗余和独立的成本功能
Resilience in Collaborative Optimization: Redundant and Independent Cost Functions
论文作者
论文摘要
该报告考虑了多代理协作优化中拜占庭式断层耐受性的问题。在此问题中，每个代理都有局部成本函数。协作优化算法的目的是计算代理成本函数的最低总计。我们考虑了一定数量的代理可能是拜占庭式有缺陷的情况。这种错误的代理可能不会遵循规定的算法，并且可能会发送有关其当地成本功能的任意或错误信息。在存在此类故障代理的情况下，一个合理的目标是最大程度地减少非故障剂的总成本。在本报告中，我们表明，只有当非故障代理的成本功能具有最低的冗余属性时，才能实现此目标。我们提出了不同的算法，这些算法能够实现对故障药物的容忍度，并证明了算法的复杂性与代理成本功能的性能之间的权衡。 此外，我们还考虑成本功能独立或不满足最小冗余属性的情况。在这种情况下，我们通过引入称为弱弹性的度量来量化对故障剂的公差。我们提出了一种算法，该算法在少数群体中的故障且成本函数是非负数时会达到较弱的弹性。
This report considers the problem of Byzantine fault-tolerance in multi-agent collaborative optimization. In this problem, each agent has a local cost function. The goal of a collaborative optimization algorithm is to compute a minimum of the aggregate of the agents' cost functions. We consider the case when a certain number of agents may be Byzantine faulty. Such faulty agents may not follow a prescribed algorithm, and they may send arbitrary or incorrect information regarding their local cost functions. A reasonable goal in presence of such faulty agents is to minimize the aggregate cost of the non-faulty agents. In this report, we show that this goal can be achieved if and only if the cost functions of the non-faulty agents have a minimal redundancy property. We present different algorithms that achieve such tolerance against faulty agents, and demonstrate a trade-off between the complexity of an algorithm and the properties of the agents' cost functions. Further, we also consider the case when the cost functions are independent or do not satisfy the minimal redundancy property. In that case, we quantify the tolerance against faulty agents by introducing a metric called weak resilience. We present an algorithm that attains weak resilience when the faulty agents are in the minority and the cost functions are non-negative.
