CT-ISG Provably Scalable and Robust Peer-to-Peer Systems

提案：0716676CT-ISG：Baruch AwerbuchJohns霍普金斯大学这个提议解决了以下基本问题：在一个极端敌对的环境中，一个人如何能够从他人的错误和成功中学习？非正式地，想象一下不同的代理人做出不可逆转的决定，并为他们的错误“付出代价”。对于代理人来说，集体避免多次犯同样的错误，而不仅仅是个别地犯同样的错误，这是很有意义的。显然，利用信任或共同的品味可以使用户社区更有效率，因为它允许他们重复彼此的好决定，同时避免不必要的重复错误。在这种情况下，探索不同选项的工作可以在合作用户之间“分配”。问题是，是否有可能设计一种算法工具，从他人的经验中学习，同时尽量减少重复错误。这当然是可能的，如果所有的代理人，可以合作和信任对方，即认为相同的行动是错误的，知道对方。然而，在一般情况下，上述假设可能是有问题的，因为可靠的代理人在系统中必须能够划分的工作，探索不同的选择，和错误的成本与这种探索，在他们自己之间，而不知道谁的建议是可信的。如果对手占多数，这似乎是“使命不可能的”;然而，这正是我们在这项研究工作中将要完成的。请注意，在对抗性多数的情况下，任何在分布式计算中使用经典工具（如拜占庭协议）的尝试都是无望的。主要思想是，我们只努力优化整体性能，而不是完美地重建偏好或发现诚实用户的联盟。非正式地，这可以通过“后悔”的概念来说明：人们可以事后分析他们的决定，确定他们希望遵循的最佳动态先见之明策略，并估计与此策略的性能差距。

Proposal: 0716676CT-ISG: Provably Scalable and Robust Peer-to-Peer SystemBaruch AwerbuchJohns Hopkins UniversityThis proposal addresses the following fundamental question: how can one provably learn from the mistakes and successes of others in an extremely adversarial environment?Informally, imagine that different agents make irreversible decisions, and ``pay'' for their mistakes. It makes a lot of sense for the agents collectively to avoid making the same mistakes multiple times, rather than just individually. Clearly, leveraging trust or shared taste enables a community of users to be more productive, as it allows them to repeat each other's good decisions while avoiding unnecessary repetition of mistakes. In this case, the job of exploring different options can be ``distributed'' among cooperative users. The question is whether it is possible to design an algorithmic tool for learning from the experience of others while minimizing repeating their mistakes. This is certainly possible if all the agents that can cooperate and trust one another, namely consider the same actions to be mistakes, know about each other.However, in general, the above assumptions may be problematic, since reliable agents in the system must be able to divide the job of exploring different options, and the cost of mistakes associated with such exploration, among themselves, without knowing in advance whose advice can be trusted. This appears to be ``mission impossible'' if adversaries are in a majority; yet this is exactly what we will accomplish in this research effort. Notice that with adversarial majority, any attempt to use classic tools in distributed computing such as Byzantine agreement is hopeless. The main idea is that we only strive to optimize the overall performance, rather than perfectly reconstruct the preferences or discover the coalitions of honest users. Informally, this can be stated via the notion of ``regret'': one can analyze their decision in hindsight, determine the best dynamic prescient strategy that they wish they had followed, and estimate the performance gap versus this strategy.