BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Stefan Schmid

Stefan Schmid contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Networking and Internet ArchitectureData Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingBiological Physicsphysics.med-phQuantitative MethodsCryptography and SecurityMachine LearningArtificial IntelligenceComputational ComplexityComputer Science and Game TheoryLogic in Computer ScienceMultiagent SystemsPerformanceSoftware EngineeringTissues and Organs

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
40works
0followers
16topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

40 published item(s)

preprint2026arXiv

A Tutorial on Controlling Metasurfaces from the Network Perspective

Metasurfaces have emerged as transformative electromagnetic structures for wireless communications, enabling the real-time control over wave propagation, yielding potential for improved data rates, privacy, energy efficiency and even precise environmental sensing. This tutorial offers a perspective on controlling metasurfaces by treating them as components of a larger networked system. Towards this end, we first review the physical principles of metasurfaces and their various applications, followed by an exploration of manufacturing approaches for creating these structures. Then, aligning with standard network layer concepts, we describe the modeling of metasurfaces as wave routers, enabling us to describe systems of metasurfaces using graph theory. This approach enables the development of a performance objective framework for optimizing these systems, while classes of heuristic and path-finding-driven algorithms are discussed as practical solvers. The paper also examines the integration of metasurfaces with communication systems, by presenting their overall workflow, discussing its relation to ongoing standardization efforts, as well as defining a context for their integration to network simulators, using Omnet++ as a driving example. Finally, the paper explores future directions for research in this field, identifying graph-theoretic, standardization and integration challenges, relating to several networking disciplines including AI-driven applications.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

Complexity of Perfect and Ideal Resilience Verification in Fast Re-Route Networks

To achieve fast recovery from link failures, most modern communication networks feature fully decentralized fast re-routing mechanisms. These re-routing mechanisms rely on pre-installed static re-routing rules at the nodes (the routers), which depend only on local failure information, namely on the failed links incident to the node. Ideally, a network is perfectly resilient: the re-routing rules ensure that packets are always successfully routed to their destinations as long as the source and the destination are still physically connected in the underlying network after the failures. Unfortunately, there are examples where achieving perfect resilience is not possible. Surprisingly, only very little is known about the algorithmic aspect of when and how perfect resilience can be achieved. We investigate the computational complexity of analyzing such local fast re-routing mechanisms. Our main result is a negative one: we show that even checking whether a given set of static re-routing rules ensures perfect resilience is coNP-complete. We also show coNP-completeness of the so-called ideal resilience, a weaker notion of resilience often considered in the literature. Additionally, we investigate other fundamental variations of the problem. In particular, we show that our coNP-completeness proof also applies to scenarios where the re-routing rules have specific patterns (known as skipping in the literature). On the positive side, for scenarios where nodes do not have information about the link from which a packet arrived (the so-called in-port), we present linear-time algorithms for both the verification and synthesis problem for perfect resilience.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

Practical Validity Conditions for Byzantine-Tolerant Federated Learning

Robust aggregation is the core operation in Byzantine-tolerant federated learning. To ensure the quality of aggregation independently of data distribution or attacks, validity conditions are needed. They provide geometric guarantees of where the output of the aggregation must lie. The widespread convex validity requires the output to lie in the convex hull of the honest vectors. Although this guarantee is strong in theory, it is poorly suited to modern federated learning systems, as it has dimension-dependent resilience and excludes many practical aggregation rules. We introduce the minimum enclosing ball (MEB) validity condition for robust aggregation, as well as its multiplicative relaxation, $c$-MEB validity, where $c$ is a constant. We show that exact MEB validity still suffers from limited resilience, while relaxed $c$-MEB validity is achievable if a majority of clients is honest, i.e. $n>2t$. We give an optimal MinMax-MEB rule for the relaxed condition with the bound $c<\sqrt{2}$ and prove explicit relaxed-MEB guarantees for standard aggregators including minimum-diameter averaging, medoid and geometric median. Finally, we relate MEB validity to convex, relaxed-convex and box validity studied in prior literature, thus providing a systematic map of geometric validity conditions for Byzantine-robust aggregation. Our results show that relaxed MEB validity connects validity conditions in distributed computing and Byzantine-tolerant aggregation rules, and offers a practical alternative to convex validity.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

Resilient Byzantine Agreement with Predictions

This paper studies the Byzantine Agreement problem where the nodes have access to a predictor that flags nodes for suspicion of faulty (Byzantine) behavior. We focus on algorithmic resilience -- the maximum number of faulty nodes an algorithm can tolerate -- and present algorithms and impossibility results whose resilience depend on the accuracy of the predictor. As our first main result, we bring a complete characterization of the consistency--robustness trade-offs in both the non-authenticated and authenticated settings: for $n$ nodes and a parameter $α\in [0, 1]$, we present algorithms that tolerate up to $α\cdot n$ faulty nodes when the predictor is correct (consistency), and up to $\frac{1-α}{2} \cdot n - 1$ faulty nodes when the predictor is arbitrarily wrong (robustness); in the authenticated setting the robustness bound improves to $(1-α) \cdot n - 1$. These trade-offs are exactly tight as we show that one additional faulty node renders the problem impossible. Our second main result characterizes smoothness: the rate at which resilience degrades as the predictor becomes less accurate. We show that resilience linearly decreases in the number of wrong predictions as long as that number stays within a constant fraction of $n$. Concretely, in the non-authenticated setting each additional wrong prediction loses one unit of resilience, whereas in the authenticated setting the decline is halved since two wrong predictions are needed to lose one unit of resilience.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

TAPAAL HyperLTL: A Tool for Checking Hyperproperties of Petri Nets

Petri nets are a modeling formalism capable of describing complex distributed systems and there exists a large number of both academic and industrial tools that enable automatic verification of model properties. Typical questions include reachability analysis and model checking against logics like LTL and CTL. However, these logics fall short when describing properties like non-interference and observational determinism that require simultaneous reasoning about multiple traces of the model and can thus only be expressed as hyperproperties. We introduce, to the best of our knowledge, the first HyperLTL model checker for Petri nets. The tool is fully integrated into the verification framework TAPAAL and we describe the semantics of the hyperlogic, present the tool&#39;s architecture and GUI, and evaluate the performance of the HyperLTL verification engine on two benchmarks of problems originating from the computer networking domain.

0 citations0 reviewsNo code linkedOpen access
preprint2024arXiv

Credence: Augmenting Datacenter Switch Buffer Sharing with ML Predictions

Packet buffers in datacenter switches are shared across all the switch ports in order to improve the overall throughput. The trend of shrinking buffer sizes in datacenter switches makes buffer sharing extremely challenging and a critical performance issue. Literature suggests that push-out buffer sharing algorithms have significantly better performance guarantees compared to drop-tail algorithms. Unfortunately, switches are unable to benefit from these algorithms due to lack of support for push-out operations in hardware. Our key observation is that drop-tail buffers can emulate push-out buffers if the future packet arrivals are known ahead of time. This suggests that augmenting drop-tail algorithms with predictions about the future arrivals has the potential to significantly improve performance. This paper is the first research attempt in this direction. We propose Credence, a drop-tail buffer sharing algorithm augmented with machine-learned predictions. Credence can unlock the performance only attainable by push-out algorithms so far. Its performance hinges on the accuracy of predictions. Specifically, Credence achieves near-optimal performance of the best known push-out algorithm LQD (Longest Queue Drop) with perfect predictions, but gracefully degrades to the performance of the simplest drop-tail algorithm Complete Sharing when the prediction error gets arbitrarily worse. Our evaluations show that Credence improves throughput by $1.5$x compared to traditional approaches. In terms of flow completion times, we show that Credence improves upon the state-of-the-art approaches by up to $95\%$ using off-the-shelf machine learning techniques that are also practical in today&#39;s hardware. We believe this work opens several interesting future work opportunities both in systems and theory that we discuss at the end of this paper.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

Dynamic Maintenance of Monotone Dynamic Programs and Applications

Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However, many DP algorithms have to fill in large DP tables, represented by two-dimensional arrays, which causes at least quadratic running times and space usages. This has led to the development of improved algorithms for special cases when the DPs satisfy additional properties like, e.g., the Monge property or total monotonicity. In this paper, we consider a new condition which assumes (among some other technical assumptions) that the rows of the DP table are monotone. Under this assumption, we introduce a novel data structure for computing $(1+\varepsilon)$-approximate DP solutions in near-linear time and space in the static setting, and with polylogarithmic update times when the DP entries change dynamically. To the best of our knowledge, our new condition is incomparable to previous conditions and is the first which allows to derive dynamic algorithms based on existing DPs. Instead of using two-dimensional arrays to store the DP tables, we store the rows of the DP tables using monotone piecewise constant functions. This allows us to store length-$n$ DP table rows with entries in $[0,W]$ using only polylog$(n,W)$ bits, and to perform operations, such as $(\min,+)$-convolution or rounding, on these functions in polylogarithmic time. We further present several applications of our data structure. For bicriteria versions of $k$-balanced graph partitioning and simultaneous source location, we obtain the first dynamic algorithms with subpolynomial update times, as well as the first static algorithms using only near-linear time and space. Additionally, we obtain the currently fastest algorithm for fully dynamic knapsack.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

SeedTree: A Dynamically Optimal and Local Self-Adjusting Tree

We consider the fundamental problem of designing a self-adjusting tree, which efficiently and locally adapts itself towards the demand it serves (namely accesses to the items stored by the tree nodes), striking a balance between the benefits of such adjustments (enabling faster access) and their costs (reconfigurations). This problem finds applications, among others, in the context of emerging demand-aware and reconfigurable datacenter networks and features connections to self-adjusting data structures. Our main contribution is SeedTree, a dynamically optimal self-adjusting tree which supports local (i.e., greedy) routing, which is particularly attractive under highly dynamic demands. SeedTree relies on an innovative approach which defines a set of unique paths based on randomized item addresses, and uses a small constant number of items per node. We complement our analytical results by showing the benefits of SeedTree empirically, evaluating it on various synthetic and real-world communication traces.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A Centrality Analysis of the Lightning Network

Payment channel networks (PCNs) such as the Lightning Network offer an appealing solution to the scalability problem faced by many cryptocurrencies operating on a blockchain such as Bitcoin. However, PCNs also inherit the stringent dependability requirements of blockchain. In particular, in order to mitigate liquidity bottlenecks as well as on-path attacks, it is important that payment channel networks maintain a high degree of decentralization. Motivated by this requirement, we conduct an empirical centrality analysis of the popular Lightning Network, and in particular, the betweenness centrality distribution of the routing system. Based on our extensive data set (using several millions of channel update messages), we implemented a TimeMachine tool which enables us to study the network evolution over time. We find that although the network is generally fairly decentralized, a small number of nodes can attract a significant fraction of the transactions, introducing skew. Furthermore, our analysis suggests that over the last two years, the centrality has increased significantly, e.g., the inequality (measured by the Gini index) has increased by more than 10%.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Deterministic Self-Adjusting Tree Networks Using Rotor Walks

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 fixed balanced binary tree T connecting n nodes V = {v_1, ... , v_n}. A source node v_0, 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. recently presented Random-Push, a constant competitive online algorithm for this problem, based on random walks, together with an analysis exploiting the most recently used (MRU) property of random walks. We study analytically and empirically, online algorithms for this problem. In particular, we explore how to derandomize Random-Push. We consider a simple derandomized algorithm which we call Rotor-Push, as its behavior is reminiscent of rotor walks. We first prove 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. In contrast to Random-Push, the algorithm does not feature the MRU property, which requires a new analysis. We present a significantly improved and simpler analysis for the randomized algorithm, showing that it is 16-competitive. We compare empirically all self-adjusting single-source tree networks, using synthetic and real data with varying locality and observe that Rotor-Push and Random-Push have almost identical performance.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Fast and Heavy Disjoint Weighted Matchings for Demand-Aware Datacenter Topologies

Reconfigurable optical topologies promise to improve the performance in datacenters by dynamically optimizing the physical network in a demand-aware manner. State-of-the-art optical technologies allow to establish and update direct connectivity (in the form of edge-disjoint matchings) between top-of-rack switches within microseconds or less. However, to fully exploit temporal structure in the demand, such fine-grained reconfigurations also require fast algorithms for optimizing the interconnecting matchings. Motivated by the desire to offload a maximum amount of demand to the reconfigurable network, this paper initiates the study of fast algorithms to find k disjoint heavy matchings in graphs. We present and analyze six algorithms, based on iterative matchings, b-matching, edge coloring, and node-rankings. We show that the problem is generally NP-hard and study the achievable approximation ratios. An extensive empirical evaluation of our algorithms on both real-world and synthetic traces (88 in total), including traces collected in Facebook datacenters and in HPC clusters reveals that all our algorithms provide high-quality matchings, and also very fast ones come within 95% or more of the best solution. However, the running times differ significantly and what is the best algorithm depends on k and the acceptable runtime-quality tradeoff.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Improved Throughput for All-or-Nothing Multicommodity Flows with Arbitrary Demands

Throughput is a main performance objective in communication networks. This paper considers a fundamental maximum throughput routing problem -- the all-or-nothing multicommodity flow (ANF) problem -- in arbitrary directed graphs and in the practically relevant but challenging setting where demands can be (much) larger than the edge capacities. Hence, in addition to assigning requests to valid flows for each routed commodity, an admission control mechanism is required which prevents overloading the network when routing commodities. We make several contributions. On the theoretical side we obtain substantially improved bi-criteria approximation algorithms for this NP-hard problem. We present two non-trivial linear programming relaxations and show how to convert their fractional solutions into integer solutions via randomized rounding. One is an exponential-size formulation (solvable in polynomial time using a separation oracle) that considers a &#34;packing&#34; view and allows a more flexible approach, while the other is a compact (polynomial-size) edge-flow formulation that allows for easy solving via standard LP solvers. We obtain a polynomial-time randomized algorithm that yields an arbitrarily good approximation on the weighted throughput, while violating the edge capacity constraints by only a small multiplicative factor. We also describe a deterministic rounding algorithm by derandomization, using the method of pessimistic estimators. We complement our theoretical results with a proof of concept empirical evaluation.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Kevin: de Bruijn-based topology with demand-aware links and greedy routing

We propose Kevin, a novel demand-aware reconfigurable rack-to-rack datacenter network realized with a simple and efficient control plane. In particular, Kevin makes effective use of the network capacity by supporting integrated and multi-hop routing as well as work-conserving scheduling. To this end, Kevin relies on local greedy routing with small forwarding tables which require local updates only during topological reconfigurations, making this approach ideal for dynamic networks. Specifically, Kevin is based on a de Bruijn topology (using a small number of optical circuit switches) in which static links are enhanced with opportunistic links.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Model-Based Insights on the Performance, Fairness, and Stability of BBR

Google&#39;s BBR is the most prominent result of the recently revived quest for efficient, fair, and flexible congestion-control algorithms (CCAs). While the performance of BBR has been investigated by numerous studies, previous work still leaves gaps in the understanding of BBR performance: Experiment-based studies generally only consider network settings that researchers can set up with manageable effort, and model-based studies neglect important issues like convergence. To complement previous BBR analyses, this paper presents a fluid model of BBRv1 and BBRv2, allowing both efficient simulation under a wide variety of network settings and analytical treatment such as stability analysis. By experimental validation, we show that our fluid model provides highly accurate predictions of BBR behavior. Through extensive simulations and theoretical analysis, we arrive at several insights into both BBR versions, including a previously unknown bufferbloat issue in BBRv2.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the Price of Locality in Static Fast Rerouting

Modern communication networks feature fully decentralized flow rerouting mechanisms which allow them to quickly react to link failures. This paper revisits the fundamental algorithmic problem underlying such local fast rerouting mechanisms. Is it possible to achieve perfect resilience, i.e., to define local routing tables which preserve connectivity as long as the underlying network is still connected? Feigenbaum et al. (ACM PODC&#39;12) and Foerster et al. (SIAM APOCS&#39;21) showed that, unfortunately, it is impossible in general. This paper charts a more complete landscape of the feasibility of perfect resilience. We first show a perhaps surprisingly large price of locality in static fast rerouting mechanisms: even when source and destination remain connected by a linear number of link-disjoint paths after link failures, local rerouting algorithms cannot find any of them which leads to a disconnection on the routing level. This motivates us to study resilience in graphs which exclude certain dense minors, such as cliques or a complete bipartite graphs, and in particular, provide characterizations of the possibility of perfect resilience in different routing models. We provide further insights into the price of locality by showing impossibility results for few failures and investigate perfect resilience on Topology Zoo networks.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

P4RROT: Generating P4 Code for the Application Layer

Throughput and latency critical applications could often benefit of performing computations close to the client. To enable this, distributed computing paradigms such as edge computing have recently emerged. However, with the advent of programmable data planes, computations cannot only be performed by servers but they can be offloaded to network switches. Languages like P4 enable to flexibly reprogram the entire packet processing pipeline. Though these devices promise high throughput and ultra-low response times, implementing application-layer tasks in the data plane programming language P4 is still challenging for an application developer who is not familiar with networking domain. In this paper, we first identify and examine obstacles and pain points one can experience when offloading server-based computations to the network. Then we present P4RROT, a code generator (in form of a library) which allows to overcome these limitations by providing a user-friendly API to describe computations to be offloaded. After discussing the design choices behind P4RROT, we introduce our proof-of-concept implementation for two P4 targets: Netronome SmartNIC and BMv2.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Renaissance: A Self-Stabilizing Distributed SDN Control Plane using In-band Communications

By introducing programmability, automated verification, and innovative debugging tools, Software-Defined Networks (SDNs) are poised to meet the increasingly stringent dependability requirements of today&#39;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 tolerate a wide range of failures. Our self-stabilizing algorithms ensure that after the occurrence of arbitrary failures, (i) every non-faulty SDN controller can reach any switch (or another controller) within a bounded communication delay (in the presence of a bounded number of failures) and (ii) every switch is managed by a controller. We evaluate Renaissance through a rigorous worst-case analysis as well as a prototype implementation (based on OVS and Floodlight, and Mininet).

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sinkless Orientation Made Simple

The sinkless orientation problem plays a key role in understanding the foundations of distributed computing. The problem can be used to separate two fundamental models of distributed graph algorithms, LOCAL and SLOCAL: the locality of sinkless orientation is $Ω(\log n)$ in the deterministic LOCAL model and $O(\log \log n)$ in the deterministic SLOCAL model. Both of these results are known by prior work, but here we give new simple, self-contained proofs for them.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Time Complexity of Consensus in Dynamic Networks Under Oblivious Message Adversaries

Consensus is a most fundamental task in distributed computing. This paper studies the consensus problem for a set of processes connected by a dynamic directed network, in which computation and communication is lock-step synchronous but controlled by an oblivious message adversary. In this basic model, determining consensus solvability and designing consensus algorithms in the case where it is possible, has been shown to be surprisingly difficult. We present an explicit decision procedure to determine if consensus is possible under a given adversary. This in turn enables us, for the first time, to study the time complexity of consensus in this model. In particular, we derive time complexity upper bounds for consensus solvability both for a centralized decision procedure as well as for solving distributed consensus. We complement these results with time complexity lower bounds. Intriguingly, we find that reaching consensus under an oblivious message adversary can take exponentially longer than broadcasting the input value of some process to all other processes.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Weighted Packet Selection for Rechargeable Links: Complexity and Approximation

We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link $(u,v)$ is determined by how much players $u$ and $v$ allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given $(u, v)$ and a packet of weight $x$ going from $u$ to $v$, player $u$ can either accept or reject the packet. If player $u$ accepts the packet, their capacity on link $(u,v)$ decreases by $x$. Correspondingly, player $v$ capacity on $(u,v)$ increases by $x$. If a player rejects the packet, this will entail a cost linear in the weight of the packet. A link is &#34;rechargeable&#34; in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on players&#39; decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show the problem is NP-hard, but can be approximated efficiently with a ratio of $(1+ \varepsilon)\cdot (1+\sqrt{3})$ for some arbitrary $\varepsilon >0$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Wiser: Increasing Throughput in Payment Channel Networks with Transaction Aggregation

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. In this work, we alleviate this limitation by introducing the notion of transaction aggregation: instead of executing transactions sequentially through a PCN, we enable senders to aggregate multiple transactions and execute them simultaneously to benefit from several amounts that may &#34;cancel out&#34;. Two direct advantages of our proposal is the decrease in intermediary fees paid by senders as well as the obfuscation of the transaction data from the intermediaries. We formulate the transaction aggregation as a computational problem, a generalization of the Bank Clearing Problem. We present a generic framework for the transaction aggregation execution, and thereafter we propose Wiser as an implementation of this framework in a specific hub-based setting. To overcome the NP-hardness of the transaction aggregation problem, in Wiser we propose a fixed-parameter linear algorithm for a special case of transaction aggregation as well as the Bank Clearing Problem. Wiser can also be seen as a modern variant of the Hawala money transfer system, as well as a decentralized implementation of the overseas remittance service of Wise.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Between-session reliability of skin marker-derived spinal kinematics during functional activities

Background: Skin marker-based analysis of functional spinal movement is a promising method for quantifying longitudinal effects of treatment interventions in patients with spinal pathologies. However, observed day-to-day changes might not necessarily be due to a treatment intervention, but can result from errors related to soft tissue artifacts, marker placement inaccuracies or biological day-to-day variability. Research question: How reliable are skin marker-derived three-dimensional spinal kinematics during functional activities between two separate measurement sessions? Methods: Twenty healthy adults (11f/9m) were invited to a movement analysis laboratory for two visits separated by 7-10 days. At each visit, they performed various functional activities (i.e. sitting, standing, walking, running, chair rising, box lifting and vertical jumping), while marker trajectories were recorded using a skin marker-based 10-camera optical motion capture system and used to calculate sagittal and frontal plane spinal curvature angles as well as transverse plane segmental rotational angles in the lumbar and thoracic regions. Between-session reliability for continuous data and discrete parameters was determined by analyzing systematic errors using one sample T-tests as well as by calculating intraclass correlation coefficients (ICCs) and minimal detectable changes (MDCs). Results and Significance: The analysis indicated high relative consistency for sagittal plane curvature angles during all activities, but not for frontal and transverse plane angles during walking and running. MDCs were mostly below 15°, with relative values ranging between 10% and 750%. This study provides important information that can serve as a basis for researchers and clinicians aiming at investigating longitudinal effects of treatment interventions on spinal motion behavior in patients with spinal pathologies.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

From Stoop to Squat: A comprehensive analysis of lumbar loading among different lifting styles

Lifting up objects from the floor has been identified as a risk factor for low back pain, whereby a flexed spine during lifting is often associated with producing higher loads in the lumbar spine. Even though recent biomechanical studies challenge these assumptions, conclusive evidence is still lacking. This study therefore aimed at comparing lumbar loads among different lifting styles using a comprehensive state-of-the-art motion capture-driven musculoskeletal modeling approach. Thirty healthy pain-free individuals were enrolled in this study and asked to repetitively lift a 15 kg-box by applying 1) a freestyle, 2) a squat and 3) a stoop lifting technique. Whole-body kinematics were recorded using an optical motion capture system and used to drive a full-body musculoskeletal model including a detailed thoracolumbar spine. Compressive, shear and total loads were calculated based on a static optimization approach and expressed as factor body weight (BW). In addition, lumbar lordosis angles and total lifting time were calculated. All parameters were compared among the lifting styles using a repeated measures design. For all lumbar segments, stoop lifting showed significantly lower compressive and total loads (-0.3 to -1.0BW) when compared to freestyle and squat lifting. Stoop lifting produced higher shear loads (+0.1 to +0.8BW) in the segments T12/L1 to L4/L5, but lower loads in L5/S1 (-0.2 to -0.4BW). Peak compressive and total loads during squat lifting occurred approximately 30% earlier in the lifting cycle compared to stoop lifting. Stoop lifting showed larger lumbar lordosis range of motion (35.9+/-10.1°) than freestyle (24.2+/-7.3°) and squat (25.1+/-8.2°) lifting. Lifting time differed significantly with freestyle being executed the fastest (4.6+/-0.7s), followed by squat (4.9+/-0.7s) and stoop (5.9+/-1.1s).

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Input-Dynamic Distributed Algorithms for Communication Networks

Consider a distributed task where the communication network is fixed but the local inputs given to the nodes of the distributed system may change over time. In this work, we explore the following question: if some of the local inputs change, can an existing solution be updated efficiently, in a dynamic and distributed manner? To address this question, we define the batch dynamic CONGEST model in which we are given a bandwidth-limited communication network and a dynamic edge labelling defines the problem input. The task is to maintain a solution to a graph problem on the labeled graph under batch changes. We investigate, when a batch of $α$ edge label changes arrive, -- how much time as a function of $α$ we need to update an existing solution, and -- how much information the nodes have to keep in local memory between batches in order to update the solution quickly. Our work lays the foundations for the theory of input-dynamic distributed network algorithms. We give a general picture of the complexity landscape in this model, design both universal algorithms and algorithms for concrete problems, and present a general framework for lower bounds. In particular, we derive non-trivial upper bounds for two selected, contrasting problems: maintaining a minimum spanning tree and detecting cliques.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Skin marker-based subject-specific spinal alignment modeling: A feasibility study

Musculoskeletal models have the potential to improve diagnosis and optimize clinical treatment by predicting accurate outcomes on an individual basis. However, the subject-specific modeling of spinal alignment is often strongly simplified or is based on radiographic assessments, exposing subjects to unnecessary radiation. We therefore developed a novel skin marker-based approach for modeling subject-specific spinal alignment and evaluated its feasibility by comparing the predicted with the actual intervertebral joint (IVJ) locations/orientations (ground truth) using lateral-view radiographic images. Moreover, the predictive performance of the subject-specific models was evaluated by comparing the predicted L1/L2 spinal loads during various functional activities with in vivo measured data obtained from the OrthoLoad database. IVJ locations/orientations were predicted closer to ground truth as opposed to standard model scaling, with average location prediction errors of 0.99+/-0.68 cm on the frontal and 1.21+/-0.97 cm on the transverse axis as well as an average orientation prediction error of 4.74°+/-2.80°. Simulated spinal loads showed similar curve patterns but considerably larger values as compared to in vivo measured data. Differences in spinal loads between generic and subject-specific models become only apparent on an individual subject level. These results underline the feasibility of the proposed method and associated workflow for inter- and intra-subject investigations using musculoskeletal simulations. When implemented into standard model scaling workflows, it is expected to improve the accuracy of muscle activity and joint loading simulations, which is crucial for investigations of treatment effects or pathology-dependent deviations.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

The Stoop-Squat-Index: a simple but powerful measure for quantifying lifting behavior

The widely held belief that squat lifting should be preferred over stoop lifting to prevent back injury is increasingly being challenged by recent biomechanical evidence. However, most of these studies only focus on very localized parameters such as lumbar spine flexion, while evaluations of whole-body lifting strategies are largely lacking. For this reason, a novel index, the Stoop-Squat-Index, was developed, which describes the proportion between trunk forward lean and lower extremity joint flexion, with possible values ranging from 0 (full squat lifting) to 100 (full stoop lifting). To enable the interpretation of the index in a real-life setting, normative values were established using motion capture data from 30 healthy pain-free individuals that were collected in the context of a previous study. The results showed mean index values of lower than 30 and higher than 90 for the most relevant phases of the squat and stoop movements, respectively, with mean index values differing significantly from each other for the full duration of the lifting phases. The main advantages of the index are that it is simple to calculate and can not only be derived from motion capture data but also from conventional video recordings, which enables large-scale in-field measurements with relatively low expenditure. When used in combination with lumbar spine flexion measurements, the index can contribute important information, which is necessary for comprehensively evaluating whole-body lifting strategies and to shed more light on the debate over the connection between lifting posture and back complaints.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Conic Formation in Presence of Faulty Robots

Pattern formation is one of the most fundamental problems in distributed computing, which has recently received much attention. In this paper, we initiate the study of distributed pattern formation in situations when some robots can be \textit{faulty}. In particular, we consider the well-established \textit{look-compute-move} model with oblivious, anonymous robots. We first present lower bounds and show that any deterministic algorithm takes at least two rounds to form simple patterns in the presence of faulty robots. We then present distributed algorithms for our problem which match this bound, \textit{for conic sections}: in at most two rounds, robots form lines, circles and parabola tolerating $f=2,3$ and $4$ faults, respectively. For $f=5$, the target patterns are parabola, hyperbola and ellipse. We show that the resulting pattern includes the $f$ faulty robots in the pattern of $n$ robots, where $n \geq 2f+1$, and that $f < n < 2f+1$ robots cannot form such patterns. We conclude by discussing several relaxations and extensions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Dynamic Balanced Graph Partitioning

This paper initiates the study of the classic balanced graph partitioning problem from an online perspective: Given an arbitrary sequence of pairwise communication requests between $n$ nodes, with patterns that may change over time, the objective is to service these requests efficiently by partitioning the nodes into $\ell$ clusters, each of size $k$, such that frequently communicating nodes are located in the same cluster. The partitioning can be updated dynamically by migrating nodes between clusters. The goal is to devise online algorithms which jointly minimize the amount of inter-cluster communication and migration cost. The problem features interesting connections to other well-known online problems. For example, scenarios with $\ell=2$ generalize online paging, and scenarios with $k=2$ constitute a novel online variant of maximum matching. We present several lower bounds and algorithms for settings both with and without cluster-size augmentation. In particular, we prove that any deterministic online algorithm has a competitive ratio of at least $k$, even with significant augmentation. Our main algorithmic contributions are an $O(k \log{k})$-competitive deterministic algorithm for the general setting with constant augmentation, and a constant competitive algorithm for the maximum matching variant.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Measuring lumbar back motion during functional activities using a portable strain gauge sensor-based system: a comparative evaluation and reliability study

Quantifying lumbar back motion during functional activities in real-life environments may contribute to a better understanding of common pathologies such as spinal disorders. The current study therefore aimed at the comparative evaluation of the Epionics SPINE system, a portable device for measuring sagittal lumbar back motion during functional activities. Twenty healthy participants were therefore evaluated with the Epionics SPINE and a Vicon motion capture system in two identical separate research visits. They performed the following activities: standing, sitting, chair rising, box lifting, walking, running and a counter movement jump (CMJ). Lumbar lordosis angles were extracted as continuous values as well as average and range of motion (ROM) parameters. Agreement between the systems was evaluated using Bland-Altman analyses, whereas within- and between-session reliability were assessed using intraclass correlation coefficients (ICC) and minimal detectable changes (MDC). The analysis showed excellent agreement between the systems for chair rising, box lifting and CMJ with a systematic underestimation of lumbar lordosis angles during walking and running. Reliability was moderate to high for all continuous and discrete parameters (ICC>=0.62), except for ROM during running (ICC=0.29). MDC values were generally below 15°, except for CMJ (peak values up to 20° within and 25° between the sessions). The Epionics SPINE system performed similarly to a Vicon motion capture system for measuring lumbar lordosis angles during functional activities and showed high consistency within and between measurement sessions. These findings can serve researchers and clinicians as a bench mark for future investigations using the system in populations with spinal pathologies.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Musculoskeletal full-body models including a detailed thoracolumbar spine for children and adolescents aged 6-18 years

Currently available musculoskeletal inverse-dynamics thoracolumbar spine models are entirely based on data from adults and might therefore not be applicable for simulations in children and adolescents. In addition, these models lack lower extremities, which are required for comprehensive evaluations of functional activities or therapeutic exercises. We therefore created OpenSim-based musculoskeletal full-body models including a detailed thoracolumbar spine for children and adolescents aged 6-18 years and validated by comparing model predictions to in vivo data. After combining our recently developed adult thoracolumbar spine model with a lower extremity model, children and adolescent models were created for each year of age by adjusting segmental length and mass distribution, center of mass positions and moments of inertia of the major body segments as well as sagittal pelvis and spine alignment based on literature data. Similarly, muscle strength properties were adjusted based on CT-derived cross-sectional area measurements. Simulations were conducted from in vivo studies reported in the literature involving children and adolescents evaluating maximum trunk muscle strength (MTMS), lumbar disc compressibility (LDC), intradiscal pressure (IDP) and trunk muscle activity (MA). Model predictions correlated highly with in vivo data (MTMS: r>=0.82, p<=0.03; LDC: r=0.77, p<0.001; IDP: r>=0.78, p<0.001; MA: r>=0.90, p<0.001), indicating suitability for the reasonably accurate prediction of maximal trunk muscle strength, segmental loading and trunk muscle activity in children and adolescents. When aiming at investigating children or adolescents with pathologies such as idiopathic scoliosis, our models can serve as a basis for the creation of deformed spine models and for comparative purposes.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Search Friction of Route Discovery in Offchain Networks

Offchain networks provide a promising solution to overcome the scalability challenges of cryptocurrencies. However, design tradeoffs of offchain networks are still not well-understood today. In particular, offchain networks typically rely on fees-based incentives and hence require mechanisms for the efficient discovery of ``good routes&#39;&#39;: routes with low fees (cost efficiency) and a high success rate of the transaction routing (effectiveness). Furthermore, the route discovery should be confidential (privacy), and e.g., not reveal information about who transacts with whom or about the transaction value. This paper provides an analysis of the ``search friction&#39;&#39; of route discovery, i.e., the costs and tradeoffs of route discovery in large-scale offchain networks in which nodes behave strategically. As a case study, we consider the Lighning network and the route discovery service provided by the trampoline nodes, evaluating the tradeoff in different scenarios also empirically. Finally, we initiate the discussion of alternative charging schemes for offchain networks.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Push-Down Trees: Optimal Self-Adjusting Complete Trees

This paper studies a fundamental algorithmic problem related to the design of demand-aware networks: networks whose topologies adjust toward the traffic patterns they serve, in an online manner. The goal is to strike a tradeoff between the benefits of such adjustments (shorter routes) and their costs (reconfigurations). In particular, we consider the problem of designing a self-adjusting tree network which serves single-source, multi-destination communication. The problem has interesting connections to self-adjusting datastructures. We present two constant-competitive online algorithms for this problem, one randomized and one deterministic. Our approach is based on a natural notion of Most Recently Used (MRU) tree, maintaining a working set. We prove that the working set is a cost lower bound for any online algorithm, and then present a randomized algorithm RANDOM-PUSH which approximates such an MRU tree at low cost, by pushing less recently used communication partners down the tree, along a random walk. Our deterministic algorithm MOVE-HALF does not directly maintain an MRU tree, but its cost is still proportional to the cost of an MRU tree, and also matches the working set lower bound.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Spinal Compressive Forces in Adolescent Idiopathic Scoliosis With and Without Carrying Loads: A Musculoskeletal Modeling Study

The pathogenesis of adolescent idiopathic scoliosis (AIS) remains poorly understood and biomechanical data are limited. A deeper insight into spinal loading could provide valuable information for the improvement of current treatment strategies. This work therefore aimed at using subject-specific musculoskeletal full-body models of patients with AIS to predict segmental compressive forces around the curve apex and to investigate how these forces are affected by simulated load carrying. Models were created based on spatially calibrated biplanar radiographic images from 24 patients with mild to moderate AIS and validated by comparing predictions of paravertebral muscle activity with reported values from in vivo studies. Spinal compressive forces were predicted during unloaded upright standing as well as upright standing with external loads of 10%, 15% and 20% of body weight (BW) applied to the scapulae to simulate carrying a backpack in the regular way, in front of the body and over both shoulders. The validation studies showed higher convex muscle activity, which was comparable to the literature. The implementation of spinal deformity resulted in a 10% increase of compressive force at the curve apex during unloaded upright standing. Apical compressive forces further increased by 50-62%, 77-94% and 103-128% for 10%, 15% and 20% BW loads, respectively. Moreover, load-dependent compressive force increases were the lowest in the regular backpack and the highest in the frontpack and convex conditions. The predictions indicated increased segmental compressive forces during unloaded standing, which could be ascribed to the scoliotic deformation. When carrying loads, compressive forces further increased depending on the carrying mode and the weight of the load. These results can be used as a basis for further studies investigating segmental loading in AIS patients during functional activities.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Survey on Cryptocurrency Networking: Context, State-of-the-Art, Challenges

Cryptocurrencies such as Bitcoin 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 paper is motivated by these differences, and in particular by the observation that many fundamental design aspects of these networks are not well-understood today. In order 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 to block and transaction propagation. In particular, we provide the context, highlighting differences and commonalities with traditional networks, review the state-of-the-art, and identify open research challenges. Our paper can hence also be seen as a call-to-arms to improve the foundation on top of which cryptocurrencies are built.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Value of Information in Selfish Routing

Path selection by selfish agents has traditionally been studied by comparing social optima and equilibria in the Wardrop model, i.e., by investigating the Price of Anarchy in selfish routing. In this work, we refine and extend the traditional selfish-routing model in order to answer questions that arise in emerging path-aware Internet architectures. The model enables us to characterize the impact of different degrees of congestion information that users possess. Furthermore, it allows us to analytically quantify the impact of selfish routing, not only on users, but also on network operators. Based on our model, we show that the cost of selfish routing depends on the network topology, the perspective (users versus network operators), and the information that users have. Surprisingly, we show analytically and empirically that less information tends to lower the Price of Anarchy, almost to the optimum. Our results hence suggest that selfish routing has modest social cost even without the dissemination of path-load information.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Toward Active and Passive Confidentiality Attacks On Cryptocurrency Off-Chain Networks

Cryptocurrency off-chain networks such as Lightning (e.g., Bitcoin) or Raiden (e.g., Ethereum) aim to increase the scalability of traditional on-chain transactions. To support nodes in learning about possible paths to route their transactions, these networks need to provide gossip and probing mechanisms. This paper explores whether these mechanisms may be exploited to infer sensitive information about the flow of transactions, and eventually harm privacy. In particular, we identify two threats, related to an active and a passive adversary. The first is a probing attack: here the adversary aims to detect the maximum amount which is transferable in a given direction over a target channel by actively probing it and differentiating the response messages it receives. The second is a timing attack: the adversary discovers how close the destination of a routed payment actually is, by acting as a passive man-in-the middle and analyzing the time deltas between sent messages and their corresponding responses. We then analyze the limitations of these attacks and propose remediations for scenarios in which they are able to produce accurate results.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Towards Fine-Grained Billing For Cloud Networking

We revisit multi-tenant network virtualization in data centers, and make the case for tenant-specific virtual switches. In particular, tenant-specific virtual switches allow cloud providers to extend fine-grained billing (known, e.g., from serverless architectures) to the network, accounting not only for IO, but also CPU or energy. We sketch an architecture and present economical motivation and recent technological enablers. We also find that virtual switches today do not offer sufficient multi-tenancy and can introduce artificial performance bottlenecks, e.g., in load balancers. We conclude by discussing additional use cases for tentant-specific switches.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Towards Runtime Verification of Programmable Switches

Is it possible to patch software bugs in P4 programs without human involvement? We show that this is partially possible in many cases due to advances in software testing and the structure of P4 programs. Our insight is that runtime verification can detect bugs, even those that are not detected at compile-time, with machine learning-guided fuzzing. This enables a more automated and real-time localization of bugs in P4 programs using software testing techniques like Tarantula. Once the bug in a P4 program is localized, the faulty code can be patched due to the programmable nature of P4. In addition, platform-dependent bugs can be detected. From P4_14 to P4_16 (latest version), our observation is that as the programmable blocks increase, the patchability of P4 programs increases accordingly. To this end, we design, develop, and evaluate P6 that (a) detects, (b) localizes, and (c) patches bugs in P4 programs with minimal human interaction. P6 tests P4 switch non-intrusively, i.e., requires no modification to the P4 program for detecting and localizing bugs. We used a P6 prototype to detect and patch seven existing bugs in eight publicly available P4 application programs deployed on two different switch platforms: behavioral model (bmv2) and Tofino. Our evaluation shows that P6 significantly outperforms bug detection baselines while generating fewer packets and patches bugs in P4 programs such as switch.p4 without triggering any regressions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Walking and running with non-specific chronic low back pain: what about the lumbar lordosis angle?

Non-specific chronic low back pain (NSCLBP) is a major health problem, affecting about one fifth of the population worldwide. To avoid further pain or injury, patients with NSCLBP seem to adopt a stiffer movement pattern during everyday living activities. However, it remains unknown how NSCLBP affects the lumbar lordosis angle (LLA) during repetitive activities such as walking or running. This pilot study therefore aimed at exploring possible NSCLBP-related alterations in LLAs during walking and running by focusing on discrete parameters as well as continuous data. Thirteen patients with NSCLBP and 20 healthy pain-free controls were enrolled and underwent a full-body movement analysis involving various everyday living activities such as standing, walking and running. LLAs were derived from markers placed on the spinous processes of the vertebrae L1-L5 and S1. Possible group differences in discrete (average and range of motion (ROM)) and continuous LLAs were analyzed descriptively using mean differences with confidence intervals ranging from 95% to 75%. Patients with NSCLBP indicated reduced average LLAs during standing, walking and running and a tendency for lower LLA-ROM during walking. Analyses of continuous data indicated the largest group differences occurring around 25% and 70% of the walking and 25% and 75% of the running cycle. Furthermore, patients indicated a reversed movement pattern during running, with increasing instead of a decreasing LLAs after foot strike. This study provides preliminary evidence that NSCLBP might affect LLAs during walking and running. These results can be used as a basis for future large-scale investigations involving hypothesis testing.

0 citations0 reviewsNo code linkedOpen access