CT-ISG: Provably Scalable and Robust Peer-to-Peer System Baruch Awerbuch Johns Hopkins University
This 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.
