Now showing items 1-20 of 504

    • Randomized Multi-Source Broadcast Protocols in Multi-Hop Radio Networks 

      Lee, Chungki; Ammar, Mostafa H. (Mostafa Hamed); Burns, James Edward (Georgia Institute of Technology, 1993)
      In [LBA93], a suite of randomized broadcast protocols was presented for the problem of broadcasting a message in arbitrary multi-hop radio networks. These protocols improved upon that of Bar-Yehuda et al. in most of the ...
    • A Theory of Interaction and Independence in Sentence Understanding 

      Mahesh, Kavi (Georgia Institute of Technology, 1993)
      Developing a complete and well-specified computational model of human language processing is a difficult problem. Natural language understanding requires the application of many different kinds of ...
    • Distributed Consensus Revisited 

      Neiger, Gil (Georgia Institute of Technology, 1993)
      Distributed Consensus is a classical problem in distributed computing. It requires the correct processors in a distributed system to agree on a common value despite the failure of other processors. This problem is ...
    • Reorganizing Split Objects 

      Astudillo R., Hernan; Shilling, John J. (Georgia Institute of Technology, 1993)
      Object-based (i.e. classless) models are very effective for elucidating requirements from users, and they support exploratory programming and rapid prototyping. On the other hand, class-based models are preferred to perform ...
    • Distributed Shared Abstractions (DSA) on Multiprocessors 

      Clemencon, Christian; Mukherjee, Bodhisattwa; Schwan, Karsten (Georgia Institute of Technology, 1993)
      Any parallel program has abstractions that are shared by the program's multiple processes, including data structures containing shared data, code implementing operations like global sums or minima, type instances used ...
    • Using Knowledge to Optimally Achieve Coordination in Distributed Systems 

      Neiger, Gil; Bazzi, Rida Adnan (Georgia Institute of Technology, 1993)
      The problem of coordinating the actions of individual processors is fundamental in distributed computing. Researchers have long endeavored to find efficient solutions to a variety of problems involving coordination. ...
    • A Simulation-based Scalability Study of Parallel Systems 

      Sivasubramaniam, Anand; Singla, Aman; Ramachandran, Umakishore; Venkateswaran, H. (Georgia Institute of Technology, 1993)
      Scability studies of parallel architectures have used scalar metrics to evaluate their performance. Very often, it is difficult to glean the sources of inefficiency resulting from the mismatch between the algorithmic ...
    • Improving Performace by Use of Adaptive Objects: Experimentation with a Configurable Multiprocessor Thread Package 

      Mukherjee, Bodhisattwa; Schwan, Karsten (Georgia Institute of Technology, 1993)
      Operating system kernels typically offer a fixed set of mechanisms and primitives. However, recent research shows that the attainment of high performance for a variety of parallel applications may require the ...
    • An Evaluation of State Sharing Techniques in Distributed Operating Systems 

      John, Ranjit; Ahamad, Mustaque; Ramachandran, Umakishore; Ananthanarayanan, R. (Rajagopal); Mohindra, Ajay (Georgia Institute of Technology, 1993)
      A shared memory abstraction in distributed systems (DSM) provides ease of programming but could be costly to implement. Many protocols have been proposed recently that are based on different approaches for exploiting ...
    • Improved Randomized Broadcast Protocol in Multi-hop Radio Networks 

      Lee, Chungki; Ammar, Mostafa H. (Mostafa Hamed); Burns, James Edward (Georgia Institute of Technology, 1993)
      This paper presents a suite of randomized broadcast protocols for the problem of broadcasting a message in multi-hop radio networks. The protocols are compared with the randomized broadcast protocol by Bar-Yehuda et ...
    • The Truth, the Whole Truth, and Nothing but the Truth: Alphabet Independent Two Dimensional Witness Table Construction 

      Amir, Amihood; Benson, Gary; Farach-Colton, Martin (Georgia Institute of Technology, 1993)
      The current explosion of stored information necessitates a new model of pattern matching, that of compressed matching. In this model one tries to find all occurrences of a pattern in a compressed text in time proportional ...
    • Leads-to Properties and the But-not-yet Operator 

      Calvert, Kenneth L. (Georgia Institute of Technology, 1993)
      We define a predicate transformer, in terms of which finite disjunctions of leads-to properties can be rewritten as single leads-to properties. Although disjunctions of leads-to properties do not typically arise naturally ...
    • The Sensible Sharing Approach to a Scalable, High-Performance Database System 

      Gottemukkala, Vibby; Omiecinski, Edward Robert; Ramachandran, Umakishore (Georgia Institute of Technology, 1993)
      Exploiting parallelism has become the key to building high-performance database systems. Several approaches to building database systems that support both inter and intra-query parallelism have been proposed. These ...
    • LU Logging - an Efficient Transaction Recovery Method 

      Gukal, Sreenivas; Omiecinski, Edward Robert; Ramachandran, Umakishore (Georgia Institute of Technology, 1993)
      In this paper, we present LU-Logging, an efficient transaction recovery method. The method is based on (flexible-redo/minimal-undo) algorithm. The paper describes an implementation which avoids the overheads of deferred ...
    • Lower Bounds for Perfect Matching in Restricted Boolean Circuits 

      Sengupta, Rimli; Venkateswaran, H. (Georgia Institute of Technology, 1993)
      We consider three restrictions on Boolean circuits: bijectivity, consistency and multilinearity. Our main result is that Boolean circuits require exponential size to compute the bipartite perfect matching function when ...
    • Alternative Object Organizations using Prototypes, Delegation and Split Objects 

      Astudillo R., Hernan; Shilling, John J. (Georgia Institute of Technology, 1993)
      Object-based (i.e. classless) models are very effective for elucidating requirements from users, and they support exploratory programming and rapid prototyping. On the other hand, class-based models are preferred to ...
    • Experimentation with Configurable, Lightweight Threads on a KSR Multiprocessor 

      Ghosh, Kaushik; Mukherjee, Bodhisattwa (Georgia Institute of Technology, 1993)
      The implementation of operating system functions can significantly affect the performance of parallel programs. Our research concerns the customization of operating system functionality for different target hardware to ...
    • FA{S,T}ER Scaled Matching 

      Amir, Amihood; Calinescu, Gruia (Georgia Institute of Technology, 1993)
      The rapidly growing need for analysis of digitized images in multimedia systems has lead to a variety of interesting problems in multidimensional pattern matching. One of the problems is that of scaled matching, finding ...
    • Space-Efficient Atomic Snapshots in Synchronous Systems 

      Neiger, Gil; Singh, Ranu (Georgia Institute of Technology, 1993)
      We consider the problem of implementing an atomic snapshot memory in synchronous distributed systems. An atomic snapshot memory is an array of memory locations, one per processor. Each processor may update its own ...
    • Maximum Agreement Subtree In a Set Of Evolutionary Trees 

      Amir, Amihood; Keselman, Dmitry (Georgia Institute of Technology, 1993)
      The maximum agreement subtree approach is one method of reconciling different evolution trees for the same set of species. Recently, dynamic programming ideas were used by Steele and Warnow to provide polynomial time ...