IMDEA Networks Institute Digital Repository
Not a member yet
1915 research outputs found
Sort by
Applying the dynamics of evolution to achieve reliability in master–worker computing
Get PDFWe consider Internet-based master–worker task computations, such as SETI@home, where a master process sends tasks, across the Internet, to worker processes; workers execute and report back some result. However, these workers are not trustworthy, and it might be at their best interest to report incorrect results. In such master–worker computations, the behavior and the best interest of the workers might change over time. We model such computations using evolutionary dynamics, and we study the conditions under which the master can reliably obtain task results. In particular, we develop and analyze an algorithmic mechanism based on reinforcement learning to provide workers with the necessary incentives to eventually become truthful. Our analysis identifies the conditions under which truthful behavior can be ensured and bounds the expected convergence time to that behavior. The analysis is complemented with illustrative simulations.pu
Investigating the Reaction of BitTorrent Content Publishers to Anti-Piracy Actions
Get PDFDuring recent years,a few countries have put in place online antipiracy laws and there has been some major enforcement actions against violators. This raises the question that to what extent antipiracy actions have been effective in deterring online piracy? This is a challenging issue to explore because of the difficulty to capture user behavior, and to identify the subtle effect of various underlying (and potentially opposing) causes. In this paper, we tackle this question by examining the impact of two major antipiracy actions, the closure of Megaupload and the implementation of the French antipiracy law, on publishers in the largest BitTorrent portal who are major providers of copyrighted content online. We capture snapshots of BitTorrent publishers at proper times relative to the targeted antipiracy event and use the trends in the number and the level of activity of these publishers to assess their reaction to these events. Our investigation illustrates the importance of examining the impact of antipiracy events on different groups of publishers and provides valuable insights on the effect of selected major antipiracy actions on publishers' behavior.TRUEpu
Novel Techniques for Automorphism Group Computation
Get PDFSpringer 2013 Lecture Notes in Computer Science ISBN 978-3-642-38526-1Graph automorphism (GA) is a classical problem, in which the objective is to compute the automorphism group of an input graph. In this work we propose four novel techniques to speed up algorithms that solve the GA problem by exploring a search tree. They increase the performance of the algorithm by allowing to reduce the depth of the search tree, and by effectively pruning it.
We formally prove that a GA algorithm that uses these techniques correctly computes the automorphism group of the input graph. We also describe how the techniques have been incorporated into the GA algorithm conauto, as conauto-2.03, with at most an additive polynomial increase in its asymptotic time complexity.
We have experimentally evaluated the impact of each of the above techniques with several graph families. We have observed that each of the techniques by itself significantly reduces the number of processed nodes of the search tree in some subset of graphs, which justifies the use of each of them. Then, when they are applied together, their effect is combined, leading to reductions in the number of processed nodes in most graphs. This is also reflected in a reduction of the running time, which is substantial in some graph families.TRUEpu
Maximizing Bandwidth provision in interval scheduling with application to optical networks
No full textDOII: http://dx.doi.org/10.1109/ICTON.2013.6602757
ISSN:2161-2056We study an interval scheduling problem in which each job j is associated with a time interval Ij, a minimum aj and maximum bj required bandwidths, and a weight wj. We are given W colors. We need to assign to each job j between aj and bj colors, such that each color is assigned at each time to at most one interval. The weighted bandwidth allocated to job j is the number of colors allocated to it times |Ij|, and the weighted bandwidth of a coloring is the sum of the weighted bandwidth of all jobs. The objective is to find a coloring with maximum weighted bandwidth. A coloring is (circularly) contiguous if the set of colors for each job forms an (circular) interval.TRUEpu
A Packet Encoding Algorithm for Network Coding with Multiple Next Hop Neighbor Consideration and its Integration with Delta Routing
No full textDOI: http://dx.doi.org/10.1109/WoWMoM.2013.6583404
Print ISBN: 978-1-4673-5827-9We propose an efficient packet encoding algorithm for network coding that considers multiple neighbors, as the next hop candidates for a packet while searching for an optimal packet combination to transmit. Our algorithm, based on bipartite graphs, lets a node exhaustively search its queue to identify the maximum set of packets that can be combined in a single transmission. This algorithm can be easily integrated with a routing scheme in which a node considers multiple neighbors before choosing to forward a packet to one of them. We demonstrate this by coupling our algorithm with delta routing. Throughput benefit offered due to network coding is often hampered by congested nodes in a network. Integration of our encoding algorithm with delta routing helps packets circumnavigate congested parts of the network, as demonstrated by the contour graphs of transmission densities. In our routing mechanism a node only requires information available from its immediate neighbors in order to make decisions regarding coding and forwarding the packets. Our simulations show that by encoding packets more efficiently and routing them through the underutilized parts of the network, our routing scheme achieves 50.00% to 92.59% higher throughput than conventional shortest path routing. This throughput benefit is 23.68% to 55.88% improvement over utilizing coding on the shortest path routing.TRUEpu
An early-stopping protocol for computing aggregate functions in Sensor Networks
Get PDFIn this paper, we study algebraic aggregate computations in Sensor Networks. The main contribution is the presentation of an early-stopping protocol that computes the average function under a harsh model of the conditions under which sensor nodes operate. This protocol is shown to be time-optimal in the presence of infrequent failures. The approach followed saves time and energy by the computation relying on a small network of delegate nodes that can be rebuilt fast in case of node failures and communicate using a collision-free schedule. Delegate nodes run two protocols simultaneously, namely, a collection/dissemination tree-based algorithm, which is shown to be optimal, and a mass-distribution algorithm. Both algorithms are analyzed under a model where the frequency of failures is a parameter. Other aggregate computation algorithms can be easily derived from this protocol. To the best of our knowledge, this is the first optimal early-stopping algorithm for aggregate computations in Sensor Networks.TRUEpu
