A celebrated and widely used result of Lenzen and Wattenhofer [STOC’11, PODC’13] shows a constant-round (deterministic) distributed routing algorithm for the complete-graph network: if each node is the source or destination of at most Θ(n) packets, there is a constant-round deterministic distributed algorithm that routes all packets to their destinations in a constant number of rounds, on the complete-graph network. We study generalizations of this result to arbitrary network graphs and show a necessary and sufficient condition for the network so that it can route any such demand in constant rounds distributedly. One can easily see that just for the existence of a constant-round routing for all such demands, it is necessary that any cut’s size, when normalized by the number of possible edges in that cut, should be lower bounded by a positive constant. That is, for any partition of nodes with exactly k∈ [1, n/2] nodes on one side, the cut should have at least Θ(kn) edges. We call this a graph with a positive minimum normalized cut, or a positive graph for short. We show that this necessary condition is also sufficient. In particular, by tightening the Leighton-Rao multicommodity max-flow min-cut theorem for positive graphs, we show the existence of a constant-round routing in positive graphs (assuming the network graph is known globally). Then, as the main technical contribution of this paper, we also show that there is a (deterministic) distributed algorithm that computes such a constant-round routing in constant rounds in these graphs. This result allows us to vastly relax the conditions of the well-studied congested clique model of distributed computing: Any distributed algorithm for the congested clique model can be run in any positive graph network, without any asymptotic slow-down. Our results are in fact more general and they give a distributed routing bound for any network, as a function of its minimum normalized cut size (and without assuming it is a constant), within a polynomial of the relevant lower bound.

Researchers rely on lists of popular websites like the Alexa Top Million both to measure the web and to evaluate proposed protocols and systems. Prior work has questioned the correctness and consistency of these lists, but without ground truth data to compare against, there has been no direct evaluation of list accuracy. In this paper, we evaluate the relative accuracy of the most popular top lists of websites. We derive a set of popularity metrics from server-side requests seen at Cloudflare, which authoritatively serves a significant portion of the most popular websites. We evaluate top lists against these metrics and show that most lists capture web popularity poorly, with the exception of the Chrome User Experience Report (CrUX) dataset, which is the most accurate top list compared to Cloudflare across all metrics. We explore the biases that lower the accuracy of other lists, and we conclude with recommendations for researchers studying the web in the future.

Hardware is the foundation and the root of trust of any security system. However, in today's global IC industry, an IP provider, an IC design house, a CAD company, or a foundry may subvert a VLSI system with back doors or logic bombs. Such a supply chain adversary's capability is rooted in his knowledge on the hardware design. Successful hardware design obfuscation would severely limit a supply chain adversary's capability if not preventing all supply chain attacks. However, not all designs are obfuscatable in traditional technologies. We propose to achieve ASIC design obfuscation based on embedded reconfigurable logic which is determined by the end user and unknown to any party in the supply chain. Combined with other security techniques, embedded reconfigurable logic can provide the root of ASIC design obfuscation, data confidentiality and tamper-proofness. As a case study, we evaluate hardware-based code injection attacks and reconfiguration-based instruction set obfuscation based on an open source SPARC processor LEON2. We prevent program monitor Trojan attacks and increase the area of a minimum code injection Trojan with a 1KB ROM by 2.38% for every 1% area increase of the LEON2 processor.

We introduce an algorithm for interactive rendering of physically-based global illumination, based on a novel frequency analysis of indirect lighting. Our method combines adaptive sampling by Monte Carlo ray or path tracing, using a standard GPU-accelerated raytracer, with real-time reconstruction of the resulting noisy images. Our theoretical analysis assumes diffuse indirect lighting, with general Lambertian and specular receivers. In practice, we demonstrate accurate interactive global illumination with diffuse and moderately glossy objects, at 1-3 fps. We show mathematically that indirect illumination is a structured signal in the Fourier domain, with inherent band-limiting due to the BRDF and geometry terms. We extend previous work on sheared and axis-aligned filtering for motion blur and shadows, to develop an image-space filtering method for interreflections. Our method enables 5--8X reduced sampling rates and wall clock times, and converges to ground truth as more samples are added. To develop our theory, we overcome important technical challenges---unlike previous work, there is no light source to serve as a band-limit in indirect lighting, and we also consider non-parallel geometry of receiver and reflecting surfaces, without first-order approximations.

We develop a simple and efficient method for soft shadows from planar area light sources, based on explicit occlusion calculation by raytracing, followed by adaptive image-space filtering. Since the method is based on Monte Carlo sampling, it is accurate. Since the filtering is in image-space, it adds minimal overhead and can be performed at real-time frame rates. We obtain interactive speeds, using the Optix GPU raytracing framework. Our technical approach derives from recent work on frequency analysis and sheared pixel-light filtering for offline soft shadows. While sample counts can be reduced dramatically, the sheared filtering step is slow, adding minutes of overhead. We develop the theoretical analysis to instead consider axis-aligned filtering, deriving the sampling rates and filter sizes. We also show how the filter size can be reduced as the number of samples increases, ensuring a consistent result that converges to ground truth as in standard Monte Carlo rendering.