Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 16 of 16
Full-Text Articles in Computer Sciences
Optimal Algorithms For Multipacket Routing Problems On Rings, Fillia Makedon, Antonios Symvonis
Optimal Algorithms For Multipacket Routing Problems On Rings, Fillia Makedon, Antonios Symvonis
Computer Science Technical Reports
We study multipacket routing problems. We divide the multipacket routing problem into two classes, namely, distance limited and bisection limited routing problems. Then, we concentrate on rings of processors. We prove a new lower bound of 2n/ 3 routing steps for the case of distance limited routing problems. We also give an algorithm that tightens this lower bound. For bisection limited problems the lower bound is kn/ 4,k >2, where k is the number of packets per processor. The trivial algorithm needs in the worst case k | n /2| steps to terminate. An algorithm that completes the routing in …
Effects Of Replication On The Duration Of Failure In Distributed Databases, Donald B. Johnson, Larry Raab
Effects Of Replication On The Duration Of Failure In Distributed Databases, Donald B. Johnson, Larry Raab
Computer Science Technical Reports
Replicating data objects has been suggested as a means of increasing the performance of a distributed database system in a network subject to link and site failures. Since a network may partition as a consequence of such failures, a data object may become unavailable from a given site for some period of time. In this paper we study duration failure, which we define as the length of time, once the object becomes unavailable from a particular site, that the object remains unavailable. We show that, for networks composed of highly-reliable components, replication does not substantially reduce the duration of failure. …
Availability Issues In Data Replication In Distributed Database, Donald B. Johnson, Larry Raab
Availability Issues In Data Replication In Distributed Database, Donald B. Johnson, Larry Raab
Computer Science Technical Reports
Replication of data at more than one site in a distributed database has been reported to increase the availability in data in systems where sites and links are subject to failure. We have shown in results summarized in this paper that in many interesting cases the advantage is slight. A well-placed single copy is available to transactions almost as much of the time as is correct replicated data no matter how ingeniously it is managed. We explain these findings in terms of the behavior of the partitions that form in networks where components fail. We also show that known and …
Complexity Of Network Reliability And Optimal Database Placement Problems, Donald B. Johnson, Larry Raab
Complexity Of Network Reliability And Optimal Database Placement Problems, Donald B. Johnson, Larry Raab
Computer Science Technical Reports
A fundamental problem of distributed database design in an existing network where components can fail is finding an optimal location at which to place the database in a centralized system or copies of each data item in a decentralized or replicated system. In this paper it is proved for the first time exactly how hard this placement problem is under the measure of data availability. Specifically, we show that the optimal placement problem for availability is #P- complete, a measure of intractability at least as severe as NP-completeness. Given the anticipated computational difficulty of finding an exact solution, we go …
Ilona: An Advanced Cai Tutorial System For The Fundamentals Of Logic, Otto Mayer, Graham E. Oberem, Fillia Makedon
Ilona: An Advanced Cai Tutorial System For The Fundamentals Of Logic, Otto Mayer, Graham E. Oberem, Fillia Makedon
Computer Science Technical Reports
An advanced tutorial system for teaching the fundamentals of logic has been developed to run on UNIX work stations and commonly available micro-computers. An important part of this tutorial is the intelligent problem solving environment which allows students to practise wiriting logical sentences in mathematical notation. A natural language system for intelligent logic narrative analysis (ILONA) allows students to type in their own logical sentences in plain English and then have the computer check their working when they write these in mathematical form. ILONA is an intelligent tutoring system which allows students a great deal of initiative in problem solving …
On Minimizing Hardware Overhead For Exhaustive Circuit Testability, Dimitrios Kagaris, Fillia Makedon, Spyros Tragoudas
On Minimizing Hardware Overhead For Exhaustive Circuit Testability, Dimitrios Kagaris, Fillia Makedon, Spyros Tragoudas
Computer Science Technical Reports
Exhaustive built-in self testing is given much attention as a viable technique in the context of VLSI technology. In this paper, we present heuristic in order to make exhaustive testing of combinational circuits practical. The goal is to place a small number of register cells on the nets of the input circuit so that the input dependency of combinational elements in the circuit is less than a small given integer k. Our heuristic guarantees that each output can be individually tested with 2k test patterns and can be used as a subroutine to generat efficient test patterns to test all …
A Metric Towards Efficient Exhaustive Test Pattern Generation, Dimitrios Kagaris, Fillia Makedon, Spyros Tragoudas
A Metric Towards Efficient Exhaustive Test Pattern Generation, Dimitrios Kagaris, Fillia Makedon, Spyros Tragoudas
Computer Science Technical Reports
A viable technique [7] in built-in self-test (BIST)[2] is to generate test patterns pseudo-exhaustively by using linear feedback shift registers (LFSR's). The goal is to find an appropriate primitive polynomial of degree d that will generat 2d test patterns in order to exercise all circuit outputs simultaneously. In an attempt to reduce the degree d of the polynomial the following strategy was proposed in [6,5]. In the first phase, partition the circuit into segments by inserting a small number of register cells, so that the input dependency of any circuit element in the segments is no more than d. Then, …
An Object-Oriented Learning/Design Support Environment, Fillia Makedon, Julie C. Jumes, Jill P. David
An Object-Oriented Learning/Design Support Environment, Fillia Makedon, Julie C. Jumes, Jill P. David
Computer Science Technical Reports
We present an object-oriented experimental learning and design support environment, call AVT, for an Algorithm Visualization Tool, implemented in Digitalk's Smalltalk/V1 on a Macintosh II2, AVT provides a domain- independent visualization tool, an exploratory learning environment, and an experimental heuristic design environment. Algorithm visualization is the exploration of ways to visualize intuitively the computational behavior of an algorithm using multiple views, some of which are visual in the graphical sense [2,4]. AVT employs other views (combining text and graphics) to explain the problem, the strategy, the heuristics, and the reasoning process behind the solutions. User interaction in AVT includes not …
Implementation Notes On Bdes(1), Matt Bishop
Implementation Notes On Bdes(1), Matt Bishop
Computer Science Technical Reports
This note describes the implementation of bdes, the file encryption program being distributed in the 4.4 release of the Berkeley Software Distribution. It implements all modes of the Data Encryption Standard program.
An Overview Of Computer Viruses In A Research Environment, Matt Bishop
An Overview Of Computer Viruses In A Research Environment, Matt Bishop
Computer Science Technical Reports
The threat of attack by computer viruses is in reality a very small part of a much more general threat, specifically attacks aimed at subverting computer security. This paper examines computer viruses as malicious logic in a research and development environment, relates them to various models of security and integrity, and examines current research techniques aimed at controlling the threats viruses in particular, and malicious logic in gerneral, pose to computer systems. Finally, a brief examination of the vulnerabilities of research and development systems that malicious logic and computer viruses may exploit is undertaken.
Privacy-Enhanced Electronic Mail, Matt Bishop
Privacy-Enhanced Electronic Mail, Matt Bishop
Computer Science Technical Reports
The security of electronic mail sent through the Internet may be described in exactly three words: there is none. The Privacy and Security Research Group has recommended implementing mechanisms designed to provide security enhancements. The first set of mechanisms provides a protocol to provide privacy, integrity, and authentication for electronic mail; the second provides a certificate-based key management infrastructure to support key distribution throughout the internet, to support the first set of mechanisms. This paper describes these mechanisms, as well as the reasons behind their selection and how these mechanisms can be used to provide some measure of securtiy in …
A Security Analysis Of Version 2 Of The Network Time Protocol Ntp: A Report To The Privacy And Security Research Group, Matt Bishop
Computer Science Technical Reports
The Network Time Protocol is being used throughout the Internet to provide an accurate time service. This paper examines the security requirements of such a service, analyzes version 2 of the NTP protocol to determine how well it meets these requirements, and suggests improvements where appropriate.
Optimal Parallel And Sequential Algorithms For The Vertex Updating Problem Of A Minimum Spanning Tree, Donald B. Johnson, Panagiotis Metaxas
Optimal Parallel And Sequential Algorithms For The Vertex Updating Problem Of A Minimum Spanning Tree, Donald B. Johnson, Panagiotis Metaxas
Computer Science Technical Reports
We present a set of rules that can be used to give optimal solutions to the vertex updating problem for a minimum spanning tree: Update a given MST when a new vertex z is introducted, along with weighted edges that connect z with the vertices of the graph. These rules lead to simple parallel algorithms that run in O(lg n) parallel time using n/lg n EREW PRAMs. They can also be used to derive simple linear-time sequential algorithms for the same problem. Furthermore, we show how our solution can be used to solve the multiple vertex updating problem.
Connected Components In O(Lg3/2|V|) Parallel Time For The Crew Pram, Donald B. Johnson, Panagiotis Metaxas
Connected Components In O(Lg3/2|V|) Parallel Time For The Crew Pram, Donald B. Johnson, Panagiotis Metaxas
Computer Science Technical Reports
Computing the connected components of an undirected graph G = (V,E) on |V| = n vertices and |E| = m edges is a fundamental computational problem. The best known parallel algorithm for the CREW PRAM model runs on O(lg2n) time using n2/lg2n processors [CLC82,HCS79]. For the CRCW PRAM model in which concurrent writing is permitted, the best known algorithm runs in O(lg n) time using almost (n+m)/lg n processors [SV82,CV86,AS87]. Unfortunately, simulating this algorithm on the weaker CREW model increases its running time to O(lg2n) [CDR86, KR90,Vis83]. We present here an efficient and simple algorithm that runs in O(lg 3/2n) …
Multipacket Routing On Rings, Fillia Makedon, Adonios Simvonis
Multipacket Routing On Rings, Fillia Makedon, Adonios Simvonis
Computer Science Technical Reports
We study multipacket routing problems. We divide the multipacket routing problem into two classes, namely, distance limited and bisection limited routing problems. Then, we concentrate on rings of processors. Having a full understanding of the multipacket routing problem on rings is essential before trying to attack the problem for the more general case of r-dimensional meshes and tori. We prove a new lower bound of 2n/3 routing steps for the case of distance limited routing problems. We also give an algorithm that tightens this lower bound. For bisection limited problems, we present an algorithm that completes the routing in near …
A Parallel Algorithm For The Minimum Spanning Tree, Donald B. Johnson, Panagiotis Metaxas
A Parallel Algorithm For The Minimum Spanning Tree, Donald B. Johnson, Panagiotis Metaxas
Computer Science Technical Reports
No abstract provided.