CAREER: Foundations for Attack-Resistant, Collaborative Peer-to-peer Systems

贾里德·萨亚新墨西哥大学：抗攻击协作对等系统的基础0644058小组ID：070111摘要一组代理如何实现目标，尽管一些代理努力防止这种情况发生？这个重要的问题跨越了许多学科，包括政治学、经济学、数学和计算机科学。在这项提案中，我们通过关注以下问题来探讨这一问题。一组n个代理想要计算n个输入的函数f的值，其中每个代理持有f的唯一输入。我们的目标是创建一种分布式算法，确保每个代理学习f的输出。我们的算法将具有抗攻击能力，因为它将正确工作，即使多达固定比例的代理被试图防止函数被计算的无所不知的对手控制时也是如此。我们的算法也将是可伸缩的，因为网络中的每个节点发送和接收多个消息和比特，这些消息和比特在n即O(Logcn)中仅是多对数，其中c是固定常数。我们正在利用几种工具来解决这个问题，包括：使用类似扩展器的图形来实现可靠的通信；使用小型随机选择的委员会作为单个值得信赖的功能单元；以及算法技术来加强对拒绝服务攻击的防御。解决这个问题可能会在投票、垃圾邮件检测、蠕虫和恶意软件检测、分布式文件系统、拍卖和机制执行、协作过滤和网络搜索等不同领域产生更广泛的影响。

Jared SaiaUniversity of New MexicoCAREER: Foundations for Attack-Resistant Collaborative Peer-to-Peer Systems0644058Panel ID: 070111AbstractHow can a group of agents achieve a goal despite efforts by some of the agents to prevent this? This important question cuts across many disciplines including political science, economics, mathematics and computer science. In this proposal, we are exploring this question by focusing on the following problem. A set of n agents wants to compute the value of a function, f, of n inputs, where each agent holds a unique input of f. Our goal is to create a distributed algorithm that ensures that each agent learns the output of f. Our algorithm will be attack-resistant in that it works correctly even when up to a constant fraction of the agents are controlled by an omniscient adversary that tries to prevent the function from being computed. Our algorithm will also be scalable in the sense that each node in the network sends and receives a number of messages and bits that is only polylogarithmic in n i.e. O(logc n) where c is a fixed constant. We are making use of several tools to solve this problem including: the use of expander-like graphs to enable robust communication; the use of small randomly chosen committees as single trustworthy functional units; and algorithmic techniques to harden against denial of service attacks. Solving this problem will likely have broader impact in such diverse areas as voting, spam detection, worm and malware detection, distributed file systems, auction and mechanism enforcement, collaborative filtering, and web search.