Search

Blockchains, in general, and cryptocurrencies such as Bitcoin, in particular, are realized using distributed systems and hence critically rely on the performance and security of the interconnecting network. The requirements on these networks and their usage, however, can differ significantly from traditional communication networks, with implications on all layers of the protocol stack. This article is motivated by these differences and, in particular, by the observation that many fundamental design aspects of these networks are not well-understood today. To support the networking community to contribute to this emerging application domain, we present a structured overview of the field, from topology and neighbor discovery, over block and transaction propagation, to sharding and off-chain networks, also reviewing existing empirical results from different measurement studies. In particular, for each of these domains, we provide the context, highlighting differences and commonalities with traditional networks, review the state-of-the-art, and identify open research challenges. Our article can hence also be seen as a call-to-arms to improve the foundation on top of which blockchains are built. [ABSTRACT FROM AUTHOR]

Programmable data plane technologies enable the systematic reconfiguration of the low-level processing steps applied to network packets and are key drivers toward realizing the next generation of network services and applications. This survey presents recent trends and issues in the design and implementation of programmable network devices, focusing on prominent abstractions, architectures, algorithms, and applications proposed, debated, and realized over the past years. We elaborate on the trends that led to the emergence of this technology and highlight the most important pointers fromthe literature, casting different taxonomies for the field, and identifying avenues for future research. [ABSTRACT FROM AUTHOR]

Peer-to-peer systems rely on a scalable overlay network that enables efficient routing between its members. Hypercubic topologies facilitate such operations while each node only needs to connect to a small number of other nodes. In contrast to static communication networks, peer-to-peer networks allow nodes to adapt their neighbor set over time in order to react to join and leave events and failures. This article shows how to maintain such networks in a robust manner. Concretely, we present a distributed and self-stabilizing algorithm that constructs a (slightly extended) skip graph, SKIP+, in polylogarithmic time from any given initial state in which the overlay network is still weakly connected. This is an exponential improvement compared to previously known self-stabilizing algorithms for overlay networks. In addition, our algorithm handles individual joins and leaves locally and efficiently. [ABSTRACT FROM AUTHOR]

The maintenance of efficient and robust overlay networks is one of the most fundamental and reoccurring themes in networking. This article presents a survey of state-of-the-art algorithms to design and repair overlay networks in a distributed manner. In particular, we discuss basic algorithmic primitives to preserve connectivity, review algorithms for the fundamental problem of graph linearization, and then survey selfstabilizing algorithms for metric and scalable topologies. We also identify open problems and avenues for future research. [ABSTRACT FROM AUTHOR]

This article studies the design of medium access control (MAC) protocols for wireless networks that are provably robust against arbitrary and unpredictable disruptions (e.g., due to unintentional external interference from co-existing networks or due to jamming). We consider a wireless network consisting of a set of n honest and reliable nodes within transmission (and interference) range of each other, and we model the external disruptions with a powerful adaptive adversary. This adversary may know the protocol and its entire history and can use this knowledge to jam the wireless channel at will at any time. It is allowed to jam a (1 -- effraction of the timesteps, for an arbitrary constant e > 0 unknown to the nodes. The nodes cannot distinguish between the adversarial jamming or a collision of two or more messages that are sent at the same time. We demonstrate, for the first time, that there is a local-control MAC protocol requiring only very limited knowledge about the adversary and the network that achieves a constant (asymptotically optimal) throughput for the nonjammed time periods under any of the aforementioned adversarial strategies. The derived principles are also useful to build robust applications on top of the MAC layer, and we present an exemplary study for leader election, one of the most fundamental tasks in distributed computing. [ABSTRACT FROM AUTHOR]