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

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

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.