Under the broader scope of optimization with explorable uncertainty, scheduling with explorable uncertainty (also known as scheduling with testing) has gained increasing attention. In scheduling with explorable uncertainty, the processing times of jobs can be potentially reduced through testing before processing. This paper studies perpetual scheduling problems within the framework of explorable uncertainty, focusing on two prominent examples: the bamboo trimming problem and the windows scheduling problem. In the bamboo trimming problem, we aim to establish a perpetual cutting schedule to minimize the maximum height of bamboos that grow at different rates. In the windows scheduling problem, we want to schedule pages on broadcasting channels such that the interval between any two consecutive broadcasts of each page does not exceed its specified window, while minimizing the total number of channels. For the bamboo trimming with explorable uncertainty problem, we present a 4-competitive algorithm for the online version and a 3.5-approximation algorithm for the offline version. For the windows scheduling with explorable uncertainty problem, we provide (3 + o(1))-competitive and (2 + o(1))-approximation algorithms for the online and offline versions, respectively.

A consensus tree is a phylogenetic tree that summarizes the evolutionary relationships inferred from a collection of phylogenetic trees with the same set of leaf labels. Among the many types of consensus trees that have been proposed in the last 50 years, the frequency difference consensus tree is one of the more finely resolved types that retains a large amount of information. This paper presents a new deterministic algorithm for constructing the frequency difference consensus tree. Given k phylogenetic trees with identical sets of n leaf labels, it runs in O(kn log n) time, improving the best previously known solution.

In this paper, we study the problems of computing the 1-center, centroid, and 1-median of objects moving with bounded speed in Euclidean space. We can acquire the exact location of only a constant number of objects (usually one) per unit time, but for every other object, its set of potential locations, called the object’s uncertainty region, grows subject only to the speed limit. As a result, the center of the objects may be at several possible locations, called the center’s uncertainty region. For each of these center problems, we design query strategies to minimize the size of the center’s uncertainty region and compare its performance to an optimal query strategy that knows the trajectories of the objects, but must still query to reduce their uncertainty. For the static case of the 1-center problem in R¹, we show an algorithm that queries four objects per unit time and is 1-competitive against the optimal algorithm with one query per unit time. For the general case of the 1-center problem in R¹, the centroid problem in Rᵈ, and the 1-median problem in R¹, we prove that the Round-robin scheduling algorithm is the best possible competitive algorithm. For the center of mass problem in Rᵈ, we provide an O(log n)-competitive algorithm. In addition, for the general case of the 1-center problem in Rᵈ (d ≥ 2), we argue that no algorithm can guarantee a bounded competitive ratio against the optimal algorithm.

This paper studies two related scheduling problems: fractional bamboo trimming and distributed windows scheduling. In the fractional bamboo trimming problem, we are given n bamboos with different growth rates and cut fractions. At the end of each day, we can cut a fraction of one bamboo. The goal is to design a perpetual schedule of cuts to minimize the height of the tallest bamboo ever. For this problem, we present a 2-approximation algorithm. In addition, we prove upper bounds on the approximation factors of well-known algorithms Reduce-Max and Reduce-Fastest(x) for this problem. In the closely related windows scheduling problem, given a multiset of positive integers W = {w₁, …, wₙ}, we want to schedule n pages on broadcasting channels such that the time interval between any two consecutive appearances of the i-th page (1 ≤ i ≤ n) is at most wᵢ. The goal of this problem is to minimize the number of channels. We provide an algorithm for the windows scheduling problem that uses at most ⌈(d(W) + 1) / 0.75⌉ channels, where d(W) = ∑(i=1 to n)(1/wᵢ). When d(W) ≤ 46, our algorithm guarantees a smaller upper bound on the number of channels than the best-known algorithm in the literature. We also describe the first approximation algorithm for the windows scheduling problem in a distributed setting, where input data is partitioned among a set of m machines. Furthermore, we introduce patterns of some multisets with d(W) ≤ 1 for which windows scheduling on one channel (i.e., pinwheel scheduling) is impossible.

Sidechains allow transaction dissemination and execution outside the blockchain main network (i.e., the mainchain), enabling a scalable, efficient, and secure financial infrastructure for the Internet of Things (IoT) without trusting any central authority. Existing sidechains either have online requirements or rely on intensive computation on a central operator, which does not meet the needs of IoT for dynamic changes and high performance. This paper proposes an alternative sidechain construction, called Cumulus, which meets the needs of IoT by leveraging the classic Byzantine fault-tolerant (BFT) consensus protocols such as PBFT that have commonly been applied in permissioned blockchains. Cumulus builds BFT-based sidechains atop public blockchains (e.g., Ethereum) using smart contracts and ensures the bidirectional safety of users’ assets. Cumulus sidechains periodically interact with the mainchain and submit checkpoints through representatives selected in an efficient and decentralized manner. The experiments show that Cumulus sidechains outperform rollup-based sidechains, and state-of-the-art sidechain constructions, achieving two and three orders of magnitude improvement in throughput and latency while retaining comparable operational cost.

As adoption of blockchain-based systems grows, more attention is being given to privacy of these systems. Early systems like BitCoin provided few privacy features. As a result, systems with strong privacy guarantees, including Monero, Zcash, and MimbleWimble have been developed. Compared to BitCoin, these cryptocurrencies are much less understood. In this paper, we focus on MimbleWimble, which uses the Dandelion++ protocol for private transaction relay and transaction aggregation to provide transaction content privacy. We find that in combination these two features make MimbleWimble susceptible to a new type of denial-of-service attacks. We design, prototype, and evaluate this attack on the Beam network using a private test network and a network simulator. We find that by controlling only 10% of the network nodes, the adversary can prevent over 45% of all transactions from ending up in the blockchain. We also discuss several potential approaches for mitigating this attack.

Sidechains enable off-chain scaling by sending transactions in a private network rather than broadcasting them in the public blockchain (i.e., the mainchain) network. To this end, classic Byzantine fault-tolerant (BFT) consensus protocols such as PBFT seem an excellent fit to fuel sidechains for their permissioned settings and inherent robustness. However, designing a secure and efficient BFT-based sidechain protocol remains an open challenge.This paper presents Cumulus, a novel BFT-based sidechain framework for blockchains to achieve off-chain scaling without compromising any security and efficiency properties of both sides’ consensus protocols. Cumulus encompasses a novel cryptographic sortition algorithm called Proof-of-Wait to fairly select sidechain nodes to communicate with the mainchain in an efficient and decentralized manner. To further reduce the operational cost, Cumulus provides an optimistic checkpointing approach in which the mainchain will not verify checkpoints unless disputes happen. Meanwhile, end-users enjoy a two-step withdrawal protocol, ensuring that they can safely collect assets back to the mainchain without relying on the BFT committee. Our experiments show that Cumulus sidechains outperform ZK-Rollup, another promising sidechain construction, achieving one and two orders of magnitude improvement in throughput and latency while retaining comparable operational cost.

Given a set of points in the plane, the unit clustering problem asks for finding a minimum-size set of unit disks that cover the whole input set. We study the unit clustering problem in a distributed setting, where input data is partitioned among several machines. We present a (3 + ε)-approximation algorithm for the problem in the Euclidean plane, and a (4 + ε)-approximation algorithm for the problem under general Lp metric (p ≥ 1). We also study the capacitated version of the problem, where each cluster has a limited capacity for covering the points. We present a distributed algorithm for the capacitated version of the problem that achieves an approximation factor of 4 + ε in the L2 plane, and a factor of 5 + ε in general Lp metric. We also provide some complementary lower bounds.