Narrow Results

Many peer-to-peer (P2P) applications require that nodes behave altruistically in order to perform tasks collectively. Here we examine a class of simple protocols that aim to self-organize P2P networks into clusters of altruistic nodes that help each other to complete jobs requiring diverse skills. We introduce a variant (called ResourceWorld) of an existing model (called SkillWorld) and compare results obtained in extensive (ten billion interactions) simulation experiments. It was found that for both model variants altruistic behavior was selected when certain cost/benefit constraints were met. Specifically, ResourceWorld selects for altruism only when the collective benefit of an action is at least as high as the individual cost. This gives a minimal method for realizing so-called "social rationality," where nodes select behaviors for the good of the collective even though actions are based on individual greedy utility maximization. Interestingly, the SkillWorld model evidences a kind of superaltruism in which nodes are prepared to cooperate even when the cost is higher than the benefit.

Massively distributed data mining in large networks such as smart device platforms and peer-to-peer systems is a rapidly developing research area. One important problem here is concept drift, where global data patterns (movement, preferences, activities, etc.) change according to the actual set of participating users, the weather, the time of day, or as a result of events such as accidents or even natural catastrophes. In an important case — when the network is very large but only a few training samples can be obtained at each node locally — no efficient distributed solution is known that could follow concept drift efficiently. This case is characteristic of smart device platforms where each device stores only one local observation or data record related to a learning problem. Here we present two algorithms to handle concept drift. None of the algorithms collects data to a central location, instead models of the data perform random walks in the network, while being improved using an online learning algorithm. The first algorithm achieves adaptivity by maintaining young as well as old models in the network according to a fixed age distribution. The second one measures the performance of models locally, and discards them if they are judged outdated. We demonstrate through a thorough experimental analysis that our algorithms outperform the known competing methods if the number of independent local samples is limited relative to the speed of drift: a typical scenario in our targeted application domains. The two algorithms have different strengths: while the age distribution approach is very simple and efficient, explicit drift detection can be useful in monitoring applications to trigger control action.