Source author record

Xavier Vilaça

Xavier Vilaça appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computer Science and Game Theory Distributed, Parallel, and Cluster Computing

Catalog footprint

What is connected

4works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2016arXiv

A Distributed Auctioneer for Resource Allocation in Decentralized Systems

In decentralized systems, nodes often need to coordinate to access shared resources in a fair manner. One approach to perform such arbitration is to rely on auction mechanisms. Although there is an extensive literature that studies auctions, most of these works assume the existence of a central, trusted auctioneer. Unfortunately, in fully decentralized systems, where the nodes that need to cooperate operate under separate spheres of control, such central trusted entity may not exist. Notable examples of such decentralized systems include community networks, clouds of clouds, cooperative nano data centres, among others. In this paper, we make theoretical and practical contributions to distribute the role of the auctioneer. From the theoretical perspective, we propose a framework of distributed simulations of the auctioneer that are Nash equilibria resilient to coalitions and asynchrony. From the practical perspective, our protocols leverage the distributed nature of the simulations to parallelise the execution. We have implemented a prototype that instantiates the framework for bandwidth allocation in community networks, and evaluated it in a real distributed setting.

preprint2016arXiv

Accountability in Dynamic Networks

We take a game theoretical approach to determine necessary and sufficient conditions under which we can persuade rational agents to exchange messages in pairwise exchanges over links of a dynamic network, by holding them accountable for deviations with punishments. We make three contributions: (1) we provide a new game theoretical model of repeated interactions in dynamic networks, where agents have incomplete information of the topology, (2) we define a new solution concept for this model, and (3) we identify necessary and sufficient conditions for enforcing accountability, i.e., for persuading agents to exchange messages in the aforementioned model. Our results are of technical interest but also of practical relevance. We show that we cannot enforce accountability if the dynamic network does not allow for \emph{timely punishments}. In practice, this means for instance that we cannot enforce accountability in some networks formed in file-sharing applications such as Bittorrent\,\cite{Cohen:03}. We also show that for applications such as secret exchange, where the benefits of the exchanges significantly surpass the communication costs, timely punishments are enough to enforce accountability. However, we cannot in general enforce accountability if agents do not possess enough information about the network topology. Nevertheless, we can enforce accountability in a wide variety of networks that satisfy 1-connectivity\,\cite{Kuhn:10} with minimal knowledge about the network topology, including overlays for gossip dissemination such as \cite{Li:06,Li:08}.

preprint2013arXiv

On the Effectiveness of Punishments in a Repeated Epidemic Dissemination Game

This work uses Game Theory to study the effectiveness of punishments as an incentive for rational nodes to follow an epidemic dissemination protocol. The dissemination process is modeled as an infinite repetition of a stage game. At the end of each stage, a monitoring mechanism informs each player of the actions of other nodes. The effectiveness of a punishing strategy is measured as the range of values for the benefit-to-cost ratio that sustain cooperation. This paper studies both public and private monitoring. Under public monitoring, we show that direct reciprocity is not an effective incentive, whereas full indirect reciprocity provides a nearly optimal effectiveness. Under private monitoring, we identify necessary conditions regarding the topology of the graph in order for punishments to be effective. When punishments are coordinated, full indirect reciprocity is also effective with private monitoring.

preprint2012arXiv

Asynchrony and Collusion in the N-party BAR Transfer Problem

The problem of reliably transferring data from a set of $N_P$ producers to a set of $N_C$ consumers in the BAR model, named N-party BAR Transfer (NBART), is an important building block for volunteer computing systems. An algorithm to solve this problem in synchronous systems, which provides a Nash equilibrium, has been presented in previous work. In this paper, we propose an NBART algorithm for asynchronous systems. Furthermore, we also address the possibility of collusion among the Rational processes. Our game theoretic analysis shows that the proposed algorithm tolerates certain degree of arbitrary collusion, while still fulfilling the NBART properties.