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.

Edge-computing is one of the most promising techniques to leverage the excess capacity that exists at users' premises. Unfortunately, edge-computing may be vulnerable to free-riding, i.e., to nodes that attempt to benefit from the system without providing any service in return. Traditional approaches model free-riders as rational nodes that strive to maximize a utility and apply Game Theory concepts to devise mechanisms that deny any utility gain to nodes that deviate from the protocol. These mechanisms impose significant overheads. This paper proposes a new approach that avoids these overheads, which applies concepts of evolutionary game theory. We propose to devise lightweight mechanisms targeted for the optimistic setting where nodes adopt one of a small number of behaviours. If a small fraction of nodes follows alternative behaviours, then the lightweight mechanism should limit the utility gain of these nodesto control the increase in the number of these nodes. This allows altruistic nodes to detect their presence in time to switch to more robust mechanisms before the system reaches a state where the lightweight mechanisms can no longer cope with the existing behaviours. We apply this approach in the context of edge-assisted streaming and propose the use of carefully crafted symmetric overlays to support message dissemination in an environment with free-riders and white-washers. The topology maintenance procedures of our overlay encourage nodes to maintain stable symmetric links. Leveraging the topological properties of the resulting symmetric overlay, direct reciprocity mechanisms deny any utility gain to free-riders and white-washers, while limiting the utility gain of small fractions of nodes that adopt more sophisticated behaviours.

We provide a game-theoretic analysis of consensus, assuming that processes are controlled by rational agents and may fail by crashing. We consider agents that care only about consensus: that is, (a) an agent's utility depends only on the consensus value achieved (and not, for example, on the number of messages the agent sends) and (b) agents strictly prefer reaching consensus to not reaching consensus. We show that, under these assumptions, there is no ex post Nash Equilibrium, even with only one failure. Roughly speaking, this means that there must always exist a failure pattern (a description of who fails, when they fail, and which agents they do not send messages to in the round that they fail) and initial preferences for which an agent can gain by deviating. On the other hand, if we assume that there is a distribution π on the failure patterns and initial preferences, then under minimal assumptions on π, there is a Nash equilibrium that tolerates f failures (i.e., π puts probability 1 on there being at most f failures) if f+1 < n (where n is the total number of agents). Moreover, we show that a slight extension of the Nash equilibrium strategy is also a sequential equilibrium (under the same assumptions about the distribution π).

Edge-computing is one of the most promising techniques to leverage the excess capacity that exists at users' premises. Unfortunately, it may be vulnerable to free-riding, i.e., To nodes that attempt to benefit from the infrastructure without providing any service in return. In this short paper we address free-riding in the context of edge-assisted streaming and propose the use of carefully crafted symmetric overlays to support message dissemination and efficient free-rider detection.