BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Antonio Fernández Anta

Antonio Fernández Anta appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Distributed, Parallel, and Cluster ComputingNetworking and Internet ArchitectureComputer Science and Game TheoryData Structures and AlgorithmsApplicationscs.CYComputationCryptography and SecurityDiscrete MathematicsMethodologyPerformancephysics.comp-phSocial and Information Networks

Catalog footprint

What is connected

25works
13topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

25 published item(s)

preprint2022arXiv

How resilient is the Open Web to the COVID-19 pandemic?

In this paper we refer to the Open Web to the set of services offered freely to Internet users, representing a pillar of modern societies. Despite its importance for society, it is unknown how the COVID-19 pandemic is affecting the Open Web. In this paper, we address this issue, focusing our analysis on Spain, one of the countries which have been most impacted by the pandemic. On the one hand, we study the impact of the pandemic in the financial backbone of the Open Web, the online advertising business. To this end, we leverage concepts from Supply-Demand economic theory to perform a careful analysis of the elasticity in the supply of ad-spaces to the financial shortage of the online advertising business and its subsequent reduction in ad spaces' price. On the other hand, we analyze the distribution of the Open Web composition across business categories and its evolution during the COVID-19 pandemic. These analyses are conducted between Jan 1st and Dec 31st, 2020, using a reference dataset comprising information from more than 18 billion ad spaces. Our results indicate that the Open Web has experienced a moderate shift in its composition across business categories. However, this change is not produced by the financial shortage of the online advertising business, because as our analysis shows, the Open Web's supply of ad spaces is inelastic (i.e., insensitive) to the sustained low-price of ad spaces during the pandemic. Instead, existing evidence suggests that the reported shift in the Open Web composition is likely due to the change in the users' online behavior (e.g., browsing and mobile apps utilization patterns).

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Multivariate Functional Outlier Detection using the FastMUOD Indices

We present definitions and properties of the fast massive unsupervised outlier detection (FastMUOD) indices, used for outlier detection (OD) in functional data. FastMUOD detects outliers by computing, for each curve, an amplitude, magnitude and shape index meant to target the corresponding types of outliers. Some methods adapting FastMUOD to outlier detection in multivariate functional data are then proposed. These include applying FastMUOD on the components of the multivariate data and using random projections. Moreover, these techniques are tested on various simulated and real multivariate functional datasets. Compared with the state of the art in multivariate functional OD, the use of random projections showed the most effective results with similar, and in some cases improved, OD performance.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Setchain: Improving Blockchain Scalability with Byzantine Distributed Sets and Barriers

Blockchain technologies are facing a scalability challenge, which must be overcome to guarantee a wider adoption of the technology. This scalability issue is mostly caused by the use of consensus algorithms to guarantee the total order of the chain of blocks (and of the operations within each block). However, total order is often overkilling, since important advanced applications of smart-contracts do not require a total order of all the operations. Hence, if a more relaxed partial order (instead of a total order) is allowed under certain safety conditions, a much higher scalability can be achieved. In this paper, we propose a distributed concurrent data type, called Setchain, that allows implementing this partial order and increases significantly blockchain scalability. A Setchain implements a grow-only set object whose elements are not totally ordered, unlike conventional blockchain operations. When convenient, the Setchain allows forcing a synchronization barrier that assigns permanently an epoch number to a subset of the latest elements added. With the Setchain, operations in the same epoch are not ordered, while operations in different epochs are. We present different Byzantine-tolerant implementations of Setchain, prove their correctness and report on an empirical evaluation of a direct implementation. Our results show that Setchain is orders of magnitude faster than consensus-based ledgers to implement grow-only sets with epoch synchronization. Since the Setchain barriers can be synchronized with block consolidation, Setchain objects can be used as a sidechain to implement many smart contract solutions with much faster operations than on basic blockchains.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Validated Objects: Specification, Implementation, and Applications

Guaranteeing the validity of concurrent operations on distributed objects is a key property for ensuring reliability and consistency in distributed systems. Usually, the methods for validating these operations, if present, are wired in the object implementation. In this work, we formalize the notion of a {\em validated object}, decoupling the object operations and properties from the validation procedure. We consider two types of objects, satisfying different levels of consistency: the validated {\em totally-ordered} object, offering a total ordering of its operations, and its weaker variant, the validated {\em regular} object. We provide conditions under which it is possible to implement these objects. In particular, we show that crash-tolerant implementations of validated regular objects are always possible in an asynchronous system with a majority of correct processes. However, for validated totally-ordered objects, consensus is always required if a property of the object we introduce in this work, {\em persistent validity,} does not hold. Persistent validity combined with another new property, {\em persistent execution}, allows consensus-free crash-tolerant implementations of validated totally-ordered objects. We demonstrate the utility of validated objects by considering several applications conforming to our formalism.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

CoronaSurveys: Using Surveys with Indirect Reporting to Estimate the Incidence and Evolution of Epidemics

The world is suffering from a pandemic called COVID-19, caused by the SARS-CoV-2 virus. National governments have problems evaluating the reach of the epidemic, due to having limited resources and tests at their disposal. This problem is especially acute in low and middle-income countries (LMICs). Hence, any simple, cheap and flexible means of evaluating the incidence and evolution of the epidemic in a given country with a reasonable level of accuracy is useful. In this paper, we propose a technique based on (anonymous) surveys in which participants report on the health status of their contacts. This indirect reporting technique, known in the literature as network scale-up method, preserves the privacy of the participants and their contacts, and collects information from a larger fraction of the population (as compared to individual surveys). This technique has been deployed in the CoronaSurveys project, which has been collecting reports for the COVID-19 pandemic for more than two months. Results obtained by CoronaSurveys show the power and flexibility of the approach, suggesting that it could be an inexpensive and powerful tool for LMICs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Hide Me: Enabling Location Privacy in Heterogeneous Vehicular Networks

To support location-based services, vehicles must share their location with a server to receive relevant data, compromising their (location) privacy. To alleviate this privacy compromise, the vehicle's location can be obfuscated by adding artificial noise. Under limited available bandwidth, and since the area including the vehicle's location increases with the noise, the server will provide fewer data relevant to the vehicle's true location, reducing the effectiveness of a location-based service. To alleviate this problem, we propose that data relevant to a vehicle is also provided through direct, ad hoc communication by neighboring vehicles. Through such Vehicle-to-Vehicle (V2V) cooperation, the impact of location obfuscation is mitigated. Since vehicles subscribe to data of (location-dependent) impact values, neighboring vehicles will subscribe to largely overlapping sets of data, reducing the benefit of V2V cooperation. To increase such benefit, we develop and study a non-cooperative game determining the data that a vehicle should subscribe to, aiming at maximizing its utilization while considering the participating (neighboring) vehicles. Our analysis and results show that the proposed V2V cooperation and derived strategy lead to significant performance increase compared to non-cooperative approaches and largely alleviates the impact of privacy on location-based services.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Mechanism for Fair Distribution of Resources without Payments

We design a mechanism for Fair and Efficient Distribution of Resources (FEDoR) in the presence of strategic agents. We consider a multiple-instances, Bayesian setting, where in each round the preference of an agent over the set of resources is a private information. We assume that in each of r rounds n agents are competing for k non-identical indivisible goods, (n > k). In each round the strategic agents declare how much they value receiving any of the goods in the specific round. The agent declaring the highest valuation receives the good with the highest value, the agent with the second highest valuation receives the second highest valued good, etc. Hence we assume a decision function that assigns goods to agents based on their valuations. The novelty of the mechanism is that no payment scheme is required to achieve truthfulness in a setting with rational/strategic agents. The FEDoR mechanism takes advantage of the repeated nature of the framework, and through a statistical test is able to punish the misreporting agents and be fair, truthful, and socially efficient. FEDoR is fair in the sense that, in expectation over the course of the rounds, all agents will receive the same good the same amount of times. FEDoR is an eligible candidate for applications that require fair distribution of resources over time. For example, equal share of bandwidth for nodes through the same point of access. But further on, FEDoR can be applied in less trivial settings like sponsored search, where payment is necessary and can be given in the form of a flat participation fee. To this extent we perform a comparison with traditional mechanisms applied to sponsored search, presenting the advantage of FEDoR.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

CoVer-ability: Consistent Versioning for Concurrent Objects

An object type characterizes the domain space and the operations that can be invoked on an object of that type. In this paper we introduce a new property for concurrent objects, we call coverability, that aims to provide precise guarantees on the consistent evolution of an object. This new property is suitable for a variety of distributed objects including concurrent file objects that demand operations to manipulate the latest version of the object. We propose two levels of coverability: (i) strong coverability and (ii) weak coverability. Strong coverability requires that only a single operation can modify the latest version of the object, i.e. "covers" the latest version with a new version, imposing a total order on object modifications. Weak coverability relaxes the strong requirements of strong coverability and allows multiple operations to modify the same version of an object, where each modification leads to a different version. Weak coverability preserves consistent evolution of the object, by demanding any subsequent operation to only modify one of the newly introduced versions. Coverability combined with atomic guarantees yield to coverable atomic read/write registers. We also show that strongly coverable atomic registers are equivalent in power to consensus. Thus, we focus on weakly coverable registers, and we demonstrate their importance by showing that they cannot be implemented using similar types of registers, like ranked-registers. Furthermore we show that weakly coverable registers may be used to implement basic (weak) read-modify-write and file objects. Finally, we implement weakly coverable registers by modifying an existing MWMR atomic register implementation.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Internet Computing: Using Reputation to Select Workers from a Pool

The assignment and execution of tasks over the Internet is an inexpensive solution in contrast with supercomputers. We consider an Internet-based Master-Worker task computing approach, such as SETI@home. A master process sends tasks, across the Internet, to worker processors. Workers execute, and report back a result. Unfortunately, the disadvantage of this approach is the unreliable nature of the worker processes. Through different studies, workers have been categorized as either malicious (always report an incorrect result), altruistic (always report a correct result), or rational (report whatever result maximizes their benefit). We develop a reputation-based mechanism that guarantees that, eventually, the master will always be receiving the correct task result. We model the behavior of the rational workers through reinforcement learning, and we present three different reputation types to choose, for each computational round, the most reputable from a pool of workers. As workers are not always available, we enhance our reputation scheme to select the most responsive workers. We prove sufficient conditions for eventual correctness under the different reputation types. Our analysis is complemented by simulations exploring various scenarios. Our simulation results expose interesting trade-offs among the different reputation types, workers availability, and cost.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Multi-resource Energy-efficient Routing in Cloud Data Centers with Networks-as-a-Service

With the rapid development of software defined networking and network function virtualization, researchers have proposed a new cloud networking model called Network-as-a-Service (NaaS) which enables both in-network packet processing and application-specific network control. In this paper, we revisit the problem of achieving network energy efficiency in data centers and identify some new optimization challenges under the NaaS model. Particularly, we extend the energy-efficient routing optimization from single-resource to multi-resource settings. We characterize the problem through a detailed model and provide a formal problem definition. Due to the high complexity of direct solutions, we propose a greedy routing scheme to approximate the optimum, where flows are selected progressively to exhaust residual capacities of active nodes, and routing paths are assigned based on the distributions of both node residual capacities and flow demands. By leveraging the structural regularity of data center networks, we also provide a fast topology-aware heuristic method based on hierarchically solving a series of vector bin packing instances. Our simulations show that the proposed routing scheme can achieve significant gain on energy savings and the topology-aware heuristic can produce comparably good results while reducing the computation time to a large extent.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Online Distributed Scheduling on a Fault-prone Parallel System

We consider a parallel system of $m$ identical machines prone to unpredictable crashes and restarts, trying to cope with the continuous arrival of tasks to be executed. Tasks have different computational requirements (i.e., processing time or size). The flow of tasks, their size, and the crash and restart of the machines are assumed to be controlled by an adversary. Then, we focus on the study of online distributed algorithms for the efficient scheduling of the tasks. We use competitive analysis, considering as efficiency metric the completed-load, i.e., the aggregated size of the completed tasks. We first present optimal completed-load competitiveness algorithms when the number of different task sizes that can be injected by the adversary is bounded. (It is known that, if it is not bounded, competitiveness is not achievable.) We first consider only two different task sizes, and then proceed to $k$ different ones, showing in both cases that the optimal completed-load competitiveness can be achieved. Then, we consider the possibility of having some form of resource augmentation, allowing the scheduling algorithm to run with a speedup $s \geq 1$. In this case, we show that the competitiveness of all work-conserving scheduling algorithms can be increased by using a large enough speedup.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Resource location based on precomputed partial random walks in dynamic networks

The problem of finding a resource residing in a network node (the \emph{resource location problem}) is a challenge in complex networks due to aspects as network size, unknown network topology, and network dynamics. The problem is especially difficult if no requirements on the resource placement strategy or the network structure are to be imposed, assuming of course that keeping centralized resource information is not feasible or appropriate. Under these conditions, random algorithms are useful to search the network. A possible strategy for static networks, proposed in previous work, uses short random walks precomputed at each network node as partial walks to construct longer random walks with associated resource information. In this work, we adapt the previous mechanisms to dynamic networks, where resource instances may appear in, and disappear from, network nodes, and the nodes themselves may leave and join the network, resembling realistic scenarios. We analyze the resulting resource location mechanisms, providing expressions that accurately predict average search lengths, which are validated using simulation experiments. Reduction of average search lengths compared to simple random walk searches are found to be very large, even in the face of high network volatility. We also study the cost of the mechanisms, focusing on the overhead implied by the periodic recomputation of partial walks to refresh the information on resources, concluding that the proposed mechanisms behave efficiently and robustly in dynamic networks.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Multi-round Master-Worker Computing: a Repeated Game Approach

We consider a computing system where a master processor assigns tasks for execution to worker processors through the Internet. We model the workers decision of whether to comply (compute the task) or not (return a bogus result to save the computation cost) as a mixed extension of a strategic game among workers. That is, we assume that workers are rational in a game-theoretic sense, and that they randomize their strategic choice. Workers are assigned multiple tasks in subsequent rounds. We model the system as an infinitely repeated game of the mixed extension of the strategic game. In each round, the master decides stochastically whether to accept the answer of the majority or verify the answers received, at some cost. Incentives and/or penalties are applied to workers accordingly. Under the above framework, we study the conditions in which the master can reliably obtain tasks results, exploiting that the repeated games model captures the effect of long-term interaction. That is, workers take into account that their behavior in one computation will have an effect on the behavior of other workers in the future. Indeed, should a worker be found to deviate from some agreed strategic choice, the remaining workers would change their own strategy to penalize the deviator. Hence, being rational, workers do not deviate. We identify analytically the parameter conditions to induce a desired worker behavior, and we evaluate experi- mentally the mechanisms derived from such conditions. We also compare the performance of our mechanisms with a previously known multi-round mechanism based on reinforcement learning.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Improving Resource Location with Locally Precomputed Partial Random Walks

Random walks can be used to search complex networks for a desired resource. To reduce search lengths, we propose a mechanism based on building random walks connecting together partial walks (PW) previously computed at each network node. Resources found in each PW are registered. Searches can then jump over PWs where the resource is not located. However, we assume that perfect recording of resources may be costly, and hence, probabilistic structures like Bloom filters are used. Then, unnecessary hops may come from false positives at the Bloom filters. Two variations of this mechanism have been considered, depending on whether we first choose a PW in the current node and then check it for the resource, or we first check all PWs and then choose one. In addition, PWs can be either simple random walks or self-avoiding random walks. Analytical models are provided to predict expected search lengths and other magnitudes of the resulting four mechanisms. Simulation experiments validate these predictions and allow us to compare these techniques with simple random walk searches, finding very large reductions of expected search lengths.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Measuring the Impact of Adversarial Errors on Packet Scheduling Strategies

In this paper we explore the problem of achieving efficient packet transmission over unreliable links with worst case occurrence of errors. In such a setup, even an omniscient offline scheduling strategy cannot achieve stability of the packet queue, nor is it able to use up all the available bandwidth. Hence, an important first step is to identify an appropriate metric for measuring the efficiency of scheduling strategies in such a setting. To this end, we propose a relative throughput metric which corresponds to the long term competitive ratio of the algorithm with respect to the optimal. We then explore the impact of the error detection mechanism and feedback delay on our measure. We compare instantaneous error feedback with deferred error feedback, that requires a faulty packet to be fully received in order to detect the error. We propose algorithms for worst-case adversarial and stochastic packet arrival models, and formally analyze their performance. The relative throughput achieved by these algorithms is shown to be close to optimal by deriving lower bounds on the relative throughput of the algorithms and almost matching upper bounds for any algorithm in the considered settings. Our collection of results demonstrate the potential of using instantaneous feedback to improve the performance of communication systems in adverse environments.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Online Parallel Scheduling of Non-uniform Tasks: Trading Failures for Energy

Consider a system in which tasks of different execution times arrive continuously and have to be executed by a set of processors that are prone to crashes and restarts. In this paper we model and study the impact of parallelism and failures on the competitiveness of such an online system. In a fault-free environment, a simple Longest-in-System scheduling policy, enhanced by a redundancy-avoidance mechanism, guarantees optimality in a long-term execution. In the presence of failures though, scheduling becomes a much more challenging task. In particular, no parallel deterministic algorithm can be competitive against an offline optimal solution, even with one single processor and tasks of only two different execution times. We find that when additional energy is provided to the system in the form of processor speedup, the situation changes. Specifically, we identify thresholds on the speedup under which such competitiveness cannot be achieved by any deterministic algorithm, and above which competitive algorithms exist. Finally, we propose algorithms that achieve small bounded competitive ratios when the speedup is over the threshold.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Reducing Search Lengths with Locally Precomputed Partial Random Walks

Random walks can be used to search a complex networks for a desired resource. To reduce the number of hops necessary to find the resource, we propose a search mechanism based on building random walks connecting together partial walks that have been precomputed at each network node in an initial stage. The resources found in each partial walk are registered in its associated Bloom filter. Searches can then jump over partial nodes in which the resource is not located, significantly reducing search length. However, additional unnecessary hops come from false positives at the Bloom filters. The analytic model provided predicts the expected search length of this mechanism, the optimal size of the partial walks and the corresponding optimal (shortest) expected search length. Simulation experiments are used to validate these predictions and to assess the impact of the number of partial walks precomputed in each node.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Routing for Energy Minimization with Discrete Cost Functions

Energy saving is becoming an important issue in the design and use of computer networks. In this work we propose a problem that considers the use of rate adaptation as the energy saving strategy in networks. The problem is modeled as an integral demand-routing problem in a network with discrete cost functions at the links. The discreteness of the cost function comes from the different states (bandwidths) at which links can operate and, in particular, from the energy consumed at each state. This in its turn leads to the non-convexity of the cost function, and thus adds complexity to solve this problem. We formulate this routing problem as an integer program, and we show that the general case of this problem is NP-hard, and even hard to approximate. For the special case when the step ratio of the cost function is bounded, we show that effective approximations can be obtained. Our main algorithm executes two processes in sequence: relaxation and rounding. The relaxation process eliminates the non-convexity of the cost function, so that the problem is transformed into a fractional convex program solvable in polynomial time. After that, a randomized rounding process is used to get a feasible solution for the original problem. This algorithm provides a constant approximation ratio for uniform demands and an approximation ratio of $O(\log^{β-1} d)$ for non-uniform demands, where $β$ is a constant and $d$ is the largest demand.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Bisection (Band)Width of Product Networks with Application to Data Centers

The bisection width of interconnection networks has always been important in parallel computing, since it bounds the amount of information that can be moved from one side of a network to another, i.e., the bisection bandwidth. Finding its exact value has proven to be challenging for some network families. For instance, the problem of finding the exact bisection width of the multidimensional torus was posed by Leighton and has remained open for almost 20 years. In this paper we provide the exact value of the bisection width of the torus, as well as of several d-dimensional classical parallel topologies that can be obtained by the application of the Cartesian product of graphs. To do so, we first provide two general results that allow to obtain upper and lower bounds on the bisection width of a product graph as a function of some properties of its factor graphs. We also apply these results to obtain bounds for the bisection bandwidth of a d-dimensional BCube network, a recently proposed topology for data centers.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Node Sampling using Random Centrifugal Walks

Sampling a network with a given probability distribution has been identified as a useful operation. In this paper we propose distributed algorithms for sampling networks, so that nodes are selected by a special node, called the \emph{source}, with a given probability distribution. All these algorithms are based on a new class of random walks, that we call Random Centrifugal Walks (RCW). A RCW is a random walk that starts at the source and always moves away from it. Firstly, an algorithm to sample any connected network using RCW is proposed. The algorithm assumes that each node has a weight, so that the sampling process must select a node with a probability proportional to its weight. This algorithm requires a preprocessing phase before the sampling of nodes. In particular, a minimum diameter spanning tree (MDST) is created in the network, and then nodes' weights are efficiently aggregated using the tree. The good news are that the preprocessing is done only once, regardless of the number of sources and the number of samples taken from the network. After that, every sample is done with a RCW whose length is bounded by the network diameter. Secondly, RCW algorithms that do not require preprocessing are proposed for grids and networks with regular concentric connectivity, for the case when the probability of selecting a node is a function of its distance to the source. The key features of the RCW algorithms (unlike previous Markovian approaches) are that (1) they do not need to warm-up (stabilize), (2) the sampling always finishes in a number of hops bounded by the network diameter, and (3) it selects a node with the exact probability distribution.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Quid Pro Quo: A Mechanism for Fair Collaboration in Networked Systems

Collaboration may be understood as the execution of coordinated tasks (in the most general sense) by groups of users, who cooperate for achieving a common goal. Collaboration is a fundamental assumption and requirement for the correct operation of many communication systems. The main challenge when creating collaborative systems in a decentralized manner is dealing with the fact that users may behave in selfish ways, trying to obtain the benefits of the tasks but without participating in their execution. In this context, Game Theory has been instrumental to model collaborative systems and the task allocation problem, and to design mechanisms for optimal allocation of tasks. In this paper, we revise the classical assumptions and propose a new approach to this problem. First, we establish a system model based on heterogenous nodes (users, players), and propose a basic distributed mechanism so that, when a new task appears, it is assigned to the most suitable node. The classical technique for compensating a node that executes a task is the use of payments (which in most networks are hard or impossible to implement). Instead, we propose a distributed mechanism for the optimal allocation of tasks without payments. We prove this mechanism to be robust event in the presence of independent selfish or rationally limited players. Additionally, our model is based on very weak assumptions, which makes the proposed mechanisms susceptible to be implemented in networked systems (e.g., the Internet).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Conauto-2.0: Fast Isomorphism Testing and Automorphism Group Computation

In this paper we present an algorithm, called conauto-2.0, that can efficiently compute a set of generators of the automorphism group of a graph, and test whether two graphs are isomorphic, finding an isomorphism if they are. This algorithm uses the basic individualization/refinement technique, and is an improved version of the algorithm conauto, which has been shown to be very fast for random graphs and several families of hard graphs. In this paper, it is proved that, under some circumstances, it is not only possible to prune the search space (using already found generators of the automorphism group), but also to infer new generators without the need of explicitly finding an automorphism of the graph. This result is especially suited for graphs with regularly connected components, and can be applied in any isomorphism testing and canonical labeling algorithm (that use the individualization/refinement technique) to significantly improve its performance. Additionally, a dynamic target cell selection function is used to adapt to different graphs. The resulting algorithm preserves all the nice features of conauto, but reduces the time for testing graphs with regularly connected components and other hard graph families. We run extensive experiments, which show that the most popular algorithms (namely, nauty, bliss, Traces, and saucy) are slower than conauto-2.0, among others, for the graph families based on components.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Failure Detectors in Homonymous Distributed Systems (with an Application to Consensus)

This paper addresses the consensus problem in homonymous distributed systems where processes are prone to crash failures and have no initial knowledge of the system membership ("homonymous" means that several processes may have the same identifier). New classes of failure detectors suited to these systems are first defined. Among them, the classes HΩ and HΣ are introduced that are the homonymous counterparts of the classes Ω and Σ, respectively. (Recall that the pair <Ω,Σ> defines the weakest failure detector to solve consensus.) Then, the paper shows how HΩ and HΣ can be implemented in homonymous systems without membership knowledge (under different synchrony requirements). Finally, two algorithms are presented that use these failure detectors to solve consensus in homonymous asynchronous systems where there is no initial knowledge of the membership. One algorithm solves consensus with <HΩ,HΣ>, while the other uses only HΩ, but needs a majority of correct processes. Observe that the systems with unique identifiers and anonymous systems are extreme cases of homonymous systems from which follows that all these results also apply to these systems. Interestingly, the new failure detector class HΩ can be implemented with partial synchrony, while the analogous class AΩ defined for anonymous systems can not be implemented (even in synchronous systems). Hence, the paper provides us with the first proof showing that consensus can be solved in anonymous systems with only partial synchrony (and a majority of correct processes).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Greening File Distribution: Centralized or Distributed?

Despite file-distribution applications are responsible for a major portion of the current Internet traffic, so far little effort has been dedicated to study file distribution from the point of view of energy efficiency. In this paper, we present a first approach at the problem of energy efficiency for file distribution. Specifically, we first demonstrate that the general problem of minimizing energy consumption in file distribution in heterogeneous settings is NP-hard. For homogeneous settings, we derive tight lower bounds on energy consumption, and we design a family of algorithms that achieve these bounds. Our results prove that collaborative p2p schemes achieve up to 50% energy savings with respect to the best available centralized file distribution scheme. Through simulation, we demonstrate that in more realistic cases (e.g., considering network congestion, and link variability across hosts) we validate this observation, since our collaborative algorithms always achieve significant energy savings with respect to the power consumption of centralized file distribution systems.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Unbounded Contention Resolution in Multiple-Access Channels

A frequent problem in settings where a unique resource must be shared among users is how to resolve the contention that arises when all of them must use it, but the resource allows only for one user each time. The application of efficient solutions for this problem spans a myriad of settings such as radio communication networks or databases. For the case where the number of users is unknown, recent work has yielded fruitful results for local area networks and radio networks, although either a (possibly loose) upper bound on the number of users needs to be known, or the solution is suboptimal, or it is only implicit or embedded in other problems, with bounds proved only asymptotically. In this paper, under the assumption that collision detection or information on the number of contenders is not available, we present a novel protocol for contention resolution in radio networks, and we recreate a protocol previously used for other problems, tailoring the constants for our needs. In contrast with previous work, both protocols are proved to be optimal up to a small constant factor and with high probability for big enough number of contenders. Additionally, the protocols are evaluated and contrasted with the previous work by extensive simulations. The evaluation shows that the complexity bounds obtained by the analysis are rather tight, and that both protocols proposed have small and predictable complexity for many system sizes (unlike previous proposals).

0 citations0 reviewsNo code linkedOpen access