Gossip algorithms are pivotal in the dissemination of information within decentralized systems. Consequently, numerous gossip libraries have been developed and widely utilized especially in blockchain protocols for the propagation of blocks and transactions. A well-established library is libp $2 p$, which provides two gossip algorithms: floodsub and gossipsub. These algorithms enable the delivery of published messages to a set of peers. In this work we aim to enhance the performance and reliability of libp $2 p$ by introducing OptimumP2P, a novel gossip algorithm that leverages the capabilities of Random Linear Network Coding (RLNC) to expedite the dissemination of information in a peer-to-peer (P2P) network. Preliminary research from the Ethereum Foundation has demonstrated the use of RLNC in the significant improvement in the block propagation time [15]. Here we present extensive evaluation results both in simulation and real-world environments that demonstrate the performance gains of OptimumP2P over the Gossipsub protocol.

SUMMARY: In the era of large data, the cloud is increasingly used as a computing environment, necessitating the development of cloud-compatible pipelines that can provide uniform analysis across disparate biological datasets. The Warp Analysis Research Pipelines (WARP) repository is a GitHub repository of open-source, cloud-optimized workflows for biological data processing that are semantically versioned, tested, and documented. A companion repository, WARP-Tools, hosts Docker containers and custom tools used in WARP workflows. AVAILABILITY AND IMPLEMENTATION: The WARP and WARP-Tools repositories and code are freely available at https://github.com/broadinstitute/WARP and https://github.com/broadinstitute/WARP-tools, respectively. The pipelines are available for download from the WARP repository, can be exported from Dockstore, and can be imported to a bioinformatics platform such as Terra.

Emulating a shared atomic , read/write storage system is a fundamental problem in distributed computing. Replicating atomic objects among a set of data hosts was the norm for traditional implementations (e.g., [ 11 ]) in order to guarantee the availability and accessibility of the data despite host failures. As replication is highly storage demanding, recent approaches suggested the use of erasure-codes to offer the same fault-tolerance while optimizing storage usage at the hosts. Initial works focused on a fixed set of data hosts. To guarantee longevity and scalability, a storage service should be able to dynamically mask hosts failures by allowing new hosts to join, and failed host to be removed without service interruptions. This work presents the first erasure-code -based atomic algorithm, called Ares , which allows the set of hosts to be modified in the course of an execution. Ares is composed of three main components: (i) a reconfiguration protocol , (ii) a read/write protocol , and (iii) a set of data access primitives (DAPs) . The design of Ares is modular and is such to accommodate the usage of various erasure-code parameters on a per-configuration basis. We provide bounds on the latency of read/write operations and analyze the storage and communication costs of the Ares algorithm.

READ transactions that read data distributed across servers dominate the workloads of real-world distributed storage systems. The SNOW Theorem [13] stated that ideal READ transactions that have optimal latency and the strongest guarantees-i.e., “SNOW” READ transactions-are impossible in one specific setting that requires three or more clients: at least two readers and one writer. However, it left many open questions. We close all of these open questions with new impossibility results and new algorithms. First, we prove rigorously the result from [13] saying that it is impossible to have a READ transactions system that satisfies SNOW properties with three or more clients. The insight we gained from this proof led to teasing out the implicit assumptions that are required to state the results and also, resolving the open question regarding the possibility of SNOW with two clients. We show that it is possible to design an algorithm, where SNOW is possible in a multi-writer, single-reader (MWSR) setting when a client can send messages to other clients; on the other hand, we prove it is impossible to implement SNOW in a multi-writer, single-reader (MWSR) setting-which is more general than the two-client setting-when client-to-client communication is disallowed. We also correct the previous claim in [13] that incorrectly identified one existing system, Eiger [12], as supporting the strongest guarantees (SW) and whose read-only transactions had bounded latency. Thus, there were no previous algorithms that provided the strongest guarantees and had bounded latency. Finally, we introduce the first two algorithms to provide the strongest guarantees with bounded latency.

Shared register emulations on top of message-passing systems provide an illusion of a simpler shared memory system which can make the task of a system designer easier. Numerous shared register applications have a considerably high read-to-write ratio. Thus, having algorithms that make reads more efficient than writes is a fair trade-off.Typically, such algorithms for reads and writes are asymmetric and sacrifice the stringent consistency condition atomicity, as it is impossible to have fast reads for multi-writer atomicity. Safety is a consistency condition that has has gathered interest from both the systems and theory community as it is weaker than atomicity yet provides strong enough guarantees like "strong consistency" or read-my-write consistency. One requirement that is assumed by many researchers is that of the reliable broadcast (RB) primitive, which ensures the "all or none" property during a broadcast. One drawback is that such a primitive takes 1.5 rounds to complete and requires server-to-server communication.This paper implements an efficient multi-writer multi-reader safe register without using a reliable broadcast primitive. Moreover, we provide fast reads or one-shot reads - our read operations can be completed in one round of client-to-server communication. Of course, this comes with the price of requiring more servers when compared to prior solutions assuming reliable broadcast. However, we show that this increased number of servers is indeed necessary as we prove a tight bound on the number of servers required to implement Byzantine-fault tolerant safe registers in a system without reliable broadcast.We extend our results to data stored using erasure coding as well. We present an emulation of single-writer multi-reader safe register based on MDS codes. The usage of MDS codes reduces storage and communication costs. On the negative side, we also show that to use MDS codes and at the same time achieve one-shot reads, we need even more servers.

In this work, we propose an erasure coding-based protocol that implements a key-value store with atomicity and near-optimal storage cost. Our protocol supports concurrent read and write operations while tolerating asynchronous communication and crash failures of any client and some fraction of servers. One novel feature is a tunable knob between the number of supported concurrent operations, availability, and storage cost. We implement our protocol into Cassandra, namely Cassan-drEAS (Cassandra + Erasure-coding Atomic Storage). Extensive evaluation using YCSB on Google Cloud Platform shows that CassandrEAS incurs moderate penalty on latency and throughput, yet saves significant amount of storage space.

Emulating a shared atomic, read/write storage system is a fundamental problem in distributed computing. Replicating atomic objects among a set of data hosts was the norm for traditional implementations (e.g., [6]) in order to guarantee the availability and accessibility of the data despite host failures. As replication is highly storage demanding, recent approaches suggested the use of erasure-codes to offer the same fault-tolerance while optimizing storage usage at the hosts. Initial works focused on a fix set of data hosts. To guarantee longevity and scalability, a storage service should be able to dynamically mask hosts failures by allowing new hosts to join, and failed host to be removed without service interruptions. This work presents the first erasure-code based atomic algorithm, called ARES, which allows the set of hosts to be modified in the course of an execution. ARES is composed of three main components: (i) a reconfiguration protocol, (ii) a read/write protocol, and (iii) a set of data access primitives. The design of ARES is modular and is such to accommodate the usage of various erasure-code parameters on a per-configuration basis. We provide bounds on the latency of read/write operations and analyze the storage and communication costs of the ARES algorithm.

In this work, we propose FLECKS, an algorithm which implements atomic memory objects in a multi-writer multi-reader (MWMR) setting in asynchronous networks and server failures. FLECKS substantially reduces storage and communication costs over its replication-based counterparts by employing erasure-codes. FLECKS outperforms the previously proposed algorithms in terms of the metrics that to deliver good performance such as storage cost per object, communication cost a high fault-tolerance of clients and servers, guaranteed liveness of operation, and a given number of communication rounds per operation, etc. We provide proofs for liveness and atomicity properties of FLECKS and derive worst-case latency bounds for the operations. We implemented and deployed FLECKS in cloud-based clusters and demonstrate that FLECKS has substantially lower storage and bandwidth costs, and significantly lower latency of operations than the replication-based mechanisms.

Motivated by emerging applications to the edge computing paradigm, we introduce a two-layer erasure-coded fault-tolerant distributed storage system offering atomic access for read and write operations. In edge computing, clients interact with an edge-layer of servers that is geographically near; the edge-layer in turn interacts with a back-end layer of servers. The edge-layer provides low latency access and temporary storage for client operations, and uses the back-end layer for persistent storage. Our algorithm, termed Layered Data Storage (LDS) algorithm, offers several features suitable for edge-computing systems, works under asynchronous message-passing environments, supports multiple readers and writers, and can tolerate f1 < n1/2 and f2 < n2/3 crash failures in the two layers having n1 and n2 servers, respectively. We use a class of erasure codes known as regenerating codes for storage of data in the back-end layer. The choice of regenerating codes, instead of popular choices like Reed-Solomon codes, not only optimizes the cost of back-end storage, but also helps in optimizing communication cost of read operations, when the value needs to be recreated all the way from the back-end. The two-layer architecture permits a modular implementation of atomicity and erasure-code protocols; the implementation of erasure-codes is mostly limited to interaction between the two layers. We prove liveness and atomicity of LDS, and also compute performance costs associated with read and write operations. In a system with n1 = Θ(n2), f1 = Θ(n1), f2 = Θ(n2), the write and read costs are respectively given by Θ(n1) and Θ(1) + n1 I(δ > 0). Here δ is a parameter closely related to the number of write operations that are concurrent with the read operation, and I(δ > 0) is 1 if δ > 0, and 0 if δ = 0. The cost of persistent storage in the back-end layer is Θ(1). The impact of temporary storage is minimally felt in a multi-object system running N independent instances of LDS, where only a small fraction of the objects undergo concurrent accesses at any point during the execution. For the multi-object system, we identify a condition on the rate of concurrent writes in the system such that the overall storage cost is dominated by that of persistent storage in the back-end layer, and is given by Θ(N).

FAST is a multi-threaded, I/O optimized Seed-and-Extend alignment program. FAST is extensible to nucleotide sequences making it comparable to both BLASTn and BLASTp, and also features several new usage flags reporting only HSPs meeting user defined e-value cut-offs. FASTs threaded database construction allows fast, low memory database construction e.g., RefSeq (9.4GB) can be indexed in under 5 minutes using 20 threads. The threaded database construction gives users the ability to create custom databases on demand which is useful for tasks requiring self-alignment, such as network construction [30]. Finally, FAST supports incremental database construction enabling users to keep their databases up-to-date by adding sequences without suffering the cost of reformatting the entire database. The FAST source is freely available through GitHub https:// github.com/hallamlab/FAST and test datasets can be found on Dropbox https://www.dropbox.com/sh/xvvavweuzgqybc4/ AAAWCrRnol67ZsXi2qLQWUuOa?

Erasure codes are increasingly being studied in the context of implementing atomic memory objects in large scale asynchronous distributed storage systems. When compared with the traditional replication based schemes, erasure codes have the potential of significantly lowering storage and communication costs while simultaneously guaranteeing the desired resiliency levels. In this work, we propose the Storage-Optimized Data-Atomic (SODA) algorithm for implementing atomic memory objects in the multi-writer multi-reader setting. SODA uses Maximum Distance Separable (MDS) codes, and is specifically designed to optimize the total storage cost for a given fault-tolerance requirement. For tolerating f server crashes in an n-server system, SODA uses an [n, k] MDS code with k = n - f, and incurs a total storage cost of n/n-f. SODA is designed under the assumption of reliable point-to-point communication channels. The communication cost of a write and a read operation are respectively given by O(f2) and n/n-f(δw+1), where δwdenotes the number of writes that are concurrent with the particular read. In comparison with the recent CASGC algorithm [1], which also uses MDS codes, SODA offers lower storage cost while pays more on the communication cost. We also present a modification of SODA, called SODAerr, to handle the case where some of the servers can return erroneous coded elements during a read operation. Specifically, in order to tolerate f server failures and e error-prone coded elements, the SODAerr algorithm uses an [n, k] MDS code such that k = n - 2e - f. SODAerr also guarantees liveness and atomicity, while maintaining an optimized total storage cost of n/n-f-2e.

A distributed system is considered that carries out computational tasks according to the master-worker paradigm. A master has a set of computational tasks to resolve. She assigns each task to a set of workers over the Internet, instead of computing the task locally. For each task each worker reply to the master with the task result. Since the task was not computed locally, the master can not trust the result for two main reasons: (i) workers might deliberately provide an incorrect result, (ii) the result is corrupted due to some hardware or software failure during the execution of the task. Given the above, we can model our workers as either “altruistic”, always willing to provide the correct result to each task, or “troll” that are trying to provide an incorrect result to each task. Moreover we model the failure of the worker to comply with her intended behavior, as an error probability ε. The goal of the master is to compute the correct result of all the tasks with high probability. In the literature two techniques have been used to achieve this goal: (i) “voting”, that determines the correct result of a task given multiple replies of distinct workers; (ii) “challenges”, that are tasks whose result is known and can be used to detect altruistic workers. What separates our work from the current literature is the realistic modelling of the worker's behavior and the fact that we do not restrict the task result to a binary set of answers; the domain of possible replies for a task can have multiple correct and multiple incorrect results. Given the above we evaluate the performance of the two techniques described in the literature in the scenario where ε = 0 and when ε > 0. Performance is measured in terms of: (1) time, i.e., the number of rounds performed by an algorithm for the computation of all the tasks, and (2) work, i.e., the number of total task computations performed by the workers. The case where ε = 0 is used as a best case scenario that provides the optimal time and work bounds of the problem. In the case where ε > 0 we propose two “natural” algorithms: one using a combination of both voting and challenges, and a second one using only voting. Both algorithms assume that certain system parameters are known. Since this might not always be the case we also provide an algorithm that estimates correctly these parameters with high probability.

Erasure codes offer an efficient way to decrease storage and communication costs while implementing atomic memory service in asynchronous distributed storage systems. In this paper, we provide erasure-code-based algorithms having the additional ability to perform background repair of crashed nodes. A repair operation of a node in the crashed state is triggered externally, and is carried out by the concerned node via message exchanges with other active nodes in the system. Upon completion of repair, the node re-enters active state, and resumes participation in ongoing and future read, write, and repair operations. To guarantee liveness and atomicity simultaneously, existing works assume either the presence of nodes with stable storage, or presence of nodes that never crash during the execution. We demand neither of these; instead we consider a natural, yet practical network stability condition N1 that only restricts the number of nodes in the crashed/repair state during broadcast of any message. We present an erasure-code based algorithm RADON_{C} that is always live, and guarantees atomicity as long as condition N1 holds. In situations when the number of concurrent writes is limited, RADON_{C} has significantly improved storage and communication cost over a replication-based algorithm RADON_{R}, which also works under N1. We further show how a slightly stronger network stability condition N2 can be used to construct algorithms that never violate atomicity. The guarantee of atomicity comes at the expense of having an additional phase during the read and write operations.

MOTIVATION: A perennial problem in the analysis of environmental sequence information is the assignment of reads or assembled sequences, e.g. contigs or scaffolds, to discrete taxonomic bins. In the absence of reference genomes for most environmental microorganisms, the use of intrinsic nucleotide patterns and phylogenetic anchors can improve assembly-dependent binning needed for more accurate taxonomic and functional annotation in communities of microorganisms, and assist in identifying mobile genetic elements or lateral gene transfer events. RESULTS: Here, we present a statistic called LCA* inspired by Information and Voting theories that uses the NCBI Taxonomic Database hierarchy to assign taxonomy to contigs assembled from environmental sequence information. The LCA* algorithm identifies a sufficiently strong majority on the hierarchy while minimizing entropy changes to the observed taxonomic distribution resulting in improved statistical properties. Moreover, we apply results from the order-statistic literature to formulate a likelihood-ratio hypothesis test and P-value for testing the supremacy of the assigned LCA* taxonomy. Using simulated and real-world datasets, we empirically demonstrate that voting-based methods, majority vote and LCA*, in the presence of known reference annotations, are consistently more accurate in identifying contig taxonomy than the lowest common ancestor algorithm popularized by MEGAN, and that LCA* taxonomy strikes a balance between specificity and confidence to provide an estimate appropriate to the available information in the data. AVAILABILITY AND IMPLEMENTATION: The LCA* has been implemented as a stand-alone Python library compatible with the MetaPathways pipeline; both of which are available on GitHub with installation instructions and use-cases (http://www.github.com/hallamlab/LCAStar/). CONTACT: [email protected] information: Supplementary data are available at Bioinformatics online.

Accurate description of the microbial communities driving matter and energy transformations in complex ecosystems such as soils cannot yet be effectively accomplished using assembly-based approaches despite the rise of next generation sequencing technologies. Here we present SOFA, an open source pipeline enabling comparative functional annotation of unassembled short-read data. The pipeline attempts to merge mate pairs in fastq files, predicts open reading frames (ORFs) on merged and unmerged reads as small as 70 bps, and completes an additional step, we term `deduplication'. Deduplication prevents the double counting of ORFs predicted from unmerged paired-end reads by checking for homologous annotations that span the same ORF, allowing for quantitatively accurate predictions. The effectiveness of SOFA is validated with both simulated and bone fide soil metagenomes, and empirical results are compared to existing strategies for obtaining accurate ORF counts, and an analytical model of read duplication. SOFA enables downstream processing stages within the existing MetaPathways pipeline, and is available for download as a stand alone application at https://github.com under the MIT license.

A fundamental step in the analysis of environmental sequence information is the prediction of potential genes or open reading frames (ORFs) encoding the metabolic potential of individual cells and entire microbial communities. FragGeneScan, a software designed to predict intact and incomplete ORFs on short sequencing reads combines codon usage bias, sequencing error models and start/stop codon patterns in a hidden Markov model to find the most likely path of hidden states from a given input sequence, provides a promising route for gene recovery in environmental datasets with incomplete assemblies. However, the current implementation of FragGeneScan does not scale efficiently with increasing input data size. Thus, FragGeneScan cannot be applied to contemporary environmental datasets that can exceed 100s of Gb. Here, we present FragGeneScan-Plus, an improved implementation of the FragGeneScan gene prediction model that leverages algorithmic thread synchronization and efficient in-memory data management to utilize multiple CPU cores without blocking I/O operations. FragGeneScan-Plus can process data approximately 5-times faster than FragGeneScan using a single core and approximately 50-times faster using eight hyper-threaded cores when benchmarked against simulated and real world environmental datasets.

UNLABELLED: Next-generation sequencing is producing vast amounts of sequence information from natural and engineered ecosystems. Although this data deluge has an enormous potential to transform our lives, knowledge creation and translation need software applications that scale with increasing data processing and analysis requirements. Here, we present improvements to MetaPathways, an annotation and analysis pipeline for environmental sequence information that expedites this transformation. We specifically address pathway prediction hazards through integration of a weighted taxonomic distance and enable quantitative comparison of assembled annotations through a normalized read-mapping measure. Additionally, we improve LAST homology searches through BLAST-equivalent E-values and output formats that are natively compatible with prevailing software applications. Finally, an updated graphical user interface allows for keyword annotation query and projection onto user-defined functional gene hierarchies, including the Carbohydrate-Active Enzyme database. AVAILABILITY AND IMPLEMENTATION: MetaPathways v2.5 is available on GitHub: http://github.com/hallamlab/metapathways2. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

The development of high-throughput sequencing technologies over the past decade has generated a tidal wave of environmental sequence information from a variety of natural and human engineered ecosystems. The resulting flood of information into public databases and archived sequencing projects has exponentially expanded computational resource requirements rendering most local homology-based search methods inefficient. We recently introduced MetaPathways v1.0, a modular annotation and analysis pipeline for constructing environmental Pathway/Genome Databases (ePGDBs) from environmental sequence information capable of using the Sun Grid engine for external resource partitioning. However, a command-line interface and facile task management introduced user activation barriers with concomitant decrease in fault tolerance. Here we present MetaPathways v2.0 incorporating a graphical user interface (GUI) and refined task management methods. The MetaPathways GUI provides an intuitive display for setup and process monitoring and supports interactive data visualization and sub-setting via a custom Knowledge Engine data structure. A master-worker model is adopted for task management allowing users to scavenge computational results from a number of worker grids in an ad hoc, asynchronous, distributed network that dramatically increases fault tolerance. This model facilitates the use of EC2 instances extending ePGDB construction to the Amazon Elastic Cloud.

Internet supercomputing is an approach to solving partitionable, computation-intensive problems by harnessing the power of a vast number of interconnected computers. For the problem of using network supercomputing to perform a large collection of independent tasks, prior work introduced a decentralized approach and provided randomized synchronous algorithms that perform all tasks correctly with high probability, while dealing with misbehaving or crash-prone processors. The main weaknesses of existing algorithms is that they assume either that the average probability of a non-crashed processor returning incorrect results is inferior to 12, or that the probability of returning incorrect results is known to each processor. Here we present a randomized synchronous distributed algorithm that tightly estimates the probability of each processor returning correct results. Starting with the set P of n processors, let F be the set of processors that crash. Our algorithm estimates the probability pi of returning a correct result for each processor i ∈ P - F, making the estimates available to all these processors. The estimation is based on the (ε, δ)-approximation, where each estimated probability p̃iof piobeys the bound Pr[pi(1 - ε) ≤ p̃i≤ pi(1 + ε)] > 1 - δ, for any constants δ > 0 and ε > 0 chosen by the user. An important aspect of this algorithm is that each processor terminates without global coordination. We assess the efficiency of the algorithm in three adversarial models as follows. For the model where the number of non-crashed processors P - F is linearly bounded the time complexity T (n) of the algorithm is O(log n), work complexity W(n) is O(n log n), and message complexity M(n) is O(n log2n). For the model where P - F is bounded by a fractional polynomial we have T(n) = O(n1-alog n log log n), W(n) = O(n log n log log n), and M(n) = O(n log2n log log n). For the model where P - F is bounded by a poly-logarithm we have T(n) = O(n), W(n) = O(n poly log n), and M(n) = O(n log2n poly log n). All bounds are shown to hold with high probability.

Distributed cooperative computing in networks involves marshaling collections of network nodes possessing the necessary computational resources. Before the willing nodes can act in a concerted way they must first discover one another. This is the general setting of the Resource Discovery Problem (RDP). This paper presents a self-stabilizing algorithm that solves RDP in a deterministic synchronous setting. The solution approach is formulated in terms of evolving knowledge graphs, where vertices represent the participating network nodes, and edges represent one node's knowledge about another. Ideally, the diameter of such a graph is one, i.e., each node knows all others. The algorithm works in rounds as it evolves the knowledge graph with the goal of reducing its diameter. This is accomplished by nodes sharing their knowledge through gossip messages. We prove that the algorithm is self-stabilizing, i.e., it tolerates arbitrary perturbations in the nodes' local states and is guaranteed to solve the problem once such failures subside. The algorithm has stabilization time of O(D), and it takes at most 4D + 4 complete round to stabilize, where D is the diameter of the initial knowledge graph, and the corresponding message complexity is O,(|V|j ⋅D), where V is the set of participating nodes.

BACKGROUND: A central challenge to understanding the ecological and biogeochemical roles of microorganisms in natural and human engineered ecosystems is the reconstruction of metabolic interaction networks from environmental sequence information. The dominant paradigm in metabolic reconstruction is to assign functional annotations using BLAST. Functional annotations are then projected onto symbolic representations of metabolism in the form of KEGG pathways or SEED subsystems. RESULTS: Here we present MetaPathways, an open source pipeline for pathway inference that uses the PathoLogic algorithm to map functional annotations onto the MetaCyc collection of reactions and pathways, and construct environmental Pathway/Genome Databases (ePGDBs) compatible with the editing and navigation features of Pathway Tools. The pipeline accepts assembled or unassembled nucleotide sequences, performs quality assessment and control, predicts and annotates noncoding genes and open reading frames, and produces inputs to PathoLogic. In addition to constructing ePGDBs, MetaPathways uses MLTreeMap to build phylogenetic trees for selected taxonomic anchor and functional gene markers, converts General Feature Format (GFF) files into concatenated GenBank files for ePGDB construction based on third-party annotations, and generates useful file formats including Sequin files for direct GenBank submission and gene feature tables summarizing annotations, MLTreeMap trees, and ePGDB pathway coverage summaries for statistical comparisons. CONCLUSIONS: MetaPathways provides users with a modular annotation and analysis pipeline for predicting metabolic interaction networks from environmental sequence information using an alternative to KEGG pathways and SEED subsystems mapping. It is extensible to genomic and transcriptomic datasets from a wide range of sequencing platforms, and generates useful data products for microbial community structure and function analysis. The MetaPathways software package, installation instructions, and example data can be obtained from http://hallam.microbiology.ubc.ca/MetaPathways.

Internet supercomputing is an approach to solving partitionable, computation-intensive problems by harnessing the power of a vast number of interconnected computers. For the problem of using network supercomputing to perform a large collection of independent tasks, our prior work introduced the decentralized approach, and provided a synchronous algorithm that is able to perform all tasks with high probability (whp), while dealing with malicious behaviors under a rather strong assumption that the average probability of live (non-crashed) processors returning bogus results remains inferior to 1/2 during the computation. There the adversary is severely limited in its ability to crash processors that normally return correct results. This work develops an efficient synchronous decentralized algorithm that is able to deal with a much stronger adversary. We consider a failure model with crashes, where given the initial set of processors P, an adversary is able to crash any subset F of processors, where |F| ≤ f•n, for a constant f (0<f<1), under the constraint that there exists a subset H ⊆ P - F, with |H| = Ω(n), called the hardened set, such that the average probability of a processor in H returning a bogus result is inferior to 1/2. Here any processor may return bogus results, and H may be much smaller than P-F, while the average probability of processors in P-F returning a bogus result may be greater than 1/2. We develop an efficient randomized algorithm for n processors and t tasks (n≤t), where each live processor is able to determine locally when all tasks are performed, and obtain the results of all tasks. We prove that in Θ(t⁄n logn) rounds all live workers know the results of all tasks whp, and that these results are correct whp. The work complexity of the algorithm is Θ(tlogn), the message complexity is Θ(nlogn ), and the bit complexity is O(tn log3n).

Traditional approaches to network supercomputing employ a master process and a large number of potentially undependable worker processes that must perform a collection of tasks on behalf of the master. In such a centralized scheme, the master process is a performance bottleneck and a single point of failure. This work develops an original approach that eliminates the master and instead uses a decentralized algorithm, where each worker is able to determine locally that all tasks have been performed, and to collect locally the results of all tasks. The failure model assumes that the average probability of a worker returning a wrong result is inferior to 1/2. A randomized synchronous algorithm for n processes and n tasks is presented. The algorithm terminates in Θ(log n) rounds, and it is proved that upon termination the workers know the results of all tasks with high probability, and that these results are correct with high probability. The message complexity of the algorithm is Θ(n log n), and the bit complexity is O(n2 log3 n).

Quorum systems-collections of sets with pairwise nonempty intersections-are used in distributed settings to implement services such as consensus and consistent memory. Quorums have been substantially studied in static settings, however the design and analysis of quorum-based distributed services in resource-limited ad hoc networks is a relatively unexplored area. The pioneering work of Chockler, Gilbert, and Patt-Shamir considers such networks and proposes an implementation of probabilistic quorum systems with per-node communication bit complexity of O(log2n), where n is the number of nodes. The authors assumes a priori knowledge of node failure probability p, where 0 ¿ p2n). We demonstrate the utility of our construction by presenting a single-writer, multi-reader algorithm that uses our probabilistic quorums to implement atomic objects in ad hoc networks, where consistency is guaranteed with high probability. We include simulation results illustrating the high probability guarantee for our atomic memory service.

Developing middleware services for dynamic distributed systems, e.g., ad-hoc networks, is a challenging task given that such services deal with dynamically changing membership and asynchronous communication. Algorithms developed for static settings are often not usable in such settings because they rely on (logical) all-to-all node connectivity through routing protocols, which may be unfeasible or prohibitively expensive to implement in highly dynamic settings. This paper explores the indirect learning, via periodic gossip, approach to information dissemination within a dynamic, distributed data service implementing atomic read/write memory service. The indirect learning scheme is used to improve the liveness of the service in the settings with uncertain connectivity. The service is formally proved to guarantee atomicity in all executions. Conditional performance analysis of the new service is presented, where this analysis has the potential of being generalized to other similar dynamic algorithms. Under the assumption that the network is connected, and assuming reasonable timing conditions, the bounds on the duration of read/write operations of the new service are calculated. Finally, the paper proposes a deployment strategy where indirect learning leads to an improvement in communication costs relative to a previous solution that assumes all-to-all connectivity.

Accurate and fast image segmentation algorithms are of paramount importance for a wide range of medical imaging applications. Level set algorithms based on narrow band implementation have been among the most widely used segmentation algorithms. However, the accuracy of standard level set algorithms is compromised by the fact that their evolution schemes deteriorate the signed distance level set functions required for accurate computation of normals and curvatures. The most common remedy is to use an ad-hoc reinitialization step to rebuild the signed distance function frequently. Meanwhile, complex upwind finite difference schemes are required for stable evolution. They together make the overall computation expensive. In this paper, we propose a novel fast narrow band distance preserving level set evolution algorithm that eliminates the need for both reinitialization and complex upwind finite difference schemes. This is achieved by incorporating into a variational level set formulation with a signed distance preserving term that regularizes the evolution. As a result, stable, accurate, fast evolution could be obtained using a simple finite difference scheme within a very narrow band, defined as the union of all 3times3 pixel blocks around the zero crossing pixels. Also, our method allows the use of larger time step to speed up the convergence while ensuring accurate result, as well as the use of more general and computational efficient initial level set functions rather than the signed distance functions required by standard level set methods. The proposed algorithm has been applied on both synthetic and real images of different modalities with promising results

The resource discovery problem, where cooperating machines need to find one another in a network, was introduced by Harchol-Balter, Leighton, and Lewin (1999) in the context of Akamai Technologies with the goal of building an Internet-wide content-distribution system. In the solutions for the synchronous setting proposed so far in the papers by Harchol-Bartel et al. (1999), Kutten et al. (2001) and Law and Siu (2000), there is a possibility that during some time step many machines may contact a single machine, and this is not a realistic assumption. This work assumes a synchronous model, however at each step a machine can send and receive only a constant number of messages. It is shown that the conjectured poly-logarithmic upper bound (Harchol-Bartel et al., 1999) for such a setting is not possible. This is done by proving a lower bound on time of Omega(n), where n is the number of participating nodes. For this model a randomized algorithm is presented that solves the resource discovery problem in O(n log2n) time, i.e., within a poly-logarithmic factor of the corresponding lower bound. The algorithm has a O(n2log2n) message complexity and O(n3log3n) communication complexity. Simulation results for the algorithm illustrate the lower and upper bounds, and lead to interesting observations

Summary: DNA-BAR is a software package for selecting DNA probes (henceforth referred to as distinguishers) that can be used in genomic-based identification of microorganisms. Given the genomic sequences of the microorganisms, DNA-BAR finds a near-minimum number of distinguishers yielding a distinct hybridization pattern for each microorganism. Selected distinguishers satisfy user specified bounds on length, melting temperature and GC content, as well as redundancy and cross-hybridization constraints. Availability: DNA-BAR can be used online through the web interface provided at http://dna.engr.uconn.edu/~software/DNA-BAR/. The open source C code, released under the GNU General Public License, is also available at the above address. Contact: [email protected]

Distributed algorithms in dynamic networks often employ communication patterns whose purpose is to disseminate information among the participants. Gossiping is one form of such communication pattern. In dynamic settings, the set of participants can change substantially as new participants join, and as failures and voluntary departures remove those who have joined previously. A natural question for such settings is: how soon can newly joined nodes discover each other by means of gossiping? This paper abstracts and studies the join problem for dynamic systems that use all-to-all gossip. The problem is studied in terms of join-connectivity graphs where vertices represent the participants and where each edge represents one participant's knowledge about another. Ideally, such a graph has diameter one, i.e., all participants know each other. The diameter can grow as new participants join, and as failures remove edges from the graph. Gossip helps participants discover one another, decreasing the diameter. The results describe the lower and upper bounds on the number of communication rounds such that the participants who have previously joined discover one another, under a variety of assumptions about the joining and failures. For example, in the case when new participants join at multiple participants and participants may crash, the number of rounds cannot be bounded. In the more benign cases when the failures can be controlled or when new participants join at only one participant, the bound on rounds is shown to be logarithmic in the diameter of the initial configuration.

A fuzzy knowledge-based network is developed based on the linguistic rules extracted from a fuzzy decision tree. A scheme for automatic linguistic discretization of continuous attributes, based on quantiles, is formulated. A novel concept for measuring the goodness of a decision tree, in terms of its compactness (size) and efficient performance, is introduced. Linguistic rules are quantitatively evaluated using new indices. The rules are mapped to a fuzzy knowledge-based network, incorporating the frequency of samples and depth of the attributes in the decision tree. New fuzziness measures, in terms of class memberships, are used at the node level of the tree to take care of overlapping classes. The effectiveness of the system, in terms of recognition scores, structure of decision tree, performance of rules, and network size, is extensively demonstrated on three sets of real-life data.