Algorithms for large scale networks

大规模网络的算法

• 批准号: 121617-2011
• 负责人: King, Valerie
• 金额: $ 2.11万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=569214
• 关键词: Algorithms; large; scale; networks

Recent years have seen a rapid increase in the presence of large networks of diverse users. Such systems have the potential to speed up computation through vast parallelization and also to revolutionize how we as a society organize our data, economic activity and decision-making. With this promise comes an exposure to new threats in the form of increasingly sophisticated malware. As our dependence on large networks grows, so does our need to develop algorithms which are robust to powerful malicious adversaries. A starting point is a fundamental problem of coordination in distributed computing, the problem of bringing processors to agreement on a bit (Byzantine agreement) and a simple model of users, good users that follow the protocol and bad users controlled by a malicious adversary. This problem was commonly thought to have a communication bottleneck requiring all-to-all communication, making it impractical to consider for large size networks. Recently, we broke through some conjectured bottlenecks in this area. The theoretical limits of what can be done still remain open and we hope to develop both practical tools and theoretical understanding of what is possible. When we look at the network as a community of users with individual preferences, other interesting problems arise. Rather than ``good" nodes, we may have factions of nodes that co-operate if they are friends or it is to their benefit. On the frontier of law and economics, we consider how nodes in a game can coordinate to improve their overall benefit by voting to change the current rules of the game. We also ask how this and other coordination problems such as the decentralized scheduling of health care, may be done without losing privacy. While these problems have been studied by others, we will seek to implement them efficiently in large networks, without all-to-all communication.

近年来，不同用户的大型网络的存在迅速增加。这种系统有可能通过大规模并行化来加速计算，并彻底改变我们作为一个社会组织数据、经济活动和决策的方式。伴随着这一承诺而来的是以日益复杂的恶意软件形式出现的新威胁。随着我们对大型网络的依赖越来越大，我们需要开发对强大的恶意对手具有鲁棒性的算法。 一个出发点是一个基本的问题，在分布式计算的协调，使处理器的协议位（拜占庭协议）和一个简单的模型的用户，好的用户遵循协议和坏的用户控制的恶意对手的问题。这个问题通常被认为是一个通信瓶颈，需要所有对所有的通信，使其不切实际的考虑大型网络。最近，我们突破了这方面的一些瓶颈。可以做什么的理论限制仍然是开放的，我们希望开发实用工具和理论理解什么是可能的。 当我们把网络看作是一个有着个人偏好的用户社区时，其他有趣的问题就出现了。而不是“好”节点，我们可能有派系的节点，合作，如果他们是朋友或这是他们的利益。在法律和经济学的前沿，我们考虑如何在一个游戏中的节点可以协调，以提高他们的整体利益，通过投票改变当前的游戏规则。我们还询问如何在不失去隐私的情况下解决这一问题和其他协调问题，如分散安排医疗保健。虽然这些问题已经被其他人研究过，但我们将寻求在大型网络中有效地实现它们，而无需所有对所有的通信。