Blockchains offer strong security guarantees, but cannot protect users against the ordering of transactions. Players such as miners, bots, and validators can reorder transactions to reap significant profits, called the maximal extractable value (MEV). In this article, we propose an MEV aware protocol design called Masquerade and show that it will increase user rewards in the system by using a strict per-transaction level of ordering to ensure that a transaction is committed either way even if it is revealed. In this protocol, we introduce the notion of a token to mitigate the actions taken by an adversary in an attack scenario. Such tokens can be purchased voluntarily by users, who can then choose to include the token numbers in their transactions. If the users include the token in their transactions, then our protocol requires the block-builder to order the transactions strictly according to token numbers. We show through extensive simulations that this reduces the probability that the adversaries can benefit from MEV transactions as compared to existing practices. We show that successful MEV attacks decrease by about 70% on average.

Popular blockchains today have hundreds of thousands of nodes and need to be able to support sophisticated scaling solutions—such as sharding, data availability sampling, and layer-2 methods. Designing secure and efficient peer-to-peer (p2p) networking protocols at these scales to support the tight demands of the upper layer crypto-economic primitives is a highly non-trivial endeavor. We identify decentralized, uniform random sampling of nodes as a fundamental capability necessary for building robust p2p networks in emerging blockchain networks. Sampling algorithms used in practice today (primarily for address discovery) rely on either distributed hash tables (e.g., Kademlia) or sharing addresses with neighbors (e.g., GossipSub), and are not secure in a Sybil setting. We present Honeybee, a decentralized algorithm for sampling nodes that uses verifiable random walks and table consistency checks. Honeybee is secure against attacks even in the presence of an overwhelming number of Byzantine nodes (e.g., ≥ 50% of the network). We evaluate Honeybee through experiments and show that the quality of sampling achieved by Honeybee is significantly better compared to the state-of-the-art. Our proposed algorithm has implications for network design in both full nodes and light nodes.

Modern biomedical research and clinical workflows are burdened by large quantities of unstructured data. These datasets include imaging files such as radiologic, histologic, or time series videos, as well as transcriptional and genomic datasets. The advent of applied mathematics approaches capable of handling unstructured datasets, collectively referred to as machine learning and artificial intelligence (ML/AI), is enabling an unprecedented advance in biomedical research, with many research groups attempting to extract meaningful data for clinical decision-making. The advent of such in silico biomarkers extracted from unstructured datasets represents an emerging trend in diagnostic medicine carrying significant promise of alleviating patient suffering whilst lowering health care costs. This accumulation of novel quantitative methodologies that enable healthcare professionals comes with significant costs related to the storage of these digital assets. Currently, no healthcare system in the developed world has a clearly articulated public policy framework for financing the storage of these large digital assets. For instance, the digitization of histology images through whole slide imaging creates a significant financial burden for Pathology departments. This financial challenge is also experienced by pre-clinical and clinical research investigators who are also ever expanding their utilization of unstructured datasets for research. The advent of new technologies and workflows to archive research data and clinical data is therefore of utmost importance to biomedical and clinical informaticists. In this editorial, we delineate the needs for biomedical and clinical research storage and discuss the suitability of modern web3/blockchain-based solutions to resolve this problem.

Graph convolutional networks (GCNs) have achieved huge success in several machine learning (ML) tasks on graph-structured data. Recently, several sampling techniques have been proposed for the efficient training of GCNs and to improve the performance of GCNs on ML tasks. Specifically, the subgraph-based sampling approaches such as ClusterGCN and GraphSAINT have achieved state-of-the-art performance on the node classification tasks. These subgraph-based sampling approaches rely on heuristics - such as graph partitioning via edge cuts - to identify clusters that are then treated as minibatches during GCN training. In this work, we hypothesize that rather than relying on such heuristics, one can learn a reinforcement learning (RL) policy to compute efficient clusters that lead to effective GCN performance. To that end, we propose PolicyClusterGCN, an online RL framework that can identify good clusters for GCN training. We develop a novel Markov Decision Process (MDP) formulation that allows the policy network to predict "importance" weights on the edges which are then utilized by a clustering algorithm (Graclus) to compute the clusters. We train the policy network using a standard policy gradient algorithm where the rewards are computed from the classification accuracies while training GCN using clusters given by the policy. Experiments on six real-world datasets and several synthetic datasets show that PolicyClusterGCN outperforms existing state-of-the-art models on node classification task.

Mining in proof-of-work blockchains has become an expensive affair requiring specialized hardware capable of executing several megahashes per second at huge electricity costs. Miners earn a reward each time they mine a block within the longest chain, which helps offset their mining costs. It is therefore of interest to miners to maximize the number of mined blocks in the blockchain and increase revenue. A key factor affecting mining rewards earned is the connectivity between miners in the peer- to- peer network. To maximize rewards a miner must choose its network connections carefully, ensuring existence of paths to other miners that are on average of a lower latency compared to paths between other miners. We formulate the problem of deciding whom to connect to for miners as a combinatorial bandit problem. Each node picks its neighbors strategically to minimize the latency to reach 90% of the hash power of the network relative to the 90-th percentile latency from other nodes. A key contribution of our work is the use of a network coordinates based model for learning the network structure within the bandit algorithm. Experimentally we show our proposed algorithm outperforming or matching baselines on diverse network settings.

Peer-to-peer (P2P) networks underlie a variety of decentralized paradigms including blockchains, distributed file storage and decentralized domain name systems. A central primitive in P2P networks is the peer selection algorithm, which decides how a node should select a fixed number of neighbors to connect with. In this paper, we consider the design of a peer selection algorithm for unstructured P2P networks with the goal of minimizing the broadcast latency. We propose Goldfish, a novel solution that dynamically decides the neighbor set by exploiting the past experiences as well as exploring new neighbors. The key technical contributions come from bringing ideas of matrix completion for estimating message delivery times for every possible message for every peer ever connected, and a streaming algorithm to efficiently perform the estimation while achieving good performance. The matrix completion interpolates the delivery times to all virtual connections in order to select the best combination of neighbors. Goldfish employs a streaming algorithm that only uses a short recent memory to finish matrix interpolation. When the number of publishing source is equal to a node's maximal number of connections, Goldfish found the global optimal solution with 92.7% probability by exploring every node only once. In more complex situations where nodes are publishing based on exponential distribution and adjusting connection in real time, we compare Goldfish with a baseline peer selection system, Perigee [1], and show Goldfish saves approximately 14.5% less time under real world geolocation and propagation latency.

A key performance metric in blockchains is the latency between when a transaction is broadcast and when it is confirmed (the so-called, confirmation latency). While improvements in consensus techniques can lead to lower confirmation latency, a fundamental lower bound on confirmation latency is the propagation latency of messages through the underlying peer-to-peer (p2p) network (in Bitcoin, the propagation latency is several tens of seconds). The de facto p2p protocol used by Bitcoin and other blockchains is based on random connectivity: each node connects to a random subset of nodes. The induced p2p network topology can be highly suboptimal since it neglects geographical distance, differences in bandwidth, hash-power and computational abilities across peers. We present Perigee, a decentralized algorithm that automatically learns an efficient p2p topology tuned to the aforementioned network heterogeneities, purely based on peers' interactions with their neighbors. Motivated by the literature on the multi-armed bandit problem, Perigee optimally balances the tradeoff between retaining connections to known well-connected neighbors, and exploring new connections to previously-unseen neighbors. Experimental evaluations show that Perigee reduces the latency to broadcast by 33%. Lastly Perigee is simple, computationally lightweight, adversary-resistant, and compatible with the selfish interests of peers, making it an attractive p2p protocol for blockchains.

We present Placeto, a reinforcement learning (RL) approach to efficiently find device placements for distributed neural network training. Unlike prior approaches that only find a device placement for a specific computation graph, Placeto can learn generalizable device placement policies that can be applied to any graph. We propose two key ideas in our approach: (1) we represent the policy as performing iterative placement improvements, rather than outputting a placement in one shot; (2) we use graph embeddings to capture relevant information about the structure of the computation graph, without relying on node labels for indexing. These ideas allow Placeto to train efficiently and generalize to unseen graphs. Our experiments show that Placeto requires up to 6.1x fewer training steps to find placements that are on par with or better than the best placements found by prior approaches. Moreover, Placeto is able to learn a generalizable placement policy for any given family of graphs that can be used without any re-training to predict optimized placements for unseen graphs from the same family. This eliminates the huge overhead incurred by the prior RL approaches whose lack of generalizability necessitates re-training from scratch every time a new graph is to be placed.

We present Park, a platform for researchers to experiment with Reinforcement Learning (RL) for computer systems. Using RL for improving the performance of systems has a lot of potential, but is also in many ways very different from, for example, using RL for games. Thus, in this work we first discuss the unique challenges RL for systems has, and then propose Park an open extensible platform, which makes it easier for ML researchers to work on systems problems. Currently, Park consists of 12 real world system-centric optimization problems with one common easy to use interface. Finally, we present the performance of existing RL approaches over those 12 problems and outline potential areas of future work.

Efficiently scheduling data processing jobs on distributed compute clusters requires complex algorithms. Current systems use simple, generalized heuristics and ignore workload characteristics, since developing and tuning a scheduling policy for each workload is infeasible. In this paper, we show that modern machine learning techniques can generate highly-efficient policies automatically.

With the growing usage of Bitcoin and other cryptocurrencies, many scalability challenges have emerged. A promising scaling solution, exemplified by the Lightning Network, uses a network of bidirectional payment channels that allows fast transactions between two parties. However, routing payments on these networks efficiently is non-trivial, since payments require finding paths with sufficient funds, and channels can become unidirectional over time blocking further transactions through them. Today's payment channel networks exacerbate these problems by attempting to deliver all payments atomically.

Two parties observing correlated random variables seek to run an interactive communication protocol. How many bits must they exchange to simulate the protocol, namely to produce a view with a joint distribution within a fixed statistical distance of the joint distribution of the input and the transcript of the original protocol? We present an information spectrum approach for this problem whereby the information complexity of the protocol is replaced by its information complexity density. Our single-shot bounds relate the communication complexity of simulating a protocol to tail bounds for information complexity density. As a consequence, we obtain a strong converse and characterize the second-order asymptotic term in communication complexity for independent and identically distributed observation sequences. Furthermore, we obtain a general formula for the rate of communication complexity, which applies to any sequence of observations and protocols. Connections with results from theoretical computer science and implications for the function computation problem are discussed.

A simulation of an interactive protocol entails the use of interactive communication to produce the output of the protocol to within a fixed statistical distance ε. Recent works have proposed that the information complexity of the protocol plays a central role in characterizing the minimum number of bits that the parties must exchange for a successful simulation, namely the distributional communication complexity of simulating the protocol. Several simulation protocols have been proposed with communication complexity depending on the information complexity of the simulated protocol. However, in the absence of any general lower bounds for distributional communication complexity, the conjectured central role of information complexity is far from settled. We fill this gap and show that the distributional communication complexity of ε-simulating a protocol is bounded below by the ε-tail λε of the information complexity density, a random variable with information complexity as its expected value. For protocols with bounded number of rounds, we give a simulation protocol that yields a matching upper bound. Thus, it is not information complexity but λε that governs the distributional communication complexity.

Hybrid switching -- in which a high bandwidth circuit switch (optical or wireless) is used in conjunction with a low bandwidth packet switch -- is a promising alternative to interconnect servers in today's large scale data centers. Circuit switches offer a very high link rate, but incur a non-trivial reconfiguration delay which makes their scheduling challenging. In this paper, we demonstrate a lightweight, simple and nearly-optimal scheduling algorithm that trades-off reconfiguration costs with the benefits of reconfiguration that match the traffic demands. Seen alternatively, the algorithm provides a fast and approximate solution towards a constructive version of Caratheodory's Theorem for the Birkhoff polytope. The algorithm also has strong connections to submodular optimization, achieves a performance at least half that of the optimal schedule and strictly outperforms state of the art in a variety of traffic demand settings. These ideas naturally generalize: we see that indirect routing leads to exponential connectivity; this is another phenomenon of the power of multi-hop routing, distinct from the well-known load balancing effects.

We consider live-streaming over a peer-to-peer network in which peers are allowed to enter or leave the system adversarially and arbitrarily. Previous approaches for streaming have either used randomized distribution graphs or structured trees with randomized maintenance algorithms. Randomized graphs handle peer churn well but have only probabilistic connectivity guarantees, while structured trees have good connectivity but have proven hard to maintain under peer churn. We improve upon both approaches by presenting a novel distribution structure with a deterministic and distributed algorithm for maintenance under peer churn. The algorithm has a constant repair time for connectivity, and near optimal delay. As opposed to order results, the guarantees provided by our algorithm are exact and hold for any network size.

We propose a new coding scheme for interference alignment in a single hop fast fading wireless network with general message demands. For the X-Channel, the Degrees of Freedom (DoF) region achievable by the scheme is shown to touch a known outer-bound at several points. For multiple-multicast demands we show that the achievable region is at least half of the cut-set bound region. The key innovation in our scheme is the reduction of the vector space alignment problem to a combinatorial arrangement problem. Finally, we use the scheme to give a poly-logarithmic bound for the flow-cut gap in fast fading Gaussian wireless networks with multiple multicasts.