IMDEA Networks Institute Digital Repository
Not a member yet
1915 research outputs found
Sort by
Byzantine-tolerant Distributed Grow-only Sets: Specification and Applications
Get PDFBlockchains (as termed by Nakamoto in [14]) or Distributed Ledger Technologies(DLTs) (as used in [7] and [15]) became one of the most trendy data structures following the introduction of crypto-currencies [14] and their recent application in finance and token-economy. Despite their early wide adoption, little was known initially about the fundamental construction and semantic properties ofDLTs. A number of research groups attempted to provide rigorous definitions to characterise the fundamental properties of DLTs as those used in Bitcoin and beyond [1, 7, 8]. Among those, Fernández Anta et al. [7], was the first to identify and provide a formal definition of a reliable concurrent object, termedDistributed Ledger Object(DLO), which conveys the essential building block form any DLTs.With a growing amount of works dedicated to the Distributed Ledger formalization, it was shown in [10] that cryptocurrencies do not need consensus to be implemented. From a theoretical point of view, it was shown in [9] that, assuming one process per account, the consensus number of cryptocurrencies is 1. A non-sequential specification of money transfer was introduced in [2]. It follows that Byzantine transactional systems do not necessarily need consensus, but rather can be implemented on top of less powerful data structures. That’s one of the reason why we focused on providing a lighter tool that gets rid of the strict ordering information of the elements that are added to the system.FALSEpu
An experimental characterization of workers' behavior and accuracy in crowdsourced tasks
Get PDFCrowdsourcing systems are evolving into a powerful tool of choice to deal with repetitive or lengthy human-based tasks. Prominent among those is Amazon Mechanical Turk, in which Human Intelligence Tasks, are posted by requesters, and afterwards selected and executed by subscribed (human) workers in the platform. Many times these HITs serve for research purposes. In this context, a very important question is how reliable the results obtained through these platforms are, in view of the limited control a requester has on the workers’ actions. Various control techniques are currently proposed but they are not free from shortcomings, and their use must be accompanied by a deeper understanding of the workers’ behavior. In this work, we attempt to interpret the workers’ behavior and reliability level in the absence of control techniques. To do so, we perform a series of experiments with 600 distinct MTurk workers, specifically designed to elicit the worker’s level of dedication to a task, according to the task’s nature and difficulty. We show that the time required by a worker to carry out a task correlates with its difficulty, and also with the quality of the outcome. We find that there are different types of workers. While some of them are willing to invest a significant amount of time to arrive at the correct answer, at the same time we observe a significant fraction of workers that reply with a wrong answer. For the latter, the difficulty of the task and the very short time they took to reply suggest that they, intentionally, did not even attempt to solve the task.pu
Precise: Predictive Content Dissemination Schemes Exploiting Realistic Mobility Patterns
Get PDFDevice-to-Device (D2D) communications have expanded the way of managing available network resources to efficiently distribute data between users. D2D exploits communication alternatives, in Opportunistic Networks, based on short range wireless radio technologies such as Bluetooth and WiFi-Direct. Besides, nowadays in most urban areas, realistic human mobility is characterized by often repeated patterns that can be used to accurately predict the next visited regions—we call these regions hotspots (or Replication Zones (RZs)). In this work, we present Predictive Content Dissemination Scheme (Precise), to explore and combine the D2D paradigm along with real mobility and predictions focused on the dissemination of content among hotspots. To analyze the viability of such scheme, we show simulation results and evaluate the average content availability, lifetime and delivery delay, storage usage and network utilization metrics. We compare the performance of Precise with state-of-the-art approaches, such as Epidemic, restricted Epidemic, and Proximity-Interest-Social (PIS) routing protocols. Our results underline the need for smart usage of communication opportunities and storage. We demonstrate that Precise allows for a neat reduction in network activity by decreasing the number of data exchanges by up to 92%, requiring the use of up to 50% less of on-device storage. This comes at negligible costs. In particular, the delivery delay with Precise shows an increase with respect to epidemic dissemination schemes that varies from 0.03 seconds in the most dynamic case to at most 1.91 seconds for the least dynamic case, and which however does not hinder the possibility to use Precise for real-time applications. Regarding how contents are spread, we observe that Precise requires 2% to 20% less mobile users to carry them within a target hotspot, especially under slow dynamics. This however does not impact on the probability that mobile users entering the hotspots obtain contents, and barely shortens the lifetime of contents in our experiments from 100 minutes down to about 95, in the worst case. This demonstrates that the reduction of content availability among mobile users with Precise is either negligible or not impactful, thus guaranteeing the dissemination of contents as with legacy epidemic dissemination protocols.Comunidad de MadridTRUEpu
System Stability Under Adversarial Injection of Dependent Tasks
Get PDFTechnological changes (NFV, Osmotic Computing, Cyber-physical Systems) are making very important devising techniques to efficiently run a flow of jobs formed by dependent tasks in a set of servers. These problem can be seen as generalizations of the dynamic job-shop scheduling problem, with very rich dependency patterns and arrival assumptions. In this work, we consider a computational model of a distributed system formed by a set of servers in which jobs, that are continuously arriving, have to be executed. Every job is formed by a set of dependent tasks (i. e., each task may have to wait for others to be completed before it can be started), each of which has to be executed in one of the servers. The arrival of jobs and their properties is assumed to be controlled by a bounded adversary, whose only restriction is that it cannot overload any server. This model is a non-trivial generalization of the Adversarial Queuing Theory model of Borodin et al., and, like that model, focuses on the stability of the system: whether the number of jobs pending to be completed is bounded at all times. We show multiple results of stability and instability for this adversarial model under different combinations of the scheduling policy used at the servers, the arrival rate, and the dependence between tasks in the jobs.Spanish State Research Agency - Spanish Ministry of Science and InnovationDepartment of Education and Research of the Regional Government of MadridTRUEpu
Superintelligence Cannot be Contained: Lessons from Computability Theory
Get PDFSuperintelligence is a hypothetical agent that possesses intelligence far surpassing that of the brightest and most gifted human minds. In light of recent advances in machine intelligence, a number of scientists, philosophers and technologists have revived the discussion about the potentially catastrophic risks entailed by such an entity. In this article, we trace the origins and development of the neo-fear of superintelligence, and some of the major proposals for its containment. We argue that total containment is, in principle, impossible, due to fundamental limits inherent to computing itself. Assuming that a superintelligence will contain a program that includes all the programs that can be executed by a universal Turing machine on input potentially as complex as the state of the world, strict containment requires simulations of such a program, something theoretically (and practically) impossible.pu
On blockchain integration into mobile crowdsensing via smart embedded devices: A comprehensive survey
No full textAs an integral part of Internet of Things (IoT), mobile crowdsensing (MCS) via smart embedded devices has recently gained significant attention for being effective in a wide range of applications and services, particularly in smart environments. In order to collect data, MCS systems seek ubiquitous sensing services from smart mobile devices such as smartphones, tablets and wearables, which are equipped with a variety of sensors, and provide analytics, visualization and recommendation services. Despite its benefits, the distributed nature of MCS results in confronting a number of challenges in terms of incentives, privacy, security and dependability. In this survey, blockchains, as a state of the art technology that builds on decentralization, immutability and consensus characteristics, are comprehensively reviewed with their potential to address main challenges in MCS. To this end, this article reviews the MCS platforms by investigating the existing works along with their challenges. Furthermore, the article reviews blockchain-integrated MCS solutions to address the incentive mechanisms, data quality, and privacy and security issues. This survey’s objective is not only to analyze existing works but also to present potential directions for future research to leverage MCS and blockchains in smart environments.pu
RL-Cache: Learning-Based Cache Admission for Content Delivery
No full textContent delivery networks (CDNs) distribute much of the Internet content by caching and serving the objects requested by users. A major goal of a CDN is to maximize the hit rates of its caches, thereby enabling faster content downloads to the users. Content caching involves two components: an admission algorithm to decide whether to cache an object and an eviction algorithm to decide which object to evict from the cache when it is full. In this paper, we focus on cache admission and propose an algorithm called RL-Cache that uses model-free reinforcement learning (RL) to decide whether or not to admit a requested object into the CDN’s cache. Unlike prior approaches that use a small set of criteria for decision making, RL-Cache weights a large set of features that include the object size, recency, and frequency of access. We develop a publicly available implementation of RL-Cache and perform an evaluation using production traces for the image, video, and web traffic classes from Akamai’s CDN. The evaluation shows that RL-Cache improves the hit rate in comparison with the state of the art and imposes only a modest resource overhead on the CDN servers. Further, RL-Cache is robust enough that it can be trained in one location and executed on request traces of the same or different traffic classes in other locations of the same geographic region.FALSEpu
Trouble Over-The-Air: An Analysis of FOTA Apps in the Android Ecosystem
Get PDFAndroid firmware updates are typically managed by the so-called FOTA (Firmware Over-the-Air) apps. Such apps are highly privileged and play a critical role in maintaining
devices secured and updated. The Android operating system
offers standard mechanisms—available to Original Equipment
Manufacturers (OEMs)—to implement their own FOTA apps but such vendor-specific implementations could be a source of security and privacy issues due to poor software engineering practices. This paper performs the first large-scale and systematic analysis of the FOTA ecosystem through a dataset of 2,013 FOTA apps detected with a tool designed for this purpose over 422,121 pre-installed apps. We classify the different stakeholders developing and deploying FOTA apps on the Android update ecosystem, showing that 43% of FOTA apps are developed by third parties. We report that some devices can have as many
as 5 apps implementing FOTA capabilities. By means of static analysis of the code of FOTA apps, we show that some apps present behaviors that can be considered privacy intrusive, such as the collection of sensitive user data (e.g., geolocation linked to unique hardware identifiers), and a significant presence of third-party trackers. We also discover implementation issues leading to critical vulnerabilities, such as the use of public AOSP test keys both for signing FOTA apps and for update verification, thus allowing any update signed with the same key to be installed. Finally, we study telemetry data collected from
real devices by a commercial security tool. We demonstrate that FOTA apps are responsible for the installation of non-system apps (e.g., entertainment apps and games), including malware and Potentially Unwanted Programs (PUP). Our findings suggest that FOTA development practices are misaligned with Google’s recommendations.TRUEpu
