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

职业：抗攻击、协作对等系统的基础

• 批准号: 0644058
• 负责人: Jared Saia
• 金额: $ 40万
• 依托单位: University of New Mexico
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0644058&HistoricalAwards=false
• 关键词: CAREER; Foundations; Attack; Resistant; Collaborative

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.

Jared Saia新墨西哥大学CAREER：抗攻击协作对等系统的基础0644058面板ID：070111摘要一组代理如何实现一个目标，尽管一些代理的努力，以防止这一点？ 这个重要的问题跨越了许多学科，包括政治学、经济学、数学和计算机科学。 在本提案中，我们通过集中讨论以下问题来探讨这一问题。 一组n个智能体想要计算一个函数f的值，f有n个输入，其中每个智能体都有一个唯一的f输入。 我们的目标是创建一个分布式算法，确保每个代理学习f的输出。 我们的算法将是抗攻击的，因为它可以正确地工作，即使当一个无所不知的对手试图阻止函数被计算控制的代理的一个常数部分。 我们的算法也将是可扩展的，在这个意义上说，网络中的每个节点发送和接收的消息和位的数量，只有polylogarithmic在n，即O（logc n），其中c是一个固定的常数。我们正在使用几种工具来解决这个问题，包括：使用类似扩展器的图形来实现强大的通信;使用随机选择的小型委员会作为单个值得信赖的功能单元;以及增强拒绝服务攻击的算法技术。 解决这个问题可能会在投票、垃圾邮件检测、蠕虫和恶意软件检测、分布式文件系统、拍卖和机制执行、协同过滤和Web搜索等不同领域产生更广泛的影响。