This paper examines the impact of heavy churn on the robustness of decentralized social network-based Sybil defense (SNSD) schemes. Our analysis reveals that (i) heavy churn disintegrates the social overlay network that is fundamental to these schemes into multiple disconnected components, resulting in poor network connectivity, and (ii) a naive solution that adds links from each node to all its 2-hop neighbors improves network connectivity but comes at a significant cost of poor attack resilience of these schemes.

We propose a new design point in the trade-off between network connectivity and attack resilience of SNSD schemes, where each node adds links to only a selective few of all its 2-hop neighbors based on a minimum expansion contribution (MinEC) heuristic. Extensive evaluation through simulations shows that our approach fares as good as the naive 2-hop solution in terms of network connectivity, while making little compromise on the attack resilience. Moreover, our approach preserves the fast-mixing property that is fundamental to many SNSD schemes even at high levels of churn. This result suggests that existing and potential future SNSD schemes relying on this property can incorporate our approach into their designs with minimal changes.

The particle filter is a Bayesian estimation technique based on Monte Carlo simulation. The nonparametric nature of particle filters makes them ideal for non-linear, non-Gaussian dynamic systems. Particle filtering has many applications: in computer vision, robotics, and econometrics to name just a few. Although superior to Kalman filters, particle filters have higher computational requirements, which limits practical use in real-time applications. In this paper, we investigate how to design a particle filter framework for complex real-time estimation problems using modern many-core architectures. We develop a robotic arm application that serves as a highly flexible estimation problem to push estimation rates and accuracy to new levels. By varying different filter and model parameters, we derive rules of thumb for good filter configurations. We evaluate our particle filter with a comprehensive performance and correctness analysis. Our results significantly lower the development effort of particle filters for other real-time estimation problems. For the most demanding robotic arm configuration, we can process one million particles at an update rate of a few hundred state estimations per second. As such, we see our results as a step towards wider adoption of particle filters, and as a prerequisite to investigate larger filter setups for even more complex estimation problems.

Peer-to-peer (p2p ) file sharing systems rely on the sharing of resources by large fractions of partic- ipants. Sharing-ratio enforcement provides a very strong incentive for peers to contribute, leading to a higher performance for all peers in the system. One way of implementing this is by banning peers that do not share enough, determined by their past behavior (i.e., reputation). Various reputation mechanisms have been designed to facilitate this, but they are centralized or not feasible in practice. In this paper, we present a secure, fully distributed mechanism for reputation management and its integration with BitTorrent. The resulting system enforces a long-term balanced sharing-ratio for all peers in a BitTor- rent file sharing network. In our system, up- and download statistics are spread among peers and used to compute a subjective reputation for each peer. We apply the maxflow algorithm to limit the effect of peers that spread false information. We present simulations that demonstrate the system’s accuracy and effectiveness. The resulting system overcomes the long-standing problem of BitTorrent’s lack of seeding incentives, without any need for centralized administration, authority, or technology.

A description is given of an online division (reciprocal) algorithm for (maximally) redundant floating-point numbers of arbitrary radix. The algorithm works for normalized, quasi-normalized, and pseudonormalized numbers, and can therefore be applied in chained online computations. The online delay of the proposed algorithm is reported. The algorithm consists of two steps: the first m digits of the result are generated by a simple table lookup method: the remaining n-m digits are generated by using an adapted Newton-Raphson iteration method. In the second step, the online digits are created by using a fast and simple selection mechanism.