We focus on the well-studied problem of distributed overlay network construction. We consider a synchronous gossip-based communication model where in each round a node can send a message of small size to another node whose identifier it knows. The network is assumed to be reconfigurable, i.e., a node can add new connections (edges) to other nodes whose identifier it knows or drop existing connections. Each node initially has only knowledge of its own identifier and the identifiers of its neighbors. The overlay construction problem is, given an arbitrary (connected) graph, to reconfigure it to obtain a bounded-degree expander graph as efficiently as possible. The overlay construction problem is relevant to building real-world peer-to-peer network topologies that have desirable properties such as low diameter, high conductance, robustness to adversarial deletions, etc. Our main result is that we show that starting from any arbitrary (connected) graph G on n nodes and m edges, we can construct an overlay network that is a constant-degree expander in polylog rounds using only Õ(n) messages. Our time and message bounds are both essentially optimal (up to polylogarithmic factors). Our distributed overlay construction protocol is very lightweight as it uses gossip (each node communicates with only one neighbor in each round) and also scalable as it uses only Õ(n) messages, which is sublinear in m (even when m is moderately dense). To the best of our knowledge, this is the first result that achieves overlay network construction in polylog rounds and o(m) messages. Our protocol uses graph sketches in a novel way to construct an expander overlay that is both time and communication efficient. A consequence of our overlay construction protocol is that distributed computation can be performed very efficiently in this model. In particular, a wide range of fundamental tasks such as broadcast, leader election, and minimum spanning tree (MST) construction can be accomplished in polylog rounds and Õ(n) message complexity in any graph.

Manual counting of viral plaques is a tedious and labor-intensive process. In this paper, an efficient and economical method is proposed for automating viral plaque counting via image segmentation and various morphological operations. The method first segments a plate image into individual well images. Then, it converts each well image into a binary image and creates a new image by merging the dilated binary image and the complement image of the eroded binary image. At last, the contour hierarchy of the merged image is obtained and the plaque count is calculated by evaluating each outer contour count and its inner contour counts. Experiment results showed that the counting accuracy for the proposed method is up to 90 percent and the average processing time for a single image is about one second. An open source implementation with optional graphical user interface is available for public use.