The centralized collection of search interaction logs for training ranking models raises significant privacy concerns. Federated Online Learning to Rank (FOLTR) offers a privacy-preserving alternative by enabling collaborative model training without sharing raw user data. However, benchmarks in FOLTR are largely based on random partitioning of classical learning-to-rank datasets, simulated user clicks, and the assumption of synchronous client participation. This oversimplifies real-world dynamics and undermines the realism of experimental results. We present AOL4FOLTR, a large-scale web search dataset with 2.6 million queries from 10,000 users. Our dataset addresses key limitations of existing benchmarks by including user identifiers, real click data, and query timestamps, enabling realistic user partitioning, behavior modeling, and asynchronous federated learning scenarios.

Centralized search engines control what we see, read, believe, and vote. Consequently, they raise concerns over information control, censorship, and bias. Decentralized search engines offer a remedy to this problem, but their adoption has been hindered by their inferior quality and lack of a self-sustaining economic framework. We present SwarmSearch, a fully decentralized, AI-powered search engine with a self-funding architecture. Our system is designed for deployment within the decentralized file-sharing software Tribler. SwarmSearch integrates volunteer-based with profit-driven mechanisms to foster an implicit marketplace for resources. Employing the state-of-the-art of AI-based retrieval and relevance ranking, we also aim to close the quality gap between decentralized search and centralized alternatives. Our system demonstrates high retrieval accuracy while showing robustness in the presence of 50 % adversarial nodes.

Shared code in blockchains, known as smart contracts , stands to replace important parts of our digital governance and financial infrastructure. The permissionless execution of smart contracts is tightly coupled to cryptocurrencies and Proof-of-Work blockchains. As a result, smart contracts inherit the environmental impact of Proof-of-Work blockchains, such as its energy consumption, carbon footprint, and electronic waste. The four concepts of relaxed consistency, strong identities, probabilistic consensus, and the use of liabilities instead of assets may change the status quo. This work explores the integration of these concepts to decouple smart contracts from Proof-of-Work blockchains. By means of a local-first approach, which may expose users to inconsistent ephemeral contract states, the architecture of smart contracts can be transformed to become green. Because such contract states may be dropped, we base the interactions between users on liabilities. We propose a novel paradigm for smart contract architectures, named Green Smart Contracts, that is based on a local-first approach. Furthermore, we present and implement a prototype solution for this paradigm. We validate the need for a mechanism to resolve consistency violations by replaying the contract calls of a real smart contract. Our simulation shows that violations occur more often (13% of contract invocations) when using liabilities than when using a traditional blockchain (3% of contract invocations). However, we additionally validate that they can be avoided using a consensus mechanism, and our experiments show that a publish-subscribe messaging pattern uses the fewest messages to do so, though it may not be applicable for use cases that disallow the inherent imbalance in the messaging between peers. Our carbon emission estimation shows that a Green Smart Contract approach lowers carbon emissions by 52.31% when compared with the messaging behavior of a typical peer-to-peer blockchain with 1000 nodes.

With the proliferation of Internet of Things (IoT) ecosystems, traditional resource orchestration mechanisms, executed on fog devices, encounter significant scalability, reliability and security challenges. To tackle these challenges, recent decentralized algorithms in Fog-IoT use Distributed Ledger Technologies to orchestrate resources and payments between peers. However, while distributed ledgers provide many desirable properties, their consensus mechanism introduces a performance bottleneck. This paper introduces Light-HIDRA, a consensus-less and decentralized resource orchestration system for Fog-IoT environments. At its core, Light-HIDRA uses Byzantine Reliable Broadcast (BRB) to coordinate actions without centralized control, therefore drastically reducing communication overhead and latency compared to consensus-based solutions. Light-HIDRA coordinates the scheduling and execution of workloads, and securely manages the payments that peers receive for dedicating resources to workloads. Light-HIDRA further increases performance and reduces overhead by grouping peers into distinct domains. We conduct an in-depth analysis of the protocol’s security properties, investigating its efficiency and robustness in diverse situations. We evaluate the performance of Light-HIDRA, highlighting its performance over HIDRA, a state-of-the-art baseline that uses smart contracts. Our experiments demonstrate that Light-HIDRA reduces the bandwidth usage by up to 57x, the latency of workload offloading by up to 142x, and shows superior throughput compared to HIDRA.

The popularity of blockchain technology has bootstrapped many “Web3” applications, e.g., Ethereum and IPFS, that apply distributed ledger technology to store transactions. The amount of transactions generated and stored in such Web3 applications is significant and, in its raw form, usually not searchable by users. Existing Web3 transaction indexing and search engines are predominantly centralized and, therefore, can manipulate search results or censor particular queries. With the proliferation of Web3 transactions and applications, a decentralized and censorship-resistant search primitive is becoming essential. We present DeScan, a decentralized and censorship-resistant indexing and search engine for Web3. Users index their local Web3 transactions using custom rules that output triplets. Generated triplets are bundled in a distributed transaction graph that is searchable by other users. To coordinate search and distribute the storage of the transaction graph over peers in the network, we build upon a Skip Graph (SG) data structure. Since the Skip Graph does not provide any resilience against adversarial peers that censor searches, we propose four modifications to improve its robustness. We implement DeScan and conduct experiments with up to 12 800 peers and 10 million Ethereum transactions. Our experiments show that DeScan with our modifications enabled can tolerate 20% adversarial peers and 35% unresponsive peers without disruption. Moreover, we find that searches in DeScan are usually completed well within a second, even when the network grows. Finally, we show that storage and network costs are evenly distributed amongst peers as the network grows.

Traditionally, peer-to-peer systems have relied on altruism and reciprocity. Although incentive-based models have gained prominence in new-generation peer-to-peer systems, it is essential to recognize the continued importance of cooperative principles in achieving performance, fairness, and correctness. The lack of this acknowledgment has paved the way for selfish peers to gain unfair advantages in these systems. As such, we address the challenge of selfish peers by devising a mechanism to reward sustained cooperation. Instead of relying on global accountability mechanisms, we propose a protocol that naturally aggregates local evaluations of cooperation. Traditional mechanisms are often vulnerable to Sybil and misreporting attacks. However, our approach overcomes these issues by limiting the benefits selfish peers can gain without incurring any cost. The viability of our algorithm is proven with a deployment to 27,259 Internet users and a realistic simulation of a blockchain gossip protocol. We show that our protocol sustains cooperation even in the presence of a majority of selfish peers while incurring only negligible overhead.

Manipulation of user transactions by miners in permissionless blockchain systems is a growing concern. This problem is a pervasive and systemic issue that incurs high costs for users of decentralised applications and is known as Miner Extractable Value (MEV). Furthermore, transaction manipulations create other issues such as congestion, higher fees, and system instability. Detecting transaction manipulations is difficult, even though it is known that they originate from the pre-consensus phase of transaction selection for building blocks, at the base layer of blockchain protocols. In this paper, we summarize known transaction manipulation attacks. We present LO, an accountable base layer protocol designed to detect and mitigate transaction manipulations. LO is built around the accurate detection of transaction manipulations and assignment of blame at the granularity of a single mining node. LO forces miners to log all the transactions they receive into a secure mempool data structure and to process them in a verifiable manner. Overall, LO quickly and efficiently detects censorship, injection or re-ordering attempts. Our performance evaluation shows that LO is also practical and only introduces a marginal performance overhead.

Web3 is emerging as the new Internet-interaction model that facilitates direct collaboration between strangers without a need for prior trust between network participants and without central authorities. However, one of its shortcomings is the lack of a defense mechanism against the ability of a single user to generate a surplus of identities, known as the Sybil attack. Web3 has a Sybil attack problem because it uses peer sampling to establish connections between users. We evaluate the promising but under-explored direction of Sybil avoidance using network latency measurements, according to which two identities with equal latencies are suspected to be operated from the same node, and thus are likely Sybils. Network latency measurements have two desirable properties: they are only malleable by attackers by adding latency, and they do not require any trust between network participants. Our basic SybilSys mechanism avoids Sybil attackers using only network latency measurements if attackers do not actively exploit their malleability. We present an enhanced version of SybilSys that protects against targeted attacks using a variant of the flow correlation attack, which we name TrafficJamTrigger. We show how the message flows of Round-Trip Time measurements can be used to expose attack patterns and we propose and evaluate six classifiers to recognize these patterns. Our experiments show, through both emulation and real-world deployment, that enhanced SybilSys can serve a fundamental role for Web3, effectively establishing connections to real users even in the face of networks consisting of 99% Sybils.

Self-Sovereign Identity (SSI) aspires to create a standardised identity layer for the Internet by placing citizens at the centre of their data, thereby weakening the grip of big tech on current digital identities. However, as millions of both physical and digital identities are lost annually, it is also necessary for SSIs to possibly be revoked to prevent misuse. Previous attempts at designing a revocation mechanism typically violate the principles of SSI by relying on central trusted components. This lack of a distributed revocation mechanism hampers the development of SSI. In this paper, we address this limitation and present the first fully distributed SSI revocation mechanism that does not rely on specialised trusted nodes. Our novel gossip-based propagation algorithm disseminates revocations throughout the network and provides nodes with a proof of revocation that enables offline verification of revocations. We demonstrate through simulations that our protocol adequately scales to national levels.

Web3 networks are emerging to replace centrally-governed networking infrastructure. The integrity of the shared public infrastructure of Web3 networks is guaranteed through data sharing between nodes. However, due to the unstructured and highly partitioned nature of Web3 networks, data sharing between nodes in different partitions is a challenging task. In this paper we present the TSRP mechanism, which approaches the data sharing problem through nodes auditing each other to enforce carrying of data between partitions. Reputation is used as an analogue for the likelihood of nodes interacting with nodes from other partitions in the future. The number of copies of data shared with other nodes is inversely related to the nodes’ reputation. We use a real-world trace of Twitter to show how our implementation can converge to an equal number of copies as structured approaches.

Existing digital identity management systems fail to deliver the desirable properties of control by the users of their own identity data, credibility of disclosed identity data, and network-level anonymity. The recently proposed Self-Sovereign Identity (SSI) approach promises to give users these properties. However, we argue that without addressing privacy at the network level, SSI systems cannot deliver on this promise. In this paper we present the design and analysis of our solution TCID, created in collaboration with the Dutch government. TCID is a system consisting of a set of components that together satisfy seven functional requirements to guarantee the desirable system properties. We show that the latency incurred by network-level anonymization in TCID is significantly larger than that of identity data disclosure protocols but is still low enough for practical situations. We conclude that current research on SSI is too narrowly focused on these data disclosure protocols.

“Big Tech” companies provide digital services used by billions of people. Recent developments, however, have shown that these companies often abuse their unprecedented market dominance for selfish interests. Meanwhile, decentralized applications without central authority are gaining traction. Decentralized applications critically depend on its users working together. Ensuring that users do not consume too many resources without reciprocating is a crucial requirement for the sustainability of such applications. We present ConTrib, a universal mechanism to maintain fairness in decentralized applications by accounting the work performed by peers. In ConTrib, participants maintain a personal ledger with tamper-evident records. A record describes some work performed by a peer and links to other records. Fraud in ConTrib occurs when a peer illegitimately modifies one of the records in its personal ledger. This is detected through the continuous exchange of random records between peers and by verifying the consistency of incoming records against known ones. Our simple fraud detection algorithm is highly scalable, tolerates significant packet loss, and exhibits relatively low fraud detection times. We experimentally show that fraud is detected within seconds and with low bandwidth requirements. To demonstrate the applicability of our work, we deploy ConTrib in the Tribler file-sharing application and successfully address free-riding behaviour. This two-year trial has resulted in over 160 million records, created by more than 94’000 users.

Abstract Permissioned blockchains are increasingly being used as a solution to record transactions between companies. Several use cases that leverage permissioned blockchains focus on the representation and management of real-world assets. Since the number of incompatible blockchains is quickly growing, there is an increasing need for a universal mechanism to exchange, or trade, digital assets between these isolated platforms. There currently is no universal mechanism for inter-blockchain asset exchange without a requirement for trusted authorities that coordinate the trade. We address this shortcoming and present XChange, a universal mechanism for asset exchange between permissioned blockchains. To achieve universality and to avoid trusted authorities that coordinate a trade, XChange does not provide atomic guarantees but leverages risk mitigation strategies to reduce value at stake. Our mechanism records the specifications and progression of each trade within records on a distributed log. XChange reduces the economic gains of adversaries by bounding the total amount of fraud they can commit at any time. After having committed fraud, an adversary is forced to finish its ongoing trades before it can engage in new trades. We first present a four-phased protocol that coordinates an asset exchange between two traders. We then outline how trade records can be stored on TrustChain, which is a lightweight distributed ledger specifically built for the tamper-proof storage of data elements. We implement XChange and conduct experiments. Our experiments demonstrate that XChange is capable of reducing the economic gains of adversaries by more than 99.9% when replaying a real-world trading dataset. A deployment on low-resource devices reveals that the latency added to a trade by XChange is only 493 milliseconds. Finally, our scalability evaluation shows that XChange achieves over 1’000 trades per second and that its throughput, in terms of trades per second, scales linearly with the system load.

Matchmaking is a core enabling element in peer-to-peer markets. To date, matchmaking is predominantly performed by proprietary algorithms, fully controlled by market operators. This raises fairness concerns as market operators effectively can hide, prioritize, or delay the orders of specific users. Blockchain technology has been proposed as an alternative for fair matchmaking without a trusted operator but is still vulnerable to specific fairness attacks.

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.

Accounting mechanisms based on credit are used in peer-to-peer systems to track the contribution of peers to the community for the purpose of deterring freeriding and rewarding good behavior. Most often, peers earn credit for uploading files, but other activities might be rewarded in the future as well, such as making useful comments or reporting spam. Credit earned can be used for accessing new content, or for receiving preferential treatment in case of network congestion. We define credit mining as the activity performed by peers for the purpose of earning credit. In this paper, we design, implement, and evaluate a system for decentralized credit mining that maximizes the contribution of idle peers to the community by automatically uploading popular files. Building on previous theoretical insights into the economics of communities, we select autonomous algorithms for bandwidth investment as the basis of our credit mining system. Additionally, we describe our experience with important challenges arising from Internet deployment, that are frequently neglected in emulation, including duplicate content avoidance, spam prevention, and the cost of keeping peer information updated. Furthermore, we implement an archival mode of operation, which prevents the disappearance of old content from the community. We show the feasibility and usefulness of our credit mining system through measurements from our implementation on top of Tribler, an Internet-deployed peer-to-peer system.

Flame graphs are gaining rapidly in popularity in industry to visualize performance profiles collected by stack-trace based profilers. In some cases, for example, during performance regression detection, profiles of different software versions have to be compared. Doing this manually using two or more flame graphs or textual profiles is tedious and error-prone. In this `Early Research Achievements'-track paper, we present our preliminary results on using differential flame graphs instead. Differential flame graphs visualize the differences between two performance profiles. In addition, we discuss which research fields we expect to benefit from using differential flame graphs. We have implemented our approach in an open source prototype called FLAMEGRAPHDIFF, which is available on GitHub. FLAMEGRAPHDIFF makes it easy to generate interactive differential flame graphs from two existing performance profiles. These graphs facilitate easy tracing of elements in the different graphs to ease the understanding of the (d)evolution of the performance of an application.

Summary User interactions are indispensable for any online network to thrive, especially for BitTorrent‐like and Web real‐time communication‐based distributed online networks that rely on users' collective contributions instead of the help of central servers. User interactions provide fine‐grained information for many applications, such as security enhancement and cooperation promotion. To date, several schemes forestimating user interaction strengthin centralized online networks have been proposed. In contrast, we present design, deployment, and analysis of UISE for user interaction strength estimation in distributed online networks. Among the strong points of UISE is that it captures both direct and indirect user interactions, and that it scales with only partial information dissemination. We apply UISE to devise the first distributed scheme for online time estimation and we implement it into Tribler, a distributed online network for media and social applications like file sharing, streaming, and voting. We demonstrate the accuracy and the scalability of UISE with different information dissemination protocols and user behaviors using simulations, emulations, and a real‐world deployment. Copyright © 2015 John Wiley & Sons, Ltd.

Crawling a DHT allows researchers to monitor the behaviour of peers, determine their geographic location, etc. However, it has always been an error-prone process as it is not feasible to capture a full snapshot of the Mainline DHT in a timely manner. Therefore, researchers have developed approximation methods which can run on subsets of the DHT and extrapolate those in order to reason on the size and structure of the complete DHT. However, in this paper we introduce a new method of collecting information on peers connected to a DHT. We exploit the caches present at bootstrap servers to collect information on peers which are currently connected. Originally added to the bootstrap servers in order to be able to withstand more than 20,000 requests for peers each second, we now use the same mechanism as peers bootstrapping into the DHT to discover more than 20 Million peers in less than 2 hours. Using the bootstrap servers, we discover more than twice as many peers as BitMon, which crawls a subset of the DHT and then extrapolates. Moreover, in contrast to related work which often require highly customized/tuned BitTorrent clients, our script consists of 90 lines of Python code and runs on a simple laptop.

In recent years fully decentralized file sharing systems were developed aimed at improving anonymity among their users. These systems provide typical file sharing features such as searching for and downloading files. However, elaborate schemes originally aimed at improving anonymity cause partial keyword matching to be virtually impossible, or introduce a substantial bandwidth overhead. In this paper we introduce 4P, a system that provides users with anonymous search on top of a semantic overlay. The semantic overlay allows users to efficiently locate files using partial keyword matching, without having to resort to an expensive flooding operation. Included into 4P are a number of privacy enhancing features such as probabilistic query forwarding, path uncertainty, caching, and encrypted links. Moreover, we integrate a content retrieval channel into our protocol allowing users to start downloading a file from multiple sources immediately without requiring all intermediate nodes to cache a complete copy. Using a trace-based dataset, we mimic a real-world query workload and show the cost and performance of search using six overlay configurations, comparing random, semantic, Gnutella, RetroShare, and OneSwarm to 4P. The state-of-the-art flooding based alternatives required approximately 10,000 messages to be sent per query, in contrast 4P only required 313. Showing that while flooding can achieve a high recall (more than 85% in our experiments) it is prohibitively expensive. With 4P we achieve a recall of 76% at a considerable reduction in messages sent.

Regression testing can be done by re-executing a test suite on different software versions and comparing the outcome. For functional testing, the outcome of such tests is either pass (correct behaviour) or fail (incorrect behaviour). For non-functional testing, such as performance testing, this is more challenging as correct and incorrect are not clearly defined concepts for these types of testing. In this paper, we present an approach for detecting and analyzing I/O performance regressions. Our method is supplemental to existing profilers and its goal is to analyze the effect of source code changes on the performance of a system. In this paper, we focus on analyzing the amount of I/O writes being done. The open source implementation of our approach, SPECTRAPERF, is available for download. We evaluate our approach in a field user study on Tribler, an open source peer-to-peer client and its decentralized solution for synchronizing messages, Dispersy. In this evaluation, we show that our approach can guide the performance optimization process, as it helps developers to find performance bottlenecks on the one hand, and on the other allows them to validate the effect of performance optimizations. In addition, we perform a feasibility study on Django, the most popular Python project on Github, to demonstrate our applicability on other projects. Copyright c 2013 John Wiley & Sons, Ltd.

BitTorrent (BT) plays an important role in Internet content distribution. Because public BTs suffer from the free-rider problem, Darknets are becoming increasingly popular, which use Sharing Ratio Enforcement to increase their efficiency. We crawled and traced 17 Darknets from September 2009 to February 2011, and obtained datasets about over 5 million torrents. We conducted a broad range of measurements, including traffic, sites, torrents, and users activities. We found that some of the features of Darknets are noticeably different from public BTs. The results of our study reflect both macroscopic and microscopic aspects of the overall ecosystem of BitTorrent Darknets.

Graphical user interfaces are difficult to test: automated tests are hard to create and maintain, while manual tests are time-consuming, expensive and hard to integrate in a continuous testing process. In this paper, we show that it is possible to crowdsource GUI tests, that is, to outsource them to individuals drawn from a large pool of workers on the Internet, by instantiating virtual machines (VMs) running the system under test and letting testers access the VMs through their web browsers. This enables semi-automated continuous testing of GUIs and usability experiments with large numbers of participants at low cost. Several large experiments on the Amazon Mechanical Turk demonstrate that our approach is technically feasible and sufficiently reliable.

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.

Reputation systems are essential to establish trust and to provide incentives for cooperation among users in decentralized networks. In these systems, the most widely used algorithms for computing reputations are based on random walks. However, in decentralized networks where nodes have only a partial view of the system, random walk-based algorithms can be easily exploited by uncooperative and malicious nodes. Traditionally, a random walk only uses information about the adjacency of nodes, and ignores their structural and temporal properties. Nevertheless, the properties of nodes indicate their reliability, and so, random walks using much richer information about the nodes than simple adjacency may achieve higher robustness against malicious exploitations. In this paper, we introduce the properties of nodes that are indicative of their reliability, and we propose a scheme to integrate these properties into the traditional random walks. Particularly, we consider two common malicious exploitations of random walks in decentralized networks, uncooperative nodes and Sybil attacks, and we show that integrating node properties into random walks results in much more robust reputation systems. Our experimental evaluation in synthetic graphs and graphs derived from real-world networks covering a significant number of users, shows the effectiveness of the resulting biased random walks.

P2P communities that use credits to incentivize their members to contribute have emerged over the last few years. In particular, private BitTorrent communities keep track of the total upload and download of each member and impose a minimum threshold for their upload/download ratio, which is known as their sharing ratio. It has been shown that these private communities have significantly better download performance than public communities. However, this performance is based on oversupply, and it has also been shown that it is hard for users to maintain a good sharing ratio to avoid being expelled from the community. In this paper, we address this problem by introducing a speculative download mechanism to automatically manage user contribution in BitTorrent private communities. This mechanism, when integrated in a BitTorrent client, identifies the swarms that have the biggest upload potential, and automatically downloads and seeds them. In other words, it tries to invests the bandwidth of the user in a profitable way. In order to accurately asses the upload potential of swarms we analyze a private BitTorrent community and derive through multiple regression a predictor for the upload potential based on simple parameters accessible to each peer. The speculative download mechanism uses the predictor to build a cache of profitable swarms to which the peer can contribute. Our results show that 75 % of investment decisions result in an increase in upload bandwidth utilization, with a median 207 % return on investment.

Many peer-to-peer communities, including private BitTorrent communities that serve hundreds of thousands of users, utilize credit-based or sharing ratio enforcement schemes to incentivize their members to contribute. In this paper, we analyze the performance of such communities from both the system-level and the user-level perspectives. We show that both credit-based and sharing ratio enforcement policies can lead to system-wide "crunches" or "crashes," where the system seizes completely due to too little or too much credit, respectively. We present a theoretical model that identifies the conditions that lead to these system pathologies and we design an adaptive credit system that automatically adjusts credit policies to maintain sustainability. Given private communities that are sustainable, it has been demonstrated that they are greatly oversupplied in terms of excessively high seeder-to-leecher ratios. We further analyze the user-level performance by studying the effects of oversupply. We show that although achieving an increase in the average downloading speed, the phenomenon of oversupply has three undesired effects: long seeding times, low upload capacity utilizations, and an unfair playing field for late entrants into swarms. To alleviate these problems, we propose four different strategies, which have been inspired by ideas in social sciences and economics. We evaluate these strategies through simulations and demonstrate their positive effects.

EigenTrust (ET) is a renowned algorithm for reputation management in adversarial P2P systems. It incorporates the opinions of all peers in the network to compute a global trust score for each peer based on its past behavior, and relies on a set of pre-trusted nodes to guarantee that malicious nodes cannot subvert the system. In this paper, we show that ET is vulnerable to community structure and a novel targeted attack based on eigenvector centrality, since ET ranks nodes close to the pre-trusted ones higher than those further away. To address these shortcomings, we propose Personalized EigenTrust (PET) which (i) enables each user to choose her trusted peers from the social network of peers, thereby eliminating the need of pre-trusted nodes and making the system autonomous, (ii) is effective in networks operating under various transaction models based on distributions such as random, community-like and power-law, and (iii) is robust to many types of attacks including the targeted one based on eigenvector centrality. Our simulation results reveal that PET outperforms ET under diverse transaction models and attack strategies.

Due to the possibility of cheap identity creation, decentralized online reputation mechanisms are susceptible to sybil attacks. Barter Cast is a reputation mechanism used in the Internet-deployed Tribler file-sharing client. In this paper we study the opportunities for sybil attacks in Barter Cast and we devise a method for making Barter Cast sybil resilient, which is incorporated in a protocol called Sybil Res. Like in Barter Cast, in Sybil Res each peer maintains a local subjective weighted directed graph reflecting data transfer actions in Tribler, from which it computes the reputations of other peers using a flow based algorithm taking the edge weights as flows. In Sybil Res, after an upload action, the uploading peer discounts the weights of the edges on the paths from the down loader to itself. As a consequence, due to the way reputations are computed, the reputation of a peer performing a sybil attack decreases fast. To mitigate the negative impact of edge weight discounting on the reputations of honest peers, after a download action, the downloading peer increases the weights of the edges on the paths from the up loader to itself. We demonstrate that Sybil Res is effective in practice by means of trace-driven simulations using data collected from the Tribler network. The results show that Sybil Res effectively marginalizes attackers while having a minimal effect on the reputations of honest peers.

Video distribution is nowadays the dominant source of Internet traffic, and recent studies show that it is expected to reach 90% of the global consumer traffic by the end of 2015. Peer-to-peer assisted solutions have been adopted by many content providers with the aim of improving the scalability and reliability of their distribution network. While many solutions have been proposed, virtually all of them are at the overlay level, and so rely on the standard functionality of the transport layer. The Peer-to-Peer Streaming Protocol workgroup of the IETF has adopted the Libswift transport-layer protocol that is targeted at P2P traffic. In this paper we describe the design features and a first implementation of the Libswift protocol, and a piece-picking protocol that uses the transport features of Libswift in an essential way. We investigate its performance on both high-end and power-constrained low-end devices, comparing it to the state-of-the-art in P2P protocols.

Enhancing reciprocity has been one of the primary motivations for the design of incentive policies in BitTorrent-like P2P systems. Reciprocity implies that peers need to contribute their bandwidth to other peers if they want to receive bandwidth in return. However, the over-provisioning that characterizes today's BitTorrent communities and the development of many next-generation P2P systems with real-time constraints (e.g., for live and on-demand streaming) suggest that more effort can be devoted to reducing the inequity (i.e., the difference of service received) among peers, rather than only enhancing reciprocity. Inspired by this observation, in this work we analyze in detail several incentive mechanisms that are used in BitTorrent systems, and explore several strategies that influence the balance between reciprocity and equity. Our study shows that (i) reducing inequity leads to a better overall system performance, and (ii) the behavior of seeders (i.e., peers that hold a complete copy of the file and upload it for free) influences whether reciprocity is enhanced or inequity reduced.

Providing incentives for user contribution has been one of the primary design goals of Peer-to-Peer systems. The newly-emerged BitTorrent private communities adopt Sharing Ratio Enforcement (SRE) on top of BitTorrent's incentive mechanism, Tit-For-Tat, in order to strictly enforce a minimum contribution a member has to provide, in relation to the amount of service it has received. In this paper, we provide a theoretical model to analyze 1) how SRE provides seeding incentives, and 2) how SRE influences the download performance in the system. Specifically, we study the influence of the SRE threshold (i.e., the minimum sharing ratio requirement) and the bandwidth heterogeneity of the peers in the system. In our analysis, we assume users to be rational, i.e., peers seed only the minimum amount required by SRE, and we show that the download performance as predicted by our model represents a lower bound for the actual performance that can be reached in a BitTorrent private community. Hence, following our model, community administrators can predict the minimum performance level their systems will be able to reach.

During the last decade of P2P research a lot of attention has been given to incentive mechanisms. While centralized incentive mechanisms are straightforward in their design, a long term challenge has been to create a decentralized incentive mechanism that can be used to effectively induce cooperation and reduce freeriding. While there have been many proposals of such mechanisms based on the spreading of reputation information, little attention has been given to the theoretical limitations of such designs. In this paper, we present a high level model of reputation-based incentive mechanisms. We derive upper bounds on the effectiveness of such mechanisms, especially with respect to the performance under behavioral change and population turnover. Moreover, we assess the effectiveness of a reputation overlay in BitTorrent, and show that while its tit-for-tat reciprocity algorithm provides incentives for uploading on the short term, it reduces the benefits of an integrated long term incentive mechanism. All in all, we offer important insights for the design of future incentive systems.

The volume of Internet video is growing, and is expected to exceed 57 percent of global consumer Internet traffic by 2014. Peer-to-Peer technology can help delivering this massive volume of traffic in a cost-efficient, scalable, and reliable manner. However, single bit rate streaming is not sufficient given today's device and network connection diversity. A possible solution to this problem is provided by layered coding techniques, such as Scalable Video Coding, which allow addressing this diversity by providing content in various qualities within a single bit stream. In this paper we propose a new self-adapting piece-picking algorithm for downloading layered video streams, called Deftpack. Our algorithm significantly reduces the number of stalls, minimises the frequency of quality changes during playback, and maximizes the effective usage of the available bandwidth. Deftpack is the first algorithm that is specifically crafted to take all these three quality dimensions into account simultaneously, thus increasing the overall quality of experience. Additionally, Deftpack can be integrated into Bit torrent-based P2P systems and so has the chance of large-scale deployment. Our results from realistic swarm simulations show that Deftpack significantly outperforms previously proposed algorithms for retrieving layered content when all three quality dimensions are taken into account.

Tribler is an open-source software project facilitating search, streaming and sharing content using P2P technology. Over 800,000 people have used Tribler since the project started in 2005. The Tribler P2P core supports BitTorrent-compatible downloading, video on demand and live streaming. Aside from a regular desktop GUI that runs on multiple OSes, it can be installed as a browser plug-in, currently used by Wikipedia. Aditionally, it runs on a 450~MHz processor, showcasing future TV support. We continuously work on extensions and test out novel research ideas within our user base, resulting in sub-second content search, a reputation system for rewarding upload, and channels for content publishing and spam prevention. Presently, 1200 channels have been created, enabling rich multimedia communities without requiring any server.

A considerable body of research shows that Bit-Torrent provides very efficient resource allocation inside single swarms. Many BitTorrent clients also allow users to participate in multiple swarms simultaneously, and implement inter-swarm resource-allocation mechanisms that are used by millions of people. However, resource allocation across multiple swarms in BitTorrent has received much less attention. In this paper, we investigate whether currently prevalent inter-swarm resource allocation mechanisms perform acceptably or call for improvements. We use data from two BitTorrent communities and present results from trace-based simulations. Two use-cases for allocation mechanisms drive our evaluation: (1) file-sharing communities, whose objective is maximizing throughput, and (2) video-streaming communities, whose objective is maximizing the number of users receiving sufficient resources for uninterrupted streaming. To put the results from the analyzed mechanisms into perspective, we devise theoretical efficiency bounds for inter-swarm resource allocation, for which we map the resource allocation problem to a graph-theoretical flow network problem. In this formalism, the goal of the file-sharing use-case, throughput maximization, is equivalent to maximizing the flow in the network. The goal of the video-streaming use-case translates into finding a max-min fair allocation for BitTorrent downloading sessions, a problem for which we devise a new algorithm.

Many private BitTorrent communities employ Sharing Ratio Enforcement (SRE) schemes to incentivize users to contribute their upload resources. It has been demonstrated that communities that use SRE are greatly oversupplied, i.e., they have much higher seeder-to-leecher ratios than communities in which SRE is not employed. The first order effect of oversupply under SRE is a positive increase in the average downloading speed. However, users are forced to seed for extremely long times to maintain adequate sharing ratios to be able to start new downloads. In this paper, we propose a fluid model to study the effects of oversupply under SRE, which predicts the average downloading speed, the average seeding time, and the average upload capacity utilization for users in communities that employ SRE. We notice that the phenomenon of oversupply has two undesired negative effects: a) Peers are forced to seed for long times, even though their seeding efforts are often not very productive (in terms of low upload capacity utilization); and b) SRE discriminates against peers with low bandwidth capacities and forces them to seed for longer durations than peers with high capacities. To alleviate these problems, we propose four different strategies for SRE, which have been inspired by ideas in social sciences and economics. We evaluate these strategies through simulations. Our results indicate that these new strategies release users from needlessly long seeding durations, while also being fair towards peers with low capacities and maintaining high system-wide downloading speeds.

Tribler is an open-source software project facilitating searching, streaming and sharing content using P2P technology that has been used by over 800 000 people. The Tribler P2P core supports BitTorrent-compatible downloading, video on demand and live streaming. We continuously work on extensions and test out novel research ideas within our user base, resulting in sub-second content search, a reputation system for rewarding upload, and channels for content publishing and spam prevention.

Flashcrowds - sudden surges of user arrivals - do occur in BitTorrent, and they can lead to severe service deprivation. However, very little is known about their occurrence patterns and their characteristics in real-world deployments, and many basic questions about BitTorrent flashcrowds, such as How often do they occur? and How long do they last?, remain unanswered. In this paper, we address these questions by studying three datasets that cover millions of swarms from two of the largest BitTorrent trackers. We first propose a model for BitTorrent flashcrowds and a procedure for identifying, analyzing, and modeling BitTorrent flashcrowds. Then we evaluate quantitatively the impact of flashcrowds on BitTorrent users, and we develop an algorithm that identifies BitTorrent flashcrowds. Finally, we study statistically the properties of BitTorrent flashcrowds identified from our datasets, such as their arrival time, duration, and magnitude, and we investigate the relationship between flashcrowds and swarm growth, and the arrival rate of flashcrowds in BitTorrent trackers. In particular, we find that BitTorrent flashcrowds only occur in very small fractions (0.3-2%) of the swarms but that they can affect over ten million users.

In a typical BitTorrent swarm, a large proportion of the peers are behind firewalls or NATs. These peers are called unconnectable. When developing P2P applications, a main requirement is to handle unconnectable peers appropriately. One important aspect of this problem, which has not been emphasized so far, is understanding the difference between the attributes of unconnectable peers and peers in the open Internet. For example, if unconnectable peers spend much less time online, or if they download significantly more, exploiting these facts helps to optimize the implementation, and ignoring these facts can even lead to severe performance problems. Comparing open and unconnectable peers is not easy because most traces contain no information about connect ability. Here we study two large traces collected in two private BitTorrent communities: FileList.org and BitSoup.org, both of which contain the connect ability attribute. From these traces we extract several attributes of individual online sessions, swarms, and users. We compare the distributions of these attributes over unconnectable and open peers. We find that there are some potentially important differences, e.g., unconnectable users tend to have a lot more sessions, and they tend to spend slightly more time online. Some of our findings are in contradiction with previous results that were based on a different trace collection methodology.

Distributed systems without a central authority, such as peer-to-peer (P2P) systems, employ incentives to encourage nodes to follow the prescribed protocol. Game theoretic analysis is often used to evaluate incentives in such systems. However, most game-theoretic analyses of distributed systems do not adequately model the repeated interactions of nodes inherent in such systems. We present a game-theoretic analysis of a popular P2P protocol, Bit-Torrent, that models the repeated interactions in such protocols. We also note that an analytical approach for modeling incentives is often infeasible given the complicated nature of most deployed protocols. In order to comprehensively model incentives in complex protocols, we propose a simulation-based method, which we call Design Space Analysis (DSA). DSA provides a tractable analysis of competing protocol variants within a detailed design space. We apply DSA to P2P file swarming systems. With extensive simulations we analyze a wide-range of protocol variants and gain insights into their robustness and performance. To validate these results and to demonstrate the efficacy of DSA, we modify an instrumented BitTorrent client and evaluate protocols discovered using DSA. We show that they yield higher system performance and robustness relative to the reference implementation.

Today, the BitTorrent Peer-to-Peer file-sharing network is one of the largest Internet applications---it generates massive traffic volumes, it is deployed in thousands of independent communities, and it serves millions of unique users worldwide. Despite a large number of empirical and theoretical studies, observing the state of the global BitTorrent network remains a grand challenge for the BitTorrent community. To address this challenge, in this work we introduce BT-World, an architecture for observing the global BitTorrent network without help from the ISPs. We design BTWorld around three main features specific to BitTorrent measurements. First, our architecture is able to find public trackers, that is, the BitTorrent components that offer unrestricted service to peers around the world. Second, by observing the state of these trackers, BTWorld obtains information about the performance, scalability, and reliability of BitTorrent. Third, BTWorld is designed to pre-process the large volumes of recorded data for later analysis. We demonstrate the viability of our architecture by deploying it in practice, to observe and analyze one week of operation of a large part of the global BitTorrent network--over 10 million swarms and tens of millions of concurrent users. We also show that BT-World can shed light on BitTorrent phenomena, such as the presence of spam trackers and giant swarms.

Most P2P systems that have some kind of incentive mechanism reward peers according to their contribution, i.e. total bandwidth offered to the system. Due to the disparity in bandwidth capacity between P2P users on the Internet, the common effect of such mechanisms is that the fastest peers reap the highest benefits. We take a different approach and study how to incentivize cooperation in P2P systems based on effort, i.e. contribution relative to capacity. We make the following contributions: 1) we argue that contribution-based incentive schemes in P2P systems unnecessarily disfavor slow peers and decrease overall system performance; 2) we advocate the use of principles from an alternative economic vision, Participatory Economics (Parecon), to inspire systems to be fair and to ensure maximization of the social welfare while being efficient at the same time, and 3) we present the results of simulations in which we apply principles from Parecon to two popular real life systems: a) the popular file sharing BitTorrent protocol; b) a generic credit based sharing ratio enforcement scheme. Our approach yields a higher system performance and fairness and offers new insights into P2P incentive design.

The efficiency of Bit Torrent in disseminating content has inspired a number of P2P protocols for on-demand video streaming (VoD). Prior work on adapting Bit Torrent to VoD mainly focused on the piece selection policy, since streaming requires a somewhat "in order" download progress. Conversely, not much effort has been spent into adapting Bit Torrent's peer selection policy, where nodes mainly serve those that have recently uploaded to them at the highest rates. This mechanism incentivizes cooperation among peers but, in a heterogeneous system (i.e. where peers have different bandwidth capacities), it causes faster peers to receive higher download speeds than slower peers. This might hurt the system's ability of providing as many nodes as possible with the minimum download speed necessary to sustain the video playback rate. Furthermore, peers gain little utility in downloading at rates much higher than the video playback rate. Inspired by these observations, in this work, we extend the peer selection mechanism of an existing Bit Torrent-like VoD protocol, give-to-get (G2G), with techniques that allow peers to relax their reciprocity-based peer selection and choose more random nodes when their current QoS is high. In this way, more peers can be granted a good QoS and free-riding is tolerated only when bandwidth resources are abundant. To demonstrate the benefits of our approach, we present extensive simulations of the introduced techniques.

Wikipedia started a project in order to enable users to add video and audio on their Wiki pages. The technical downside of this is that its bandwidth requirements will increase manifold. BitTorrent-based peer-to-peer technology from P2P-Next (a European research project) is explored to handle this bandwidth surge. We discuss the impact on the BitTorrent piece picker and outline our ''tribe'' protocol for seamless integration of P2P into the HTML5 video and audio elements. Ongoing work on libswift which uses UDP, an enhanced transport protocol and integrated NAT/Firewall puncturing, is also described.

The efficiency of BitTorrent for file sharing has inspired a number of BitTorrent-based P2P protocols for Video-on-Demand (VoD). It has been shown that these systems are scalable in steady-state: the service quality provided to the users does not depend on the number of users in the system. However, it is not well understood how these systems scale under flash-crowds. In this work, we model a general BitTorrent-like VoD system and we find that under a flash-crowd the quality-of-service (QoS) degrades with the number of users. Also, our analysis shows that, at the very beginning of a flash-crowd, the maximum number of simultaneous users that can obtain a given service level is intrinsically related to two fundamental system parameters, namely the initial service capacity and the efficiency of piece exchange of the underlying P2P protocol. Finally, we illustrate the impact of peers turning into seeders (i.e peers that have finished downloading and remain in the system to upload) on the system scale.

P2P systems can benefit from reputation mechanisms to promote cooperation and help peers to identify good service providers. However, in spite of a large number of proposed reputation mechanisms, few have been investigated in real situations. BarterCast is a distributed reputation mechanism used by our Internet-deployed Bittorent-based file-sharing client Tribler. In BarterCast, each peer uses messages received from other peers to build a weighted, directed subjective graph that represents the upload and download activity in the system. A peer calculates the reputations of other peers by applying the maxflow algorithm to its subjective graph. For efficiency reasons, only paths of at most two hops are considered in this calculation. In this paper, we identify and assess three potential modifications to BarterCast for improving its accuracy and coverage (fraction of peers for which a reputation value can be computed). First, a peer executes maxflow from the perspective of the node with the highest betweenness centrality in its subjective graph instead of itself. Second, we assume a gossiping protocol that gives each peer complete information about upload and download activities in the system, and third, we lift the path length restriction in the maxflow algorithm. To assess these modifications, we crawl the Tribler network and collect the upload and download actions of the peers for three months. We apply BarterCast with and without the modifications on the collected data and measure accuracy and coverage.

Free-riding is an important problem in Peer-to-Peer (P2P) file-sharing networks. When peers refuse to contribute upload bandwidth, the whole network can collapse. A relatively new free-riding vulnerability in BitTorrent is the Large View Exploit, in which a peer connects to as many other peers as possible to increase the chance to get free data. This exploit can not be thwarted by tit-for-tat-like mechanisms which have traditionally been used to ban free-riding. Several approaches have been proposed to combat the Large View Exploit in fully decentralized systems, most of which rely on encryption. However, the use of regular encryption makes it impossible to verify the correctness of received data. In this paper we propose a novel encryption method which does allow verification of the plaintext data without decryption, at the expense of encryption strength. We show that a colluding peer still has to send data that is at least 40% of the size of the original data to allow decryption.

A well-known problem in P2P systems is freeriding, where users do not share content if there is no incentive to do so. In this paper, we distinguish lazy freeriders that are merely reluctant to share but follow the protocol, versus die-hard freeriders that employ sophisticated methods to subvert the protocol. Existing incentive designs often provide theoretically attractive resistance against die-hard freeriding, yet are rarely deployed in real networks because of practical infeasibility. Meanwhile, real communities benefit greatly from prevention of lazy freeriding, but have only centralized technology available to do so. We present a lightweight, fully distributed mechanism called BARTERCAST that prevents lazy freeriding and is deployed in practice. BarterCast uses a maxflow reputation algorithm based on a peer's private history of its data exchanges as well as indirect information received from other peers. We assess different reputation policies under realistic, trace-based community conditions and show that our mechanism is consistent and effective, even when significant fractions of peers spread false information. Furthermore, we present results of the deployment of BarterCast in the BitTorrent-based Tribler network which currently has thousands of users worldwide.

The explosion of freely available media content through BitTorrent file sharing networks over the Internet means that users need guides or recommendations to find the right, high quality, content. Current systems rely on centralized servers to aggregate, rate and moderate metadata for this purpose. We present the design and simulations, using real BitTorrent traces, for a method combining fully decentralized metadata dissemination, vote sampling and ranking for deployment in the Tribler.org BitTorrent media client. Our design provides robustness to spam attacks, where metadata does not reflect the content it is attached to, by controlling metadata spreading and by vote sampling based on a collusion proof experience function. Our design is light-weight, fully decentralized and offers good performance and robustness under realistic conditions.

The BitTorrent protocol is by far the most popular protocol for offline peer-to-peer video distribution on the Internet. BitTorrent has previously been extended to support the streaming of recorded video, that is, Video-on-Demand (VoD). In this paper, we take this support for video streaming a step further by presenting extensions to BitTorrent for supporting live video streaming, which we have implemented in our BitTorrent client called Tribler. We have tested our extensions both by running simulations, and by deploying our implementation in a public trial in the Internet, using the optimal values of several parameters as found in the simulations. We analyse the performance of Tribler in systems with varying values for the percentage of peers behind a firewall or NAT, which we consider to be one of the key parameters in the performance of deployed P2P systems. Our public trial lasted 9 days, during which 4555 unique peers participated from around the globe. We found 61% of the peers to be behind a firewall, a level at which our simulations still indicate acceptable performance. Most of the peers indeed obtained good performance, with for instance a very low prebuffering time before playback starts, indicating the feasibility of our approach. The median prebuffering time we measured was 3.6 seconds, which is 3-10 times shorter than the prebuffering time measured in other deployed peer-to-peer systems.

A number of analytical models exists that capture various properties of the BitTorrent protocol. However, until now virtually all of these models have been based on the assumption that the peers in the system have homogeneous bandwidths. As this is highly unrealistic in real swarms, these models have very limited applicability. Most of all, these models implicitly ignore BitTorrent's most important property: peer selection based on the highest rate of reciprocity. As a result, these models are not suitable for understanding or predicting the properties of real BitTorrent networks. Furthermore, they are hardly of use in the design of realistic BitTorrent simulators and new P2P protocols. In this paper, we extend existing work by presenting a model of a swarm in BitTorrent where peers have arbitrary upload and download bandwidths. In our model we group peers with (roughly) the same bandwidth in classes, and then analyze the allocation of upload slots from peers in one class to peers in another class. We show that our model accurately predicts the bandwidth clustering phenomenon observed experimentally in other work, and we analyze the resulting data distribution in swarms. We validate our model with experiments using real BitTorrent clients. Our model captures the effects of BitTorrent's well-known `tit-for-tat' mechanism in bandwidth-inhomogeneous swarms and provides an accurate mathematical description of the resulting dynamics.

Peer-to-peer file-sharing networks depend on peers uploading data to each other. Some peers, called free-riders, will not upload data unless there is an incentive to do so. Algorithms designed to prevent free-riding typically assume that connectivity is not a problem. However, on the Internet, a large fraction of the peers resides behind a firewall or NAT, making them unable to accept incoming connections. In this paper, we will prove that it is impossible to prevent free-riding when more than half of the peers are firewalled, and we will provide bounds on the sharing ratios (defined as the number of bytes uploaded divided by the number of bytes downloaded) of both firewalled and non-firewalled peers. Firewall puncturing techniques are complex but can be used to connect two firewalled peers; we will provide a bound on their required effectiveness in order to achieve fairness.We confirm our theory by simulating individual BitTorrent swarms (sets of peers that download the same file), and show that the theoretical bounds can be met in systems with many firewalled peers. We have also collected statistics covering thousands of BitTorrent swarms in several communities, both open and closed; the latter ban peers if their sharing ratios drop below a certain treshhold. We found 45% of the peers to be firewalled in the closed communities, as opposed to 66% in the open communities, which correlates with our theory that to obtain fair sharing ratios for all peers, at most half of them can be behind firewalls.

Abstract Most current peer‐to‐peer (P2P) file‐sharing systems treat their users as anonymous, unrelated entities, and completely disregard any social relationships between them. However, social phenomena such as friendship and the existence of communities of users with similar tastes or interests may well be exploited in such systems in order to increase their usability and performance. In this paper we present a novel social‐based P2P file‐sharing paradigm that exploits social phenomena by maintaining social networks and using these in content discovery, content recommendation, and downloading. Based on this paradigm's main concepts such as taste buddies and friends, we have designed and implemented the TRIBLER P2P file‐sharing system as a set of extensions to BitTorrent. We present and discuss the design of TRIBLER, and we show evidence that TRIBLER enables fast content discovery and recommendation at a low additional overhead, and a significant improvement in download performance. Copyright © 2007 John Wiley & Sons, Ltd.

We propose a fully decentralized collaborative filtering approach that is self-organizing and operates in a distributed way. The relevances between downloading files (items) are stored locally at these items in so called item-based buddy tables and are updated each time that the items are downloaded. We then propose to use the language model to build recommendations for the different users based on the buddy tables of those items a user has downloaded previously. We have tested and compared our distributed collaborative filtering approach to centralized collaborative filtering and showed that it has similar performance. It is therefore a promising technique to facilitate recommendations in peer-to-peer networks.

Clock (and voltage) scheduling is an important technique to reduce the energy consumption of processors that support voltage scaling. It is difficult, however, to achieve good results using only statistics from the operating system level when applications show bursty (unpredictable) behavior. We take the approach that such applications must be made power-aware and specify their average execution time (AET) and the deadline to the scheduler controlling the clock speed and processor voltage. This paper describes our energy priority scheduling (EPS) algorithm supporting power-aware applications. EPS orders tasks according to how tight their deadlines are and how often tasks overlap. Low-priority tasks are scheduled first, since they can be easily preempted to accommodate for high-priority tasks later. The EPS algorithm does not always yield the optimal schedule, but has a low complexity. We have implemented EPS on a StrongARM-based variable-voltage platform. We conducted experiments with a modified video decoder that estimates the AET of each frame. Measurements show that application-directed voltage scaling reduces processor power consumption with 50% for the bursty video decoder without missing any frame deadlines.

Clock (and voltage) scheduling is an important technique to reduce energy consumption of variable-voltage processors. It is dicult, however, to achieve good results at the OS and hardware level when applications show bursty behavior. We take the approach that such applications must be made power aware and specify their future demands to a central scheduler controlling the clock speed and processor voltage. This paper describes our energy priority scheduling (EPS) heuristic that orders tasks according to how tight their deadlines are and how often tasks overlap. We schedule low-priority tasks rst, since they can be easily preempted to accommodate for high-priority tasks later. The EPS heuristic does not always yield the optimal schedule, but has low complexity and can be used as an incremental on-line algorithm. We implemented EPS on a StrongARM-based variable-voltage platform. Measurements show that EPS reduces energy consumption with 50% for a bursty video decoding application without missing any frame deadlines.

Power consumption is the limiting factor for the functionality of future wearable devices. Since interactive applications like wireless information access generate bursts of activities, it is important to match the performance of the wearable device accordingly. This paper describes a system with a microprocessor whose speed can be varied (frequency scaling) as well as its supply voltage. Voltage scaling is important for reducing power consumption to very low values when operating at low speeds. Measurements show that the energy per instruction at minimal speed is 1/5 of the energy required at full speed. The frequency and voltage can be scaled dynamically from user space in only 140 μs. This allows power-aware applications to quickly adjust the performance level of the processor whenever the workload changes. Experiments with an H.263 video benchmark show that the power-aware decoder outperforms a static fixed-frequency policy as well as a dynamic interval-based scheduler.