In a decentralized storage system, agents replicate each other’s data to increase availability. Compared to organizationally centralized solutions, such as cloud storage, a decentralized storage system requires less trust in the provider and may result in smaller monetary costs. Our system is based on reciprocal storage contracts that allow the agents to adopt to changes in their replication partners’ availability (by dropping inefficient contracts and forming new contracts with other partners). The data availability provided by the system is a function of the participating agents’ availability. However, a straightforward system in which agents’ matching is decentralized uses the given agent availability inefficiently. As agents are autonomous, the highly available agents form cliques replicating data between each other, which makes the system too hostile for the weakly available newcomers. In contrast, a centralized, equitable matching is not incentive compatible: it does not reward users for keeping their software running. We solve this dilemma by a mixed solution: an “adoption” mechanism in which highly available agents donate some replication space, which in turn is used to help the worst-off agents. We show that the adoption motivates agents to increase their availability (is incentive-compatible), but also that it is sufficient for acceptable data availability for weakly-available agents.

Publish/subscribe (pub/sub) is a popular communication paradigm in the design of large-scale distributed systems. A fundamental challenge in deploying pub/sub systems on a data center or a cloud infrastructure is efficient and cost-effective resource allocation that would allow delivery of notifications to all subscribers. In this paper, we provide answers to the following three fundamental questions: Given a pub/sub workload, (1) what is the minimum amount of resources needed to satisfy all the subscribers, (2) what is a cost-effective way to allocate resources for the given workload, and (3) what is the cost of hosting it on a public Infrastructure-as-a-Service (IaaS) provider like Amazon EC2. To answer these questions, we formulate a problem coined Minimum Cost Subscriber Satisfaction (MCSS). We prove MCSS to be NP-hard and provide an efficient heuristic solution based on a combination of optimizations. We evaluate the solution experimentally using real traces from Spotify and Twitter along with a pricing model from Amazon. We show the impact of each optimization using a naive solution as the baseline. Using a variety of practical scenarios for each dataset, we also show that our solution scales well for millions of subscribers and runs fast.

Publish/subscribe (pub/sub) is a popular communication paradigm in the design of large-scale distributed systems. A provider of a pub/sub service (whether centralized, peer-assisted, or based on a federated organization of cooperatively managed servers) commonly faces a fundamental challenge: given limited resources, how to maximize the satisfaction of subscribers? We provide, to the best of our knowledge, the first formal treatment of this problem by introducing two metrics that capture subscriber satisfaction in the presence of limited resources. This allows us to formulate matters as two new flavors of maximum coverage optimization problems. Unfortunately, both variants of the problem prove to be NP-hard. By subsequently providing formal approximation bounds and heuristics, we show, however, that efficient approximations can be attained. We validate our approach using real-world traces from Spotify and show that our solutions can be executed periodically in real-time in order to adapt to workload variations.

Spotify is a peer-assisted music streaming service that has gained worldwide popularity in the past few years. Until now, little has been published about user behavior in such services. In this paper, we study the user behavior in Spotify by analyzing a massive dataset collected between 2010 and 2011. Firstly, we investigate the system dynamics including session arrival patterns, playback arrival patterns, and daily variation of session length. Secondly, we analyze individual user behavior on both multiple and single devices. Our analysis reveals the favorite times of day for Spotify users. We also show the correlations between both the length and the downtime of successive user sessions on single devices. In particular, we conduct the first analysis of the device-switching behavior of a massive user base.

In this work, we present a Flow Stealing attack, where a victim's browser is redirected in the middle of a browsing session. We detail two attack scenarios. The first is redirecting the victim's browser as it moves from a store to a payment provider, and the second redirects the victim to a phishing page, when she navigates to one of a set of target sites. A key issue in flow stealing is correctly timing the redirect. The main way to accomplish this is to leverage a history detection attack to test whether the victim has visited a target. By repeatedly polling, an attacker learns when the victim navigates to a tested target page. With this application, we demonstrate that the impact of history detection is greater than previously known. Our primary history detection mechanism is a cache timing attack, measuring the time it takes to load an element to determine if it was served from the browser cache. This attack works with present browser versions. We also discuss CSS history detection, based on detecting the styling of visited links, which has been solved in most browsers. Lastly, we also consider a network-based attacker who can mount a man-in-the-middle attack on the victim's network traffic. We discuss several countermeasures against flow stealing. These include two new proposed policies on JavaScript window navigation which can be implemented by browser vendors. We also present mitigations which can be implemented by individual stores or payment providers.

One of the differences between typical peer-to-peer (P2P) and client-server systems is the existence of user accounts. While many P2P applications, like public file sharing, are anonymous, more complex services such as decentralized online social networks require user authentication. In these, the common approach to P2P authentication builds on the possession of cryptographic keys. A drawback with that approach is usability when users access the system from multiple devices, an increasingly common scenario. In this work, we present a scheme to support logins based on users knowing a username-password pair. We use passwords, as they are the most common authentication mechanism in services on the Internet today, ensuring strong user familiarity. In addition to password logins, we also present supporting protocols to provide functionality related to password logins, such as resetting a forgotten password via e-mail or security questions. Together, these allow P2P systems to emulate centralized password logins. The results of our performance evaluation indicate that incurred delays are well within acceptable bounds.

Automated assessment systems have been employed in computer science (CS) courses at a number of different universities. Such systems are especially applicable in teaching algorithmic problem solving since they can automatically test if an algorithm has been correctly implemented, i.e., that it performs its specified function on a set of inputs. Being able to implement algorithms that work correctly is a crucial skill for CS students in their professional role, but it can be difficult to convey the importance of this in a classroom situation. Programming and problem solving education supported by automated grading has been used since 2002 at our department. We study, using action research methodology, different strategies for deploying automated assessment systems in CS courses. Towards this end, we have developed an automated assessment system and both introduced it into existing courses and constructed new courses structured around it. Our primary data sources for evaluation consists of course evaluations, statistics on students' submitted solutions, and experience teaching the courses. Authors of this paper have been participating in teaching all of the courses mentioned here.

Spotify is a streaming service offering low-latency access to a large library of music. Streaming is performed by a combination of client-server access and a peer-to-peer protocol. The service currently has a user base of over 10 million and is available in seven European countries. We provide a background on the Spotify protocol with emphasis on the formation of the peer-to-peer overlay. Using measurement data collected over a week by instrumenting Spotify clients, we analyze general network properties such as the correspondence between individual user accounts and the number of IP addresses they connect from and the prevalence of Network Address Translation devices (NATs). We also discuss the performance of one of the two peer discovery mechanisms used by Spotify.

Spotify is a music streaming service offering low-latency access to a library of over 8 million music tracks. Streaming is performed by a combination of client-server access and a peer-to-peer protocol. In this paper, we give an overview of the protocol and peer-to-peer architecture used and provide measurements of service performance and user behavior. The service currently has a user base of over 7 million and has been available in six European countries since October 2008. Data collected indicates that the combination of the client-server and peer-to-peer paradigms can be applied to music streaming with good results. In particular, 8.8% of music data played comes from Spotify's servers while the median playback latency is only 265 ms (including cached tracks). We also discuss the user access patterns observed and how the peer-to-peer network affects the access patterns as they reach the server.