Efficient parallel algorithms forr-dominating set andp-center problems on trees

We develop efficient parallel algorithms for ther-dominating set and thep-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for ther-dominating set problem runs inO(logn log logn) time withn processors. The algorithm for thep-center problem runs inO(log² n log logn) time withn processors.     

On Using a Warehouse to Analyze Web Logs

Analyzing Web Logs for usage and access trends can not only provide important information to web site developers and administrators, but also help in creating adaptive web sites. While there are many existing tools that generate fixed reports from web logs, they typically do not allow ad-hoc analysis queries. Moreover, such tools cannot discover hidden patterns of access embedded in the access logs. We describe a relational OLAP (ROLAP) approach for creating a web-log warehouse. This is populated both from web logs, as well as the results of mining web logs. We discuss the design criteria that influenced our choice of dimensions, facts and data granularity. A web based ad-hoc tool for analytic queries on the warehouse was developed. We present some of the performance specific experiments that we performed on our warehouse.     

Efficient parallel algorithms forr-dominating set andp-center problems on trees

We develop efficient parallel algorithms for ther-dominating set and thep-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for ther-dominating set problem runs inO(logn log logn) time withn processors. The algorithm for thep-center problem runs inO(log² n log logn) time withn processors.Xin He was supported in part by an Ohio State University Presidential Fellowship, and by the Office of Research and Graduate Studies of Ohio State University. Yaacov Yesha was supported in part by the National Science Foundation under Grant No. DCR-8606366.     

Medium access control protocols for multimedia traffic in wirelessnetworks

This article presents a survey on medium access control protocols for multimedia traffic in wireless networks. A basic overview of MAC protocol concepts is presented, and a framework is developed on which to base qualitative comparisons. The MAC protocols covered include third-generation TDMA and CDMA schemes intended for use in a single-hop wireless system. The operation of each protocol is explained, and its advantages and disadvantages ore presented. Finally, a qualitative comparative outline of the discussed protocols is provided, based on multimedia traffic requirements     

On a unified framework for the evaluation of distributed quorumattainment protocols

Quorum attainment protocols are an important part of many mutual exclusion algorithms. Assessing the performance of such protocols in terms of number of messages, as is usually done, may be less significant than being able to compute the delay in attaining the quorum. Some protocols achieve higher reliability at the expense of increased message cost or delay. A unified analytical model which takes into account the network delay and its effect on the time needed to obtain a quorum is presented. A combined performability metric, which takes into account both availability and delay, is defined, and expressions to calculate its value are derived for two different reliable quorum attainment protocols: D. Agrawal and A. El Abbadi's (1991) and Majority Consensus algorithms (R.H. Thomas, 1979). Expressions for the primary site approach are also given as upper bound on performability and lower bound on delay. A parallel version of the Agrawal and El Abbadi protocol is introduced and evaluated. This new algorithm is shown to exhibit lower delay at the expense of a negligible increase in the number of messages exchanged. Numerical results derived from the model are discussed     

Querying in Packs: Trustworthy Data Management in Ad Hoc Networks

We describe a trust-based data management framework enabling mobile devices to access the distributed computation, storage, and sensory resources available in pervasive computing environments. Available resources include those in the fixed surrounding infrastructure as well as services offered by other nearby mobile devices. We take a holistic approach that considers data trust, security, and privacy and focus on the collaborative mechanisms providing a trustworthy data management platform in an ad hoc network. The framework is based on a pack formation mechanism that enables collaborative peer interactions using context information and landmarks. A pack provides a routing substrate allowing devices to find reliable information sources and coordinated pro-active and reactive mechanisms to detect and respond to malicious activity. Consequently, a pack forms a foundation for distributed trust management and data intensive interactions. We describe our data management framework with an emphasis on pack formation in mobile ad hoc networks and present preliminary results from simulation experiments.     

A lower bound on the probability of conflict under nonuniform access in database systems

Past performance analyses of resource sharing systems have often assumed uniform resource access distributions. This assumption is made for reasons of computational tractability. In some of these analyses it has been conjectured that such an assumption is optimistic, in the sense that it minimizes the probability of resource conflict. In this paper we give conditions on access distributions for which the above conjecture is true and show that these conditions are satisfied for two natural probabilistic models. Our technique can be applied to other resource contention problems.Research supported by NSF and NSA under Grant DMS-9001295.