Abstract Vector clock algorithms are fundamental wait-free building blocks that enable the causal ordering of events. As wait-free algorithms, they are designed to complete their operations within a finite number of steps. Stabilizing algorithms aid the system in recovering after the occurrence of transient faults, such as soft errors and arbitrary violations of the assumptions according to which the system was designed to behave. To the best of our knowledge, this paper introduces the first stabilizing vector clock algorithm for asynchronous crash-prone message-passing systems that can achieve wait-free recovery after the occurrence of transient faults. In such settings, demonstrating finite and wait-free recovery from transient faults as well as communication and crash failures, bounding the message and storage sizes, handling the removal of stale information without blocking, and addressing concurrent counter overflow events at different network nodes pose significant challenges. We propose an algorithm that ensures safety in the absence of transient faults and offers bounded time recovery during fair executions following the last transient fault. The novelty lies in guaranteeing a bound on the number of safety violations, even in the absence of execution fairness (where existing algorithms may become permanently blocked due to both transient faults and crash failures). Considering the usefulness of vector clocks in facilitating various elementary synchronization building blocks in asynchronous systems without requiring remote replica synchronization, our analytical insights hold promise for designing other systems that cannot guarantee execution fairness.

Payment channel networks (PCNs) are among the most promising solutions to the scalability issues in permissionless blockchains , allowing parties to pay each other off-chain through a path of payment channels (PCs). However, the cost of routing transactions is proportional to the number of intermediaries since each charges a fee. Analogous to other networks, malicious intermediaries on the path can lead to security/privacy threats. Virtual channels (VCs), i.e., bridges over PC paths, mitigate the above PCN issues: Intermediaries participate only in the VC setup but in no future VC payments. However, creating a VC has a cost that must be paid out of the bridged PCs’ balance. Currently, we are missing guidelines on how/where to set up VCs. Ideally, VCs should minimize transaction costs while mitigating security and privacy threats from on-path adversaries. In this work, we address for the first time the VC setup problem, formalizing it as an optimization problem . We present an integer linear program (ILP) computing the globally optimal VC setup strategy in terms of cost, security, and privacy. We accompany this expensive ILP with a fast, greedy algorithm . Our model and algorithms can be used with any on-path adversary whose strategy can be expressed as a set of corrupted nodes. We evaluate the greedy algorithm over a snapshot of the Lightning Network (LN), the largest Bitcoin-based PCN. Our results confirm that the greedy strategy minimizes costs while protecting against security and privacy threats and may serve the LN community as guidelines for VC deployment.

Datacenter networks are becoming increasingly flexible with the incorporation of new optical communication technologies, such as optical circuit switches, enabling self-adjusting topologies that can adapt to the traffic pattern in a demand-aware manner. In this paper, we take the first steps toward demand-aware and self-adjusting k-ary tree networks. These are more powerful generalizations of existing binary search tree networks (like SplayNet [22]), which have been at the core of self-adjusting network (SAN) designs. k-ary search tree networks are a natural generalization offering nodes of higher degrees, reduced route lengths, and local routing in spite of reconfigurations (due to maintaining the search property). Our main results are two online heuristics for self-adjusting k-ary tree networks. Empirical results show that our heuristics work better than SplayNet in most of the real network traces and for average to low locality synthetic traces, and are only a little inferior to SplayNet in all remaining traces. We build our online algorithms by first solving the offline case. First, we compute an offline (optimal) static demand-aware network for arbitrary traffic patterns in O(n3 · k) time via dynamic programming, where n is the number of network nodes (e.g., datacenter racks), and also improve the bound for the special case of uniformly distributed traffic. Then, we present a centroid-based approach to demand-aware network designs that we use both in the offline static and online settings. In the offline uniform-workload case, we construct this centroid network in linear time O(n).

Payment channel networks (PCNs) are one of the most prominent solutions to the limited transaction throughput of blockchains. Nevertheless, PCNs suffer themselves from a throughput limitation due to the capital constraints of their channels. A similar dependence on high capital is also found in inter-bank payment settlements, where the so-called netting technique is used to mitigate liquidity demands.

We revisit the design of self-adjusting single-source tree networks. The problem can be seen as a generalization of the classic list update problem to trees, and finds applications in reconfigurable datacenter networks. We are given a balanced binary tree T connecting n nodes V = {v1,…, vn}. A source node v0, attached to the root of the tree, issues communication requests to nodes in V , in an online and adversarial manner; the access cost of a request to a node v, is given by the current depth of v in T . The online algorithm can try to reduce the access cost by performing swap operations, with which the position of a node is exchanged with the position of its parent in the tree; a swap operation costs one unit. The objective is to design an online algorithm which minimizes the total access cost plus adjustment cost (swapping). Avin et al. [12] (LATIN 2020) recently presented RANDOM-PUSH, a constant competitive online algorithm for this problem, based on random walks, together with a sophisticated analysis exploiting the working set property.This paper studies analytically and empirically, online algorithms for this problem. In particular, we explore how to derandomize RANDOM-PUSH. In the analytical part, we consider a simple derandomized algorithm which we call ROTOR-PUSH, as its behavior is reminiscent of rotor walks. Our first contribution is a proof that ROTOR-PUSH is constant competitive: its competitive ratio is 12 and hence by a factor of five lower than the best existing competitive ratio. Interestingly, in contrast to RANDOM-PUSH, the algorithm does not feature the working set property, which requires a new analysis. We further present a significantly improved and simpler analysis for the randomized algorithm, showing that it is 16-competitive.In the empirical part, we compare all self-adjusting single-source tree networks, using both synthetic and real data. In particular, we shed light on the extent to which these self-adjusting trees can exploit temporal and spatial structure in the workload. Our experimental artefacts and source codes are publicly available.

Self-adjusting networks (SANs) utilize novel optical switching technologies to support dynamic physical network topology reconfiguration. SANs rely on online algorithms to exploit this topological flexibility to reduce the cost of serving network traffic, leveraging locality in the demand. While prior work has shown the potential of SANs, the theoretical guarantees rely on a simplified cost model in which traversing and adjusting a single link has uniform cost.We initiate the study of online algorithms for SANs in a more realistic cost model, the Matching Model (MM), in which the network topology is given by the union of a constant number of bipartite matchings (realized by optical switches), and in which changing an entire matching incurs a fixed cost α. The cost of routing is given by the number of hops packets need to traverse.Our main result is a lazy topology adjustment method for designing efficient online SAN algorithms in the MM. We design and analyze online SAN algorithms for line, tree, and bounded degree networks in the MM, with cost ${\mathcal{O}}(\sqrt \alpha )$ times the cost of reference algorithms in the uniform cost model. We report on empirical results considering publicly available datacenter network traces, that verify the theoretical bounds.

Payment channel networks are a promising approach to improve the scalability of cryptocurrencies: they allow to perform transactions in a peer-to-peer fashion, along multihop routes in the network, without requiring consensus on the blockchain. However, during the discovery of cost-efficient routes for the transaction, critical information may be revealed about the transacting entities. This paper initiates the study of privacy-preserving route discovery mechanisms for payment channel networks. In particular, we present LightPIR, an approach which allows a client to learn the shortest (or cheapest in terms of fees) path between two nodes without revealing any information about the endpoints of the transaction to the servers. The two main observations which allow for an efficient solution in LightPIR are that: (1) surprisingly, hub labelling algorithms - which were developed to preprocess “street network like” graphs so one can later efficiently compute shortest paths - also perform well for the graphs underlying payment channel networks, and that (2) hub labelling algorithms can be conveniently combined with private information retrieval. LightPIR relies on a simple hub labeling heuristic on top of existing hub labeling algorithms which leverages the specific topological features of cryptocurrency networks to further minimize storage and bandwidth overheads. In a case study considering the Lightning network, we show that our approach is an order of magnitude more efficient compared to a privacy-preserving baseline based on using private information retrieval on a database that stores all pairs shortest paths.

Self-adjusting networks (SANs) utilize novel optical switching technologies to support dynamic physical network topology reconfiguration. SANs rely on online algorithms to exploit this topological flexibility to reduce the cost of serving network traffic, leveraging locality in the demand. Models in prior work assign uniform cost for traversing and adjusting a single link (e.g. both cost 1). In this paper, we initiate the study of online algorithms for SANs in a more realistic cost model, the Matching Model (MM), in which the network topology is given by the union of a constant number of bipartite matchings (realized by optical switches), and in which changing an entire matching incurs a fixed cost a. The cost of routing is given by the number of hops packets need to traverse. We present online SAN algorithms in the MM with cost O(√α) times the cost of reference algorithms in the uniform cost model.

This paper explores the design of dynamic network topologies which adjust to the workload they serve, in a demand-aware and online manner. Such self-adjusting networks (SANs) are enabled by emerging optical technologies, and can be found, e.g., in datacenters. SANs can be used to reduce routing costs by moving frequently communicating nodes topologically closer. However, such reconfigurations also come at a cost, introducing a need for online algorithms which strike an optimal balance between the benefits and costs of reconfigurations.This paper presents SANs which provide, for the first time, provable working set guarantees: the routing cost between node pairs is proportional to how recently these nodes communicated last time. Our SANs rely on a distributed implementation of skip lists (which serves as the topology) and provide additional interesting properties such as local routing. Our first contribution is SASL2, which is a randomized and sequential SAN algorithm that achieves the working set property. Then we show how SASL2can be converted to a distributed algorithm that handles concurrent communication requests and maintains SASL2's properties. Finally, we present deterministic SAN algorithms.

This paper explores the design of dynamic network topologies which adjust to the workload they serve, in an online manner. Such self-adjusting networks (SANs) are enabled by emerging optical technologies, and can be found, e.g., in datacenters. SANs can be used to reduce routing costs by moving frequently communicating nodes topologically closer. This paper presents SANs which provide, for the first time, provable working set guarantees: the routing cost between node pairs is proportional to how recently these nodes communicated last time. Our SANs rely on skip lists (which serve as the topology) and provide additional interesting properties such as local routing.

By introducing programmability, automated verification, and innovative debugging tools, Software-Defined Networks (SDNs) are poised to meet the increasingly stringent dependability requirements of today's communication networks. However, the design of fault-tolerant SDNs remains an open challenge. This paper considers the design of dependable SDNs through the lenses of self-stabilization - a very strong notion of fault-tolerance. In particular, we develop algorithms for an in-band and distributed control plane for SDNs, called Renaissance, which tolerates a wide range of (concurrent) controller, link, and communication failures. Our self-stabilizing algorithms ensure that after the occurrence of an arbitrary combination of failures, (i) every non-faulty SDN controller can eventually reach any switch in the network within a bounded communication delay (in the presence of a bounded number of concurrent failures) and (ii) every switch is managed by at least one non-faulty controller. We evaluate Renaissance through a rigorous worst-case analysis as well as a prototype implementation (based on OVS and Floodlight), and we report on our experiments using Mininet.

Adopting distributed control planes is critical towards ensuring high availability and fault-tolerance of dependable Software-Defined Networks (SDNs). However, designing and bootstrapping a distributed SDN control plane is a challenging task, especially if to be done in-band, without a dedicated control network, and without relying on legacy networking protocols. One of the most appealing and powerful notions of fault-tolerance is self-organization and this paper discusses the possibility of self-organizing algorithms for in-band control planes.