home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / reports / bibs.refer.2010-05-11 < prev    next >
Text File  |  2010-05-11  |  147KB  |  3,049 lines

  1.  
  2. %A  Madhavan, Arun
  3. %A  Zhang, Beichuan
  4. %T NAT Traversal by Tunneling
  5. %D May 11, 2010
  6. %Z Tue, 11 May 10 11:34:31 MST
  7. %R TR10-01
  8. %I The Department of Computer Science, University of Arizona
  9. %U ftp://ftp.cs.arizona.edu/reports/2010
  10. %X Network Address Translation (NAT) is widely prevalent solution adopted to
  11. alleviate the IPv4 address exhaustion problem. Due to the use of private IP
  12. addresses on hosts behind the NAT, it is not possible for external hosts to
  13. initiate communication with these hosts. This poses a hurdle to many
  14. emerging applications, such as VoIP and P2P. Although a plethora of NAT
  15. traversal solutions have been proposed in recent years, they suffer
  16. from being application-specific, complex, or requiring some behavioral
  17. compliance from the NAT.
  18. The work presents an simple technique that is generic, works with nested
  19. NATs, is incrementally deployable and only expects minimalistic common
  20. behavior across all NAT implementations. The design includes the use of UDP
  21. tunnels and a sequence of NAT addresses and private IP addresses to uniquely
  22. identify a host. Simple and incrementally deployable changes are proposed to
  23. DNS to learn the addresses.
  24. %K 
  25. %Y
  26.  
  27. %A Fowler, Joe
  28. %A Kobourov, Stephen
  29. %A Estrella-Balderrama, Alejandro
  30. %T Colored Simultaneous Geometric Embeddings and Universal Pointsets
  31. %D 5/14/09
  32. %Z Mon, 05 Jan 09 00:00:00 GMT
  33. %R TR09-02
  34. %I The Department of Computer Science, University of Arizona
  35. %U ftp://ftp.cs.arizona.edu/reports/2009/TR09-02.pdf
  36. %X Universal pointsets can be used for visualizing multiple relationships on
  37. the same set of objects or for visualizing dynamic graph processes. Using the
  38. same point in the plane to represent the same object helps preserve the
  39. viewer.s mental map. Small universal pointsets are highly desirable but often
  40. do not exist because of the restriction that a given object must be mapped
  41. to a fixed point in the plane. In colored simultaneous embeddings this
  42. restriction is relaxed, by allowing a given object to map to a subset of
  43. points in the plane. Specifically, consider a set of graphs on the same set
  44. of n vertices partitioned into k colors. Finding a corresponding set of
  45. k-colored points in the plane in which each vertex is mapped to a point of
  46. the same color so as to allow a straight-line plane drawing of each graph
  47. is the problem of colored simultaneous geometric embedding. For trees, we
  48. show that there exists small universal pointsets (1) for 3-colored
  49. caterpillars of size n, (2) for 3-colored radius-2 stars of size n+3, and
  50. (3) for 2-colored spiders of size n. For outerplanar graphs, we show that
  51. these same universal pointsets also suffice for (1) 3-colored K3-caterpillars,
  52. (2) 3-colored K3-stars, and (3) 2-colored fans, respectively. We also show
  53. that there exist (i) a 2-colored planar graph and pseudo-forest, (ii) three
  54. 3-colored outerplanar graphs, (iii) four 4-colored pseudo-forests, and (iv)
  55. three 5-colored pseudo-forests without simultaneous embeddedings.
  56. %K keywords
  57. %Y
  58.  
  59. %A Perkins, David N.
  60. %T Predicting Secondary Structure of Proteins by Linear and Dynamic Programming
  61. %D April 29, 2009
  62. %Z Mon, 05 Jan 09 00:00:00 GMT
  63. %R TR09-01
  64. %I The Department of Computer Science, University of Arizona
  65. %U ftp://ftp.cs.arizona.edu/reports/2009/TR09-01.pdf
  66. %X Proteins are sequences of amino acids that fold into secondary and tertiary structure, which plays an important role in their function. As biologists have yet to discover the rules that govern how a protein folds in nature from its underlying sequence, this thesis tries a new approach to secondary structure prediction using dynamic programming on the input protein sequence. The sequence is broken into short words, where each word has a probability of folding into the three different types of secondary structure. By combining word probabilities with an abstraction called contexts, which model a run of the same secondary structure type up to a bounded length, the optimal prediction for an entire sequence can be computed via dynamic programming. The structure probabilities for words are learned from a training set of sequences with known secondary structure using linear programming. The combined approach to prediction using linear and dynamic programming achieves high accuracy on protein sequences whose words were observed in the training set, but is far less accurate on sequences with unobserved words not seen in the training set. The challenge for future work lies in interpolating probabilities for unobserved words to achieve improved generalization.
  67. %K keywords
  68. %Y
  69.  
  70. %A Huang, Huilong
  71. %T Efficient Routing in Wireless Ad Hoc Networks
  72. %D August 12, 2008
  73. %Z Mon, 03 Jan 08 00:00:00 GMT
  74. %R TR08-05
  75. %I The Department of Computer Science, University of Arizona
  76. %U ftp://ftp.cs.arizona.edu/reports/2008/TR08-05.pdf
  77. %X abstract (see TR)
  78. %K dissertation
  79. %Y
  80.  
  81. %A Cappos, Justin
  82. %T Stork: Secure Package Management for VM Environments
  83. %D May 6, 2008
  84. %Z Mon, 03 Jan 08 00:00:00 GMT
  85. %R TR08-04
  86. %I The Department of Computer Science, University of Arizona
  87. %U ftp://ftp.cs.arizona.edu/reports/2008/TR08-04.pdf
  88. %X Package managers are a common tool for installing, removing, and
  89. updating software on modern computer systems. Unfortunately existing
  90. package managers have two major problems. First, inadequate security
  91. leads to vulnerability to attack. There are nine feasible attacks against
  92. modern package managers, many of which are enabled by flaws in the
  93. underlying security architecture. Second, in Virtual Machine (VM)
  94. environments such as Xen, VMWare, and VServers, different VMs on the
  95. same physical machine are treated as separate systems by package managers
  96. leading to redundant package downloads and installations.
  97.      This dissertation focuses on the design, development, and evaluation of
  98. a package manager called Stork that does not have these problems. Stork
  99. provides a security architecture that prevents the attacks other package
  100. managers are vulnerable to. Stork also is efficient in VM environments
  101. and reduces redundant package management actions.   Stork is a real system
  102. that has been in use for four years and has managed half a million VM
  103. instantiations.
  104. %K dissertation, Stork
  105. %Y
  106.  
  107. %A Collberg, Christian
  108. %A Nagra, Jasvir
  109. %A Snavely, Will
  110. %T bi`anli.an: Remote Tamper-Resistance with Continuous Replacement
  111. %D March 31, 2008
  112. %Z Mon, 03 Jan 08 00:00:00 GMT
  113. %R TR08-03
  114. %I The Department of Computer Science, University of Arizona
  115. %U ftp://ftp.cs.arizona.edu/reports/2008/TR08-03.pdf
  116. %X In this paper we describe bi`anli.an, a system for producing
  117. tamper-resistant clients programs running over the Internet. The basic
  118. idea is to use continuous replacement of program blocks running on the
  119. client site to make it difficult for an adversary to analyze and modify
  120. the program. There are many potential applications, for example protecting
  121. client programs in networked computer games from being tampered with.
  122. We show the basic design of a continuous replacement system for Java,
  123. including a number of obfuscating and tamperproofing transformations. In
  124. achieving tamper-resistance bi`anli.an incorporates two novel ideas. First,
  125. it maintains an incorrect pool of code on the client such that no snapshot
  126. that an adversary takes contains the complete correct program. In addition,
  127. the type of incorrect code introduced ensures that on different input,
  128. executing the same trace of instructions will produce incorrect results.
  129. Secondly, bi`anli.an achieves scalability through a distributed protection
  130. scheme which allows the server to offload the tamper-detection of one client
  131. to another client.
  132. %K bi`anli.an, tamperproofing, tamper-detection
  133. %Y
  134.  
  135. %A Fowler, Joe
  136. %A Junger, Michael
  137. %A Kobourov, Stephen
  138. %A Schulz, Michael
  139. %T Characterizing Simultaneous Embedding with Fixed Edges
  140. %D February 8, 2008
  141. %Z Mon, 01 Jan 08 00:00:00 GMT
  142. %R TR08-01
  143. %I The Department of Computer Science, University of Arizona
  144. %U ftp://ftp.cs.arizona.edu/reports/2008/TR08-01.ps.Z
  145. %X A set of planar graphs share a simultaneous embedding if they can be
  146. drawn on the same vertex set V in the plane without crossings between edges
  147. of the same graph. Fixed edges are common edges between graphs that share
  148. the same Jordan curve in the simultaneous drawings.While any number of planar
  149. graphs have a simultaneous embedding without fixed edges, determining which
  150. graphs always share a simultaneous embedding with fixed edges (SEFE) has
  151. been open.
  152. We partially close this problem by giving a necessary condition
  153. to determine when pairs of graphs have a SEFE. As a direct application, we
  154. are able to determine for the set of planar graphs P and for the set of
  155. outerplanar graphs O (all vertices lie on an outerface), what the proper
  156. subsets of P and O are that always have a SEFE with all of P and O,
  157. respectively. In both cases, we provide algorithms to compute the
  158. simultaneous drawings. Finally, we provide a polynomial time decision
  159. algorithm for deciding when a specific pair of outerplanar graphs has
  160. a SEFE. Whether two planar graphs have a SEFE can similarly be decided
  161. in polynomial time remains as an open problem.
  162. %K SEFE, vertex, Jordan curve
  163. %Y
  164.  
  165. %A Cappos, Justin
  166. %A Donnelly, Austin
  167. %A Mortier, Richard
  168. %A Narayanan, Dushyanth
  169. %A Rowstron, Antony
  170. %T Cost-aware view materialization for highly distributed datasets
  171. %D Thursday, September 13, 2007
  172. %Z Mon, 03 Jan 05 00:00:00 GMT
  173. %R TR07-05
  174. %I The Department of Computer Science, University of Arizona
  175. %U ftp://ftp.cs.arizona.edu/reports/2007/TR07-05.pdf
  176. %X Querying large datasets distributed over thousands of endsystems is a
  177. challenge for existing distributed querying infrastructures. High data
  178. availability requires either replicating or centralizing the dataset but
  179. both require infeasibly high network bandwidth. In-situ querying provides
  180. low bandwidth overheads but requires users to tolerate low data availability.
  181.      This paper advocates partial data replication, increasing the availability
  182. of a subset of the data through centralization and/or in-network (peer-to-peer)
  183. replication. This is analogous to materializing views in centralized
  184. databases, but where materialized views in centralized databases trade view
  185. update overheads for query overheads, in the distributed case they trade
  186. bandwidth usage for availability. Given an example workload, state-of-the-art
  187. tools for centralized databases are able to determine a set of materialized
  188. views that will improve performance. Key to this is the ability to estimate
  189. view maintenance costs with different hypothetical materialized views. This
  190. paper describes estimation of view maintenance costs in a highly distributed
  191. database. We present metrics that capture the cost of different
  192. materializations, and show that we can estimate these metrics accurately,
  193. efficiently, and scalably on a real distributed dataset.
  194. %K keywords
  195. %Y
  196.  
  197. %A Cappos, Justin
  198. %A Baker, Scott
  199. %A Plichta, Jeremy
  200. %A Nyugen, Duy
  201. %A Hardies, Jason
  202. %A Borgard, Matt
  203. %A Johnston, Jeffry
  204. %A Hartman, John H.
  205. %T Stork: Package Management for Dstributed VM Environments
  206. %D Tuesday, May 15, 2007
  207. %Z Tues, 02 Jan 07 00:00:00 GMT
  208. %R TR07-02
  209. %I The Department of Computer Science, University of Arizona
  210. %U ftp://ftp.cs.arizona.edu/reports/2007/TR07-02.ps.Z
  211. %X In virtual machine environments each application is often run in its
  212. own virtual machine (VM), isolating it from other applications running
  213. on the same physical machine.  Contention for memory, disk space, and
  214. network bandwidth among virtual machines, coupled with an inability to
  215. share due to the isolation virtual machines provide, leads to heavy
  216. resource utilization.  Additionally, VMs increase management overhead
  217. as each is essentially a separate system.
  218.         Stork is a package management tool for virtual machine environments
  219. that is designed to alleviate these problems.  Stork securely and
  220. efficiently downloads packages to physical machines and shares packages
  221. between VMs.  Disk space and memory requirements are reduced because shared
  222. files, such as libraries and binaries, only require one persistent copy per
  223. physical machine.  Experiments show that Stork reduces the disk space
  224. required to install additional copies of a package by over an order of
  225. magnitude, and memory by about 50\%.  Stork downloads each package once
  226. per physical machine no matter how many VMs install it.   The transfer
  227. protocols used during download improve elapsed time by 7X and reduce
  228. repository traffic by an order of magnitude.   Stork users can manage groups
  229. of VMs with the ease of managing a single machine -- even groups that
  230. consist of machines distributed around the world.  Stork is a real service
  231. that has run on PlanetLab for over 4 years and has managed thousands of VMs.
  232. %K keywords
  233. %Y
  234.  
  235. %A Cappos, Justin
  236. %A Hartman, John H.
  237. %T San Fermin: Aggregating Large Data Sets using Dynamic Binomial Trees
  238. %D Monday, May 14, 2007
  239. %Z Tues, 02 Jan 07 00:00:00 GMT
  240. %R TR07-01
  241. %I The Department of Computer Science, University of Arizona
  242. %U ftp://ftp.cs.arizona.edu/reports/2007
  243. %X This paper presents San Fermin, a system for aggregating large data 
  244. sets from the nodes of large-scale distributed systems. Each San Fermin 
  245. node individually computes the aggregated result by dynamically creating 
  246. its own binomial tree as it aggregates data. Nodes that fall behind abort 
  247. their aggregations, thereby reducing overhead. Having each node create its 
  248. own binomial tree makes San Fermin highly resilient to failures, and ensures
  249. that the internal nodes of the tree have high capacity, reducing completion
  250. time without overwhelming nodes.
  251.         Compared to existing solutions San Fermin handles large data sets 
  252. better, has higher completeness when nodes fail, computes the aggregated 
  253. result faster, and has better scalability. We analyze the completion time, 
  254. completeness, and overhead of San Fermin versus existing solutions using 
  255. analytical models, simulation, and experimentation with a prototype deployed 
  256. on PlanetLab. Our evaluation shows that San Fermin is scalable both in the 
  257. number of nodes and in the size of the data being aggregated. With 10% 
  258. node failures during aggregation, San Fermin still returns the answer from 
  259. over 97% of the nodes and in most cases does so faster than the underlying DHT recovers from failures.
  260. %K keywords
  261.  
  262. %A Fowler, J. Joseph
  263. %A Kobourov, Stephen G.
  264. %T Characterization of Unlabeled Level Planar Graphs
  265. %D Monday, December 4, 2006
  266. %Z Mon, 03 Jan 06 00:00:00 GMT
  267. %R TR06-04
  268. %I The Department of Computer Science, University of Arizona
  269. %U ftp://ftp.cs.arizona.edu/reports/2006/TR06-04.ps.Z
  270. %X abstract
  271. %K keywords
  272. %Y
  273.  
  274. %A Zhang, Beichuan
  275. %A Kambhampati, Vamsi
  276. %A Massey, Daniel
  277. %A Oliveira, Ricardo
  278. %A Pei, Dan
  279. %A Wang, Lan
  280. %A Zhang, Lixia
  281. %T A Secure and Scalable Internet Routing Architecture (SIRA)
  282. %D Tuesday, April 4, 2006
  283. %Z Mon, 03 Jan 06 00:00:00 GMT
  284. %R TR06-01
  285. %I The Department of Computer Science, University of Arizona
  286. %U ftp://ftp.cs.arizona.edu/reports/2006/TR06-01.ps.Z
  287. %X Today's Internet routing architecture faces many challenges, ranging
  288. from scaling problems, security threats, poor fault diagnosis to inadequate
  289. support for traffic engineering and customer multihoming.  By analyzing
  290. these  challenges and learning lessons from previously proposed solutions,
  291. we gain two fundamental insights for designing a secure and scalable
  292. routing architecture: cutting a clear boundary between customer networks
  293. and transit  providers, and embedding essential information in the
  294. address structure.  We propose the Secure and Scalable Internet Routing
  295. Architecture  (SIRA), a clean-slate design that separates provider
  296. networks from customer  networks and embeds organization and location
  297. information in address structure.
  298. The resulting system provides dramatic improvements in scalability, security,
  299. fault diagnosis, and multihoming and traffic engineering support. We also
  300. identify new design issues raised by SIRA and sketch out straw-man solutions.
  301. %K keyword
  302. %Y
  303.  
  304. %A Rao, Praveen
  305. %A Moon, Bongki
  306. %T psiX: Hierarchical Distributed Index for Efficiently Locating XML Data
  307. in Peer-to-Peer Networks
  308. %D Monday, March 13, 2006
  309. %Z Mon, 03 Jan 05 00:00:00 GMT
  310. %R TR05-10
  311. %I The Department of Computer Science, University of Arizona
  312. %U ftp://ftp.cs.arizona.edu/reports/
  313. %X This report has been superseded by a UMKC-TR
  314. %K keywords
  315. %Y 
  316.  
  317. %A Barnard, Kobus
  318. %A Fan, Quanfu
  319. %A Swaminathan, Ranjini
  320. %A Hoogs, Anthony
  321. %A Collins, Roderic
  322. %A Rondot, Pascale
  323. %A Kaufhold, John
  324. %T Evaluation of localized semantics: data, methodology, and experiments
  325. %D Monday, October 31, 2005
  326. %Z Mon, 03 Jan 05 00:00:00 GMT
  327. %R TR05-08
  328. %I The Department of Computer Science, University of Arizona
  329. %U ftp://ftp.cs.arizona.edu/reports/2005/TR05-08.ps
  330. %X We present a new data set encoding localized semantics for 1014 images and a
  331. methodology for using this kind of data for recognition evaluation. This
  332. methodology establishes protocols for mapping algorithm specific localization
  333. (e.g., segmentations) to our data, handling synonyms, scoring matches at
  334. different levels of specificity, dealing with vocabularies with sense ambiguity
  335. (the usual case), and handling ground truth regions with multiple labels. Given
  336. these protocols, we develop two evaluation approaches. The first measures the
  337. range of semantics that an algorithm can recognize, and the second measures the
  338. frequency that an algorithm recognizes semantics correctly. The data, the image
  339. labeling tool, and programs implementing our evaluation strategy are all
  340. available on-line (kobus.ca//research/data/IJCV).
  341.     We apply this infrastructure to evaluate four algorithms which learn to
  342. label image regions from weakly labeled data. The algorithms tested include two
  343. variants of multiple instance learning, and two generative multi-modal mixture
  344. models. These experiments are on a significantly larger scale than previously
  345. reported, especially in the case of the multiple instance learning. More
  346. specifically, we used training data sets up to 37,000 images and training
  347. vocabularies of up to 650 words.
  348.     We found that image level word prediction, which is a cheaper evaluation
  349. alternative, does not correlate well with region labeling performance, thus
  350. validating the need for region level analysis. We also found that for the
  351. measures sensitive to occurrence statistics, we needed to provide the multiple
  352. instance learning methods with an appropriate prior for good performance. With
  353. that modification used when appropriate, we found that the EMDD multiple
  354. instance learning method gave the best overall performance over three tasks,
  355. with one of the generative multi-mixture models giving the best performance on
  356. one of them.
  357. %K keywords
  358. %Y
  359.  
  360. %A Kobourov, Stephen
  361. %A Iyer, Anand
  362. %A Efrat, Alon
  363. %A Erten, Cesim
  364. %A Forrester, David
  365. %T A Force-Directed Approach to Sensor Localization
  366. %D Friday, July 15, 2005
  367. %Z Mon, 03 Jan 05 00:00:00 GMT
  368. %R TR05-07
  369. %I The Department of Computer Science, University of Arizona
  370. %U ftp://ftp.cs.arizona.edu/reports/2005/TR05-07.ps
  371. %X abstract
  372. %K keywords
  373. %Y
  374.  
  375. %A Kobourov, Stephen
  376. %A Cappos, Justin
  377. %T Outerplanar Graphs and Trees on Tracks
  378. %D Friday, July 15, 2005
  379. %Z Mon, 03 Jan 05 00:00:00 GMT
  380. %R TR05-06
  381. %I The Department of Computer Science, University of Arizona
  382. %U ftp://ftp.cs.arizona.edu/reports/2005/TR05-06.ps
  383. %X abstract
  384. %K keywords
  385. %Y
  386.  
  387. %A Kobourov, Stephen
  388. %A Landis, Matthew
  389. %T Morphing Planar Graphs in Spherical Space
  390. %D Friday, July 15, 2005
  391. %Z Mon, 03 Jan 05 00:00:00 GMT
  392. %R TR05-05
  393. %I The Department of Computer Science, University of Arizona
  394. %U ftp://ftp.cs.arizona.edu/reports/2005/TR05-05.ps
  395. %X abstract
  396. %K keywords
  397. %Y
  398.  
  399. %A Collberg, Christian
  400. %A Kobourov, Stephen
  401. %A Hutcheson, C.
  402. %A Trimble, J.
  403. %A Stepp, Michael
  404. %T Monitoring Java Programs Using Music
  405. %D Wednesday, June 15, 2005
  406. %Z Mon, 03 Jan 05 00:00:00 GMT
  407. %R TR05-04
  408. %I The Department of Computer Science, University of Arizona
  409. %U ftp://ftp.cs.arizona.edu/reports/2005/TR05-04.ps.Z
  410. %X    We present jmusic, a tool to analyze the run-time behavior of
  411. a Java program.  Unlike other profiling systems, this one presents
  412. its results to the user as {\em music}. Using audio in addition to more
  413. standard visual methods of presentation allows more attempt at presenting
  414. profiling information as computer-generated music. The tool is
  415. specification-driven, allowing users complete control over what profiling
  416. information to present, and what type of (MIDI) music to generate for
  417. different situations.  We discuss the system design and implementation,
  418. as well as present several examples.
  419. %K jmusic, run-time, Java
  420. %Y
  421.  
  422. %A Rajagopolan, Mohan
  423. %A Debray, Saumya
  424. %A Hiltunen, Matti
  425. %A Schlichting, Richard
  426. %T Automatic Operating System Specialization via Binary Rewriting
  427. %D Monday, May 9, 2005
  428. %Z Mon, 03 Jan 05 00:00:00 GMT
  429. %R TR05-03
  430. %I The Department of Computer Science, University of Arizona
  431. %U ftp://ftp.cs.arizona.edu/reports/2005/TR05-03.ps.Z
  432. %X This paper explores the application of binary rewriting techniques
  433. to customization of operating system kernels. Specifically, this paper
  434. describes a new binary rewriting system, {\it Charon}, and its
  435. application to the synthesis of application-specific operating systems.
  436. Compiler techniques are used to analyze and transform the kernel
  437. based on holistic knowledge of the system. Preliminary experiments
  438. have been promising and argue persuasively that more
  439. opportunities for automation should be explored.
  440. %K keywords
  441. %Y
  442.  
  443. %A Cappos, Justin
  444. %A Hartman, John
  445. %T A Resource Allocation Framework for Global Service-Oriented Networks
  446. %D Thursday, February 24, 2005
  447. %Z Mon, 03 Jan 05 00:00:00 GMT
  448. %R TR05-02
  449. %I The Department of Computer Science, University of Arizona
  450. %U ftp://ftp.cs.arizona.edu/reports/2005/TR05-02.ps
  451. %X We study the problem of allocating resources on global networks where there
  452. is no central administrative control.   We describe a framework that
  453. abstractly describes a number of components that are necessary in an
  454. auction system to provide users with a secure trading environment.   We
  455. propose solutions for specific issues relating to auction granularity,
  456. cost/value effective bidding, bids on large resource sets, currency
  457. control, and computationally effective auction resolution.   We then
  458. describe the application of our framework to PlanetLab and how the
  459. components would be implemented on this system.
  460. %K keywords
  461. %Y
  462.  
  463. %A Rajagopalan, Mohan
  464. %A Baker, Scott
  465. %A Debray, Saumya K.
  466. %A Hiltunen, Matti
  467. %A Schlichting, Richard D.
  468. %A Hartman, John
  469. %T System Call Signatures and Hidden Fingerprints
  470. %D Wednesday, December 22, 2004
  471. %Z Wed, 03 Jan 04 00:00:00 GMT
  472. %R TR04-15
  473. %I The Department of Computer Science, University of Arizona
  474. %U ftp://ftp.cs.arizona.edu/reports/2004
  475. %X Remote code injection attacks against computer systems
  476. are occurring at an alarming frequency. A crucial aspect
  477. of such attacks is that in order to do any real damage,
  478. the injected attack code has to execute system calls, and
  479. therefore can be foiled by suitably hardening the system
  480. call interface. Most current proposals for doing so, however,
  481. suffer from various shortcomings, such as relying
  482. on special compilers or libraries, or incurring huge runtime
  483. overheads, or being vulnerable to mimicry attacks.
  484. This paper describes a systematic approach to defending
  485. against remote code injection attacks that uses two complementary
  486. techniques: cryptographic signatures to protect
  487. system calls themselves, and compiler-based techniques
  488. to hide code fingerprints that could be exploited
  489. for mimicry attacks. Experiments indicate that our approach
  490. is effective against a wide variety of attacks at
  491. modest cost.
  492. %K keywords
  493. %Y
  494.  
  495. %A Barnard, Kobus
  496. %A Johnson, Matthew
  497. %T Word Sense Disambiguation with Pictures
  498. %D Monday, August 9, 2004
  499. %Z Wed, 03 Jan 04 00:00:00 GMT
  500. %R TR04-12
  501. %I The Department of Computer Science, University of Arizona
  502. %U ftp://ftp.cs.arizona.edu/reports/2004/
  503. %X We introduce using images for word sense disambiguation, either alone, or
  504. in conjunction with traditional text based methods. The approach is based on
  505. a recently developed method for automatically annotating images by using a
  506. statistical model for the joint probability for image regions and words.
  507. The model itself is learned from a data base of images with associated text.
  508. To use the model for word sense disambiguation, we constrain the predicted
  509. words to be possible senses for the word under consideration. When word
  510. prediction is constrained to a narrow set of choices (such as possible senses),
  511. it can be quite reliable.  We report on experiments using the resulting
  512. sense probabilities as is, as well as augmenting a state of the art text
  513. based word sense disambiguation algorithm.  In order to evaluate our approach,
  514. we developed a new corpus, ImCor, which consists of a substantive portion
  515. of the Corel image data set associated with disambiguated text drawn from the
  516. SemCor corpus. Our experiments using this corpus suggest that visual
  517. information can be very useful in disambiguating word senses. It also
  518. illustrates that associated non-textual information such as image data can
  519. help ground language meaning.
  520. Please note: This TR has been superseeded by the
  521. http://kobus.ca/research/publications/AIJ-WSD AIJ version.
  522. %K keywords
  523. %Y
  524.  
  525. %A Collberg, Christian
  526. %A Myles, Ginger
  527. %A Stepp, Michael
  528. %T An Empirical Study of Java Bytecode Programs
  529. %D Thursday, August 5, 2004
  530. %Z Wed, 03 Jan 04 00:00:00 GMT
  531. %R TR04-11
  532. %I The Department of Computer Science, University of Arizona
  533. %U ftp://ftp.cs.arizona.edu/reports/2004/TR04-11.ps
  534. %X We present a study of the static structure of real Java bytecode
  535. programs. A total of 1132 Java jar- les were collected from the Internet
  536. and analyzed. In addition to simple counts (number of methods per class,
  537. number of bytecode instructions per method, etc.), structural metrics such
  538. as the complexity of control- ow and inheritance graphs were computed. We
  539. believe this study will be valuable in the design of future programming
  540. languages and virtual machine instruction sets, as well as in the ef cient
  541. implementation of compilers and other language processors.
  542. %K keywords
  543. %Y
  544.  
  545. %A Collberg, Christian
  546. %A Proebsting, Todd A.
  547. %T AlgoVista - A Tool for Classifying Algorithmic Problems and Combinatorial
  548. Structures
  549. %D Wed, April 28, 2004
  550. %Z Wed, 03 Jan 04 00:00:00 GMT
  551. %R TR04-09
  552. %I The Department of Computer Science, University of Arizona
  553. %U ftp://ftp.cs.arizona.edu/reports/2004
  554. %X AlgoVista is a web-based search engine that assists programmers to
  555. classify algorithmic problems and combinatorial structures.  AlgoVista is
  556. not keyword based but rather requires users to provide --- in a very simple
  557. query language ---  input==>output samples that give a rough description of
  558. the behavior of their needed algorithm.  AlgoVista also allows algorithm
  559. designers to advertise their results in a forum accessible to programmers
  560. and theoreticians alike.
  561.      AlgoVista's search mechanism is based on a novel application of program
  562. checking, a technique developed as an alternative to program verification and
  563. testing.
  564.      The current AlgoVista database consists of over 300 problem descriptions
  565. including problems on graphs, trees, matrices, vectors, sets, numbers, and
  566. geometric objects.
  567.      AlgoVista can be searched textually as well as visually. A user creates
  568. a visual query by simply drawing it on the canvas of a web browser. Visual
  569. queries are parsed into their textual counter-part by an algorithm that
  570. relies on user input to resolve ambiguities.
  571.      AlgoVista operates at http://algovista.cs.arizona.edu.
  572. %K keywords
  573. %Y
  574.  
  575. %A Collberg, Christian
  576. %A Thomborson, Clark
  577. %A Townsend, Gregg M.
  578. %T Dynamic Graph-Based Software Watermarking
  579. %D Wed, April 28, 2004
  580. %Z Wed, 03 Jan 04 00:00:00 GMT
  581. %R TR04-08
  582. %I The Department of Computer Science, University of Arizona
  583. %U ftp://ftp.cs.arizona.edu/reports/2004/TR04-08.ps
  584. %X Watermarking embeds a secret message into a cover message. In media
  585. watermarking the secret is usually a copyright notice and the cover a
  586. digital image. Watermarking an object discourages intellectual property
  587. theft, or when such theft has occurred, allows us to prove ownership.
  588.      The Software Watermarking problem can be described as follows. Embed
  589. a structure $W$ into a program $P$ such that: $W$ can be reliably located
  590. and extracted from $P$ even after $P$ has been subjected to code
  591. transformations such as translation, optimization and obfuscation; $W$
  592. is stealthy; $W$ has a high data rate; embedding $W$ into $P$ does not
  593. adversely affect the performance of $P$; and $W$ has a mathematical property
  594. that allows us to argue that its presence in $P$ is the result of deliberate
  595. actions.
  596.      In this paper we describe a software watermarking technique in which
  597. a dynamic graph watermark is stored in the execution state of a program.
  598. Because of the hardness of pointer alias analysis such watermarks are
  599. difficult to attack automatically.
  600. %K keywords
  601. %Y
  602.  
  603. %A Sahoo, Tapas Ranjan
  604. %A Collberg, Christian
  605. %T Software Watermarking in the Frequency Domain: Implementation, Analysis, and
  606. Attacks
  607. %D Wednesday, March 3, 2004
  608. %Z Wed, 03 Jan 04 00:00:00 GMT
  609. %R TR04-07
  610. %I The Department of Computer Science, University of Arizona
  611. %U ftp://ftp.cs.arizona.edu/reports/2004/TR04-07.ps.Z
  612. %X In this paper we analyze the \SHKQ\ software watermarking algorithm,
  613. originally due to Stern, Hachez, Koeune and Quisquater.  The algorithm has
  614. been implemented within the \SM\ framework, a system designed to allow
  615. effective study of software protection algorithms (such as code obfuscation,
  616. software watermarking, and code tamper-proofing) targeting Java bytecode.
  617.    The SHKQ algorithm embeds a watermark in a program using a spread spectrum
  618. technique. The idea is to spread the watermark over the entire application by
  619. modifying instruction frequencies. Spreading the watermark over the code
  620. provides a high level of stealth and some manner of resilience against attack.
  621.    In this paper we describe the implementation of the \SHKQ\ algorithm, in
  622. particular the issues that arise when targeting Java bytecodes.  We then
  623. present an empirical examination of the robustness of the watermark against
  624. a wide variety of attacks. We conclude that \SHKQ, while stealthy, is easily
  625. attacked by simple distortive transformations.
  626. %K keywords
  627. %Y
  628.  
  629. %A Collberg, Christian
  630. %A Huntwork, Andrew
  631. %A Carter, Edward
  632. %A Townsend, Gregg
  633. %T Graph Theoretic Software Watermarks: Implementation, Analysis, and Attacks
  634. %D Wednesday, March 3, 2004
  635. %Z Wed, 03 Jan 04 00:00:00 GMT
  636. %R TR04-06
  637. %I The Department of Computer Science, University of Arizona
  638. %U ftp://ftp.cs.arizona.edu/reports/2004/TR04-06.ps.Z
  639. %X This paper presents an implementation of the novel watermarking method
  640. proposed by Venkatesan, Vazirani, and Sinha in their recent paper
  641. {\em A Graph Theoretic Approach to Software Watermarking}.  An executable
  642. program is marked by the addition of code for which the topology of the
  643. control-flow graph encodes a watermark.  We discuss issues that were
  644. identified during construction of an actual implementation that operates
  645. on Java bytecode.  We measure the size and time overhead of watermarking,
  646. and evaluate the algorithm against a variety of attacks.
  647. %K keywords
  648. %Y
  649.  
  650. %A Collberg, Christian
  651. %A Myles, Ginger
  652. %A Stepp, Michael
  653. %T Cheating Cheating Detectors
  654. %D Wednesday, March 3, 2004
  655. %Z Wed, 03 Jan 04 00:00:00 GMT
  656. %R TR04-05
  657. %I The Department of Computer Science, University of Arizona
  658. %U ftp://ftp.cs.arizona.edu/reports/2004/TR04-05.ps.Z
  659. %X In this paper we present a new cheating technique that is successful at
  660. defeating cheating detectors and could become popular with students. The
  661. idea is to use obfuscating code transformations (such as those found in the
  662. \SM\ tool) to apply a sequence of minor code transformations to a copied
  663. programming assignment. This purpose is to produce a copy that will defeat
  664. detection. We show that this technique is successful in defeating common
  665. plagiarism detectors such as Moss.
  666.    This paper is offered as a cautionary tale to the Computer Science
  667. teaching community. With the advent of powerful code transformation tools
  668. it will become necessary to develop correspondingly more powerful cheating
  669. detectors, or to revert back to manually testing for plagiarism.
  670. %K keywords
  671. %Y
  672.  
  673. %A Rao, Praveen
  674. %A Moon, Bongki
  675. %T Approximate Tree Pattern Counts over (Streaming) Labeled Trees
  676. %D Thursday, July 7, 2005
  677. %Z Wed, 03 Jan 04 00:00:00 GMT
  678. %R TR04-04
  679. %I The Department of Computer Science, University of Arizona
  680. %U ftp://ftp.cs.arizona.edu/reports/2004/TR04-04.ps.Z
  681. %X There has been a growing interest in developing online approximation
  682. algorithms for data streams that use only limited amounts of memory.
  683. With XML emerging as a standard for data interchange on the Internet, we
  684. believe that the problem of counting twig patterns over streaming XML is
  685. worth addressing.  In this paper, we address the problem of approximately
  686. counting twig patterns over a stream of XML document trees that are looked
  687. at only once and appear in a fixed order. We propose a novel approximation
  688. algorithm called k-TwigSketch that computes a synopsis of the stream in one
  689. pass using a limited amount of memory.  k-TwigSketch provides approximate
  690. answers for twig counts with provably strong error guarantees.  Furthermore,
  691. we propose an effective optimization called SHUFFLE that can be applied to
  692. k-TwigSketch to reduce the memory requirements for estimating twig counts
  693. with a particular relative error guarantee. Experimental results on real
  694. and synthetic datasets demonstrate that k-TwigSketch can estimate twig
  695. counts within 10% relative errors with high confidence by using small amounts
  696. of memory. Further, we observed that the proposed optimization SHUFFLE can
  697. achieve significant memory reduction.
  698. %K updated
  699. %Y
  700.  
  701. %A Heffner, Kelly
  702. %A Collberg, Christian
  703. %T The Obfuscation Executive
  704. %D Friday, February 27, 2004
  705. %Z Wed, 03 Jan 04 00:00:00 GMT
  706. %R TR04-03
  707. %I The Department of Computer Science, University of Arizona
  708. %U ftp://ftp.cs.arizona.edu/reports/2004/TR04-03.ps.Z
  709. %X Code obfuscations are semantics-preserving code transformations used to
  710. protect a program from reverse engineering.  There is generally no expectation
  711. of complete, long-term, protection. Rather, there is a trade-off between the
  712. protection afforded by an obfuscation (i.e. the amount of resources an
  713. adversary has to expend to overcome the layer of confusion added by the
  714. transformation) and the resulting performance overhead.
  715.   An obfuscation tool will generally apply a series of obfuscation algorithms
  716. to the same application. While each individual obfuscation may add a trivial
  717. amount of confusion, the layering of and interaction between the different
  718. transformations can result in a highly obfuscated application.
  719.   In this paper we examine the problems that arise when constructing an
  720. {\em Obfuscation Executive}.  This is the main loop in charge of a) selecting
  721. the part of the application to be obfuscated next, b) choosing the best
  722. transformation to apply to this part, c) evaluating how much confusion and
  723. overhead has been added to the application, and d) deciding when the
  724. obfuscation process should terminate.
  725. %K keywords
  726. %Y
  727.  
  728. %A Hartman, John
  729. %A Collberg, Christian
  730. %A Babu, Sridivya
  731. %A Udupa, Sharath K.
  732. %T Slinky: Static Linking Reloaded
  733. %D Friday, February 27, 2004
  734. %Z Wed, 03 Jan 04 00:00:00 GMT
  735. %R TR04-02
  736. %I The Department of Computer Science, University of Arizona
  737. %U ftp://ftp.cs.arizona.edu/reports/2004/TR04-02.ps.Z
  738. %X Static linking has many advantages over dynamic linking. It is simple to
  739. understand, implement, and use. It ensures that an executable is self-contained
  740. and does not require a particular set of libraries during execution. As a
  741. consequence, the executable image that was tested by the developer is exactly
  742. the same as gets executed by the user, diminishing the risk that the user's
  743. environment will affect correct behavior.
  744.   The major disadvantages of static linking are increases in the memory
  745. required to run an executable, network bandwidth to transfer it, and disk
  746. space to store it.
  747.   In this paper we describe the \slinky\ system that uses digest-based sharing
  748. to combine the simplicity of static linking with the space savings of dynamic
  749. linking: \slinky\ executables are completely self-contained and minimal
  750. performance and disk-space penalties are incurred if two executables use the
  751. same library.  We have developed a \slinky\ prototype that consists of tools
  752. for adding digests to executables, and a slight modification of the Linux
  753. kernel to use those digests to share code pages.  Results show that our
  754. unoptimized prototype has a performance decrease of at most 4\% and a space
  755. increase of 40\% relative to dynamic linking.
  756. %K keywords
  757. %Y
  758.  
  759. %A Rajagopalan, Mohan
  760. %A Debray, Saumya K.
  761. %A Hiltunen, Matti A.
  762. %A Schlichting, Richard D.
  763. %T Reducing the energy cost of application/OS Interactions
  764. %D Tuesday, October 21, 2003
  765. %Z Wed, 03 Jan 04 00:00:00 GMT
  766. %R TR03-19
  767. %I The Department of Computer Science, University of Arizona
  768. %U ftp://ftp.cs.arizona.edu/reports/2003/TR03-19.ps
  769. %X Software approaches to power optimization have traditionally
  770. had two distinct foci, in relative isolation,
  771. targeting either individual applications (compilationbased
  772. techniques) or global (operating system) policies.
  773. Dynamic interactions between the application
  774. and operating system through system calls, which
  775. can potentially have a large impact on overall performance
  776. and power consumption, remain largely unoptimized
  777. due to the partitioning of concerns. This
  778. paper discusses the energy implications of a new system
  779. call clustering optimization technique for reducing
  780. application/OS interaction costs that is based on
  781. a novel multi-call mechanism. Preliminary results
  782. on common utility programs such as the mpeg play
  783. video decoder have been promising.
  784. %K keywords
  785. %Y
  786.  
  787. %A Kollipara, Siva
  788. %T Applying Network Processors to Header Compression
  789. %D Monday, October 20, 2003
  790. %Z Wed, 03 Jan 00 00:00:00 GMT
  791. %R TR03-17
  792. %I The Department of Computer Science, University of Arizona
  793. %U ftp://ftp.cs.arizona.edu/reports/2003/TR03-17.ps.Z
  794. %X Network Processors (NPs) are highly specialized processors optimized to
  795. handle protocol processing, with possibly including many other services like
  796. QoS, Statistics, Compression-Decompression etc, at highest speeds possible.
  797. Many vendors like Intel, IBM etc., have released powerful silicon for this
  798. market. NPs represent the Holy Grail  the panacea of network bottlenecks.
  799. Even though the architectural design of these various NPs varies significantly,
  800. the architectural principles/goals/ideas/requirements are almost similar - to
  801. achieve network processing at highest speeds possible with low latency. The
  802. programmability and parallel nature of these processor chips make them an
  803. ideal choice when high performance and ability to quickly adapt to new network
  804. standards are the requirements.
  805.    This report briefly describes the need for header compression in the
  806. Internet today and provides an analysis of the evolution of CRTP header
  807. compression design, using the IXP2X00. This was a particularly difficult
  808. challenge due to the fact that the order of packets is important. Reordering
  809. is not admissible since the compression (decompression) of each valid packet
  810. makes changes to the context, which is used for the compression (decompression)
  811. of the next packet. We also have time constraints to consider based on bus
  812. width, bus clock speed, processor clock speed, pipelining, network data rate
  813. (keeping in mind the link layer, physical layer overhead) and packet
  814. processing. Say some "x" bus ops/pkt and "y" CPU ops/pkt. At this rate,
  815. for each packet, buffers must be allocated, the packet must be received,
  816. stored in DRAM, header verified, classified, evaluated as to whether it
  817. should be dropped, compressed (decompressed), context updated, previous
  818. header stripped, new compressed (decompressed) header prepended, statistic
  819. counters updated, (multi-field and destination lookups performed for
  820. destination,) enqueued for transmit, transmitted, and buffers freed. This
  821. report chronicles the issues encountered and solutions devised to achieve
  822. header compression. The necessary concepts of context/functional pipeline,
  823. critical sections, signaling and ring buffers are defined with references.
  824. The CRTP pipe stages are described.
  825. %K keywords
  826. %Y
  827.  
  828. %A Kollipara, Siva
  829. %T Venti FS: A Hash Based File System
  830. %D Monday, October 20, 2003
  831. %Z Wed, 03 Jan 00 00:00:00 GMT
  832. %R TR03-16
  833. %I The Department of Computer Science, University of Arizona
  834. %U ftp://ftp.cs.arizona.edu/reports/2003/TR03-16.ps.Z
  835. %X Venti, a network storage system, is a write-once archival repository.
  836. It provides a block level interface and uses unique hashes (SHA1 hash) to
  837. identify these blocks. These hashes can be used to identify duplicate blocks
  838. and thus eliminate redundant duplication of blocks and reduce storage
  839. consumption. A direct mapping between hashes and disk addresses is not
  840. possible, therefore an indexer is used to map the hashes to Venti disk
  841. addresses. Venti can be used as a building block for constructing a variety
  842. of storage applications such as logical backup, physical backup and snapshot
  843. file systems.
  844.    Most file systems to date use fixed size blocks. Fixed size blocks limit
  845. the amount of duplication possible. However by breaking files into variable
  846. sized blocks based on the identification of anchor or break points, duplication
  847. can be increased and cross file similarities can be exploited efficiently.
  848.    We have built a file system on top of Venti and investigated the
  849. implications of several design decisions:
  850. 1. Use of different searching algorithms (B-Tree / Binary Tree) in indexer;
  851. 2. Variable Sized blocks instead of fixed size blocks.
  852.    We present some performance results that measure the average execution
  853. time for various operations of the file system and also analyze the impact
  854. of the design decisions made.
  855. %K keywords
  856. %Y
  857.  
  858. %A Kollipara, Siva
  859. %T SENSE: A Toolkit for Stick-e Frameworks
  860. %D Monday, October 20, 2003
  861. %Z Wed, 03 Jan 00 00:00:00 GMT
  862. %R TR03-15
  863. %I The Department of Computer Science, University of Arizona
  864. %U ftp://ftp.cs.arizona.edu/reports/2003/TR03-15.ps.Z
  865. %X Context-aware applications are gaining popularity and are hot research
  866. topics. As context-aware devices hit the market these kinds of applications
  867. will become common. This paper presents one such application that takes
  868. advantage of context-awareness - Electronic Post-It Note. This application
  869. consists of presenting information to the user as he enters a given context.
  870. There are already some existing E-Post-It Note software, but these are too
  871. application/field oriented; thus lacking the broadness that would make this
  872. a "killer" application. This project aims at providing a generic E-Post-It
  873. Note application that can support various end-user devices, enhanced/enriched
  874. contexts and even a combination of contexts!
  875.    The increase in the number of handheld devices and active research in the
  876. field of Context Aware Computing has led to a growing interest in the
  877. development of platforms and toolkits for context aware applications. In
  878. this paper we present the experiences in designing and implementing SENSE:
  879. An e-note toolkit for context aware applications. SENSE provides a platform
  880. to develop applications like campus guides that are both passive and active
  881. context aware.
  882. %K keywords
  883. %Y
  884.  
  885. %A Arango, Jesus
  886. %T Virtual IP Machines: A System Framework for Emulating Multiple IP Hosts
  887. %D Friday, October 10, 2003
  888. %Z Wed, 03 Jan 00 00:00:00 GMT
  889. %R TR03-14
  890. %I The Department of Computer Science, University of Arizona
  891. %U ftp://ftp.cs.arizona.edu/reports/2003
  892. %X This paper proposes a framework for emulating multiple IP hosts (virtual IP
  893. machines) inside a single system kernel. By augmenting and restructuring
  894. certain system components, the framework can provide an emulation and
  895. testing environment where a single system is capable of transparently
  896. representing multiple IP hosts comprising a virtual network.
  897.      The main advantage of the framework is that existing protocols,
  898. applications and network configuration utilities may execute under multiple
  899. virtual IP machines without being modified nor recompiled. The framework
  900. significantly reduces the equipment and spatial resources required by test
  901. beds and laboratory environments to appropriately conduct experiments and
  902. emulations.
  903.      This paper describes the architecture of the framework. We  also
  904. describe our implementation in the Linux kernel and analyze the performance
  905. and scalability of the framework based on the results obtained from experiments
  906. conducted on our implementation.
  907. %K keywords
  908. %Y
  909.  
  910. %A Arango, Jesus
  911. %A Degermark, Mikael
  912. %A Efrat, Alon
  913. %T An Efficient Flooding Algorithm for Mobile Ad-hoc Networks
  914. %D Friday, October 10, 2003
  915. %Z Wed, 03 Jan 03 00:00:00 GMT
  916. %R TR03-13
  917. %I The Department of Computer Science, University of Arizona
  918. %U ftp://ftp.cs.arizona.edu/reports/2003/
  919. %X We present a bandwidth-efficient flooding algorithm intended for use in
  920. wireless ad-hoc networks, and demonstrate its viability by simulation.
  921. Flooding algorithms solve the problem of delivering a message to all nodes
  922. in a network. With standard flooding algorithms, each node broadcasts
  923. received messages being flooded in order to ensure delivery to all nodes in
  924. the network. Our simulations show that the new algorithm is able to achieve
  925. a significant reduction in the number of broadcasts required to reach all
  926. nodes while still being able to maintain high coverage and low latencies.
  927. The number of broadcast messages required decreases with increasing node
  928. density, with an overhead reduction of 57% at a node density of 6.56. The
  929. new algorithm is simple to implement and does not require any additional
  930. protocol messages.
  931. %K keywords
  932. %Y
  933.  
  934. %A Visvanathan, Srinivas
  935. %A Hartman, John H.
  936. %T Exploiting Trust in Peer-to-Peer Systems
  937. %D Tuesday, August 5, 2003
  938. %Z Wed, 03 Jan 00 00:00:00 GMT
  939. %R TR03-09
  940. %I The Department of Computer Science, University of Arizona
  941. %U ftp://ftp.cs.arizona.edu/reports/2003/TR03-09.ps.Z
  942. %X Second generation peer-to-peer systems have shown a lot of promise with
  943. many desirable properties such as scalability, self-configuration, automatic
  944. load balancing etc. However the open nature of these systems also makes them
  945. vulnerable to Byzantine attacks.
  946.    These systems are designed to be fault tolerant in the presence of a few
  947. malicious nodes. We however believe that even a handful of evil nodes could
  948. disrupt the system by exploiting certain weaknesses that we have identified.
  949. In these systems, a single malicious node, can present multiple identities
  950. to the system. This allows them to emulate multiple nodes simultaneously and
  951. also allows them limited control of their placement in overlay networks that
  952. are integral to the system. We devised attacks based on these weaknesses to
  953. disrupt lookup and storage operations in the peer-to-peer storage systems,
  954. CFS and PAST. We show that it is possible to exploit these weaknesses to
  955. attack these systems and have evaluated the feasibility of these attacks.
  956. %K keywords
  957. %Y
  958.  
  959. %A Siva Kollipara
  960. %T SFSRO LITE - A Self-Certifying Read-Write File System
  961. %D Thursday, June 26, 2003
  962. %Z Wed, 03 Jan 03 00:00:00 GMT
  963. %R TR03-07
  964. %I The Department of Computer Science, University of Arizona
  965. %U ftp://ftp.cs.arizona.edu/reports/2003
  966. %X This report presents a read-write version of SFSRO. SFSRO [2], a
  967. self-certifying read-only file system, is a content distribution system
  968. providing secure, scalable read-only access to data. Since the data exists
  969. as a database, the read-only file system structure is too tightly coupled
  970. with the data [2]. Any change in the data will cause the whole file system
  971. to be updated and its hierarchy modified. To get around this problem,
  972. SFSRO creates a completely new database for each version of the file
  973. system and incrementally updates the replica file servers.
  974.   In this report, we present some modifications and extensions to SFSRO.
  975. We aim to achieve a file system with SFSRO functionality and guarantees,
  976. but without its drawbacks and limitations - suitably called SFSRO Lite
  977. (SFSROL). We plan to build a read-write version of SFSRO that uses a
  978. 'floating inode table' [5] and supports variable sized blocks. We have
  979. currently finished making necessary changes to incorporate the floating
  980. inode table. Further research in achieving a read-write version is in
  981. progress. Measurements of an implementation show that SFSROL is
  982. approximately 0-2% slower than SFSRO.
  983. %K keywords
  984. %Y
  985.  
  986. %A Rao, Praveen
  987. %A Moon, Bongki
  988. %T PRIX: Indexing And Querying XML Using Prufer Sequences
  989. %D Wednesday, June 25, 2003
  990. %Z Wed, 03 Jan 03 00:00:00 GMT
  991. %R TR03-06
  992. %I The Department of Computer Science, University of Arizona
  993. %U ftp://ftp.cs.arizona.edu/reports/2003/TR03-06.ps.Z
  994. %X We propose a new way of indexing XML documents and processing twig
  995. patterns in an XML database. Every XML document in the database can be
  996. transformed into a sequence of labels by Prufer's method that constructs
  997. a one-to-one correspondence between trees and sequences.  During query
  998. processing, a twig pattern is also transformed into its Prufer sequence.
  999. By performing subsequence matching on the set of sequences in the database,
  1000. and performing a series of refinement phases that we have developed, we can
  1001. find all the occurrences of a twig pattern in the database. Our approach
  1002. allows holistic processing of a twig pattern without breaking the twig
  1003. into root-to-leaf paths and processing these paths individually. 
  1004. Furthermore, we show in the paper that all correct answers are found
  1005. without any false dismissals or false alarms.  Experimental results
  1006. demonstrate the performance benefits of our proposed techniques.
  1007. %K keywords
  1008. %Y
  1009.  
  1010. %A Rajagopalan, Mohan
  1011. %A Debray, Saumya K.
  1012. %A Hiltunen, Matti A.
  1013. %A Schlichting, Richard D.
  1014. %T Profile Directed Optimization of Event Based Programs
  1015. %D Friday, June 6, 2003
  1016. %Z Wed, 03 Jan 03 00:00:00 GMT
  1017. %R TR03-05
  1018. %I The Department of Computer Science, University of Arizona
  1019. %U ftp://ftp.cs.arizona.edu/reports/2003
  1020. %X Events are used as a fundamental abstraction in programs ranging from
  1021. graphical user interfaces (GUIs) to systems for building customized network
  1022. protocols.
  1023. While providing a flexible structuring and execution paradigm, events have
  1024. the potentially serious drawback of extra execution overhead due to the
  1025. indirection between modules that raise events and those that handle them.
  1026. This paper describes an approach to addressing this issue using static
  1027. optimization techniques.
  1028. This approach, which exploits the underlying predictability often exhibited
  1029. by event-based programs, is based on first profiling the program to identify
  1030. commonly occurring event sequences. A variety of techniques that use the
  1031. resulting profile information are then applied to the program to reduce
  1032. the overheads associated with such mechanisms as indirect function calls and
  1033. argument marshaling.  In addition to describing the overall approach,
  1034. experimental results are given that demonstrate the effectiveness of the
  1035. techniques.
  1036. These results are from event-based programs written for X Windows,
  1037. a system for building GUIs, and Cactus, a system for constructing highly
  1038. configurable distributed services and network protocols.
  1039. %K keywords
  1040. %Y
  1041.  
  1042. %A Erten, Cesim
  1043. %A Harding, Philip J.
  1044. %A Kobourov, Stephen G.
  1045. %A Wampler, Kevin
  1046. %A Yee, Gary
  1047. %T Exploring the Computing Literature Using Temporal Graph Visualization
  1048. %D Tuesday, June 3, 2003
  1049. %Z Wed, 03 Jan 03 00:00:00 GMT
  1050. %R TR03-04
  1051. %I The Department of Computer Science, University of Arizona
  1052. %U ftp://ftp.cs.arizona.edu/reports/2003
  1053. %X What are the hottest computer science research topics today?
  1054. Which research areas are experiencing steady decline? How many
  1055. co-authors are typical for a research paper today and 20 years ago?
  1056. Who are the most prolific writers? In this paper, we attempt to
  1057. address these questions as well as study collaboration patterns,
  1058. research communities, interactions between related research
  1059. specialties, and the evolution of these characteristics through
  1060. time. For our analysis we use data from the Association of Computing
  1061. Machinery's Digital Library of Scientific Literature (ACM Portal)
  1062. which contains over a hundred thousand research papers and
  1063. authors. We use a novel technique for visualization of large graphs
  1064. that evolve through time. Given a dynamic graph, the layout algorithm
  1065. produces two-dimensional representations of each time-slice, while
  1066. preserving the mental map of the graph from one slice to the next. A
  1067. combined view, with all the time-slices can also be viewed and
  1068. explored. Graphs with tens of thousands of vertices and edges,
  1069. resulting from specific queries to our local copy of the ACM database,
  1070. are generated and displayed in seconds. The images in this paper are
  1071. produced by a graph layout tool which uses the dynamic graph layout
  1072. algorithm.
  1073. %K keywords
  1074. %Y
  1075.  
  1076. %A Kobourov, Stephen
  1077. %A Collberg, Christian
  1078. %T Self-Plagiarism in Computer Science
  1079. %D Tuesday, May 13, 2003
  1080. %Z Wed, 03 Jan 00 00:00:00 GMT
  1081. %R TR03-03
  1082. %I The Department of Computer Science, University of Arizona
  1083. %U ftp://ftp.cs.arizona.edu/reports/2003
  1084. %X abstract
  1085. %K keywords
  1086. %Y
  1087.  
  1088. %A Arvind Krishnaswamy
  1089. %A Rajiv Gupta
  1090. %T Instruction Coalescing for 16-bit Code
  1091. %D Thursday, January 16, 2003
  1092. %Z Mon, 06 Jan 03 00:00:00 GMT
  1093. %R TR03-01
  1094. %I The Department of Computer Science, University of Arizona
  1095. %U ftp://ftp.cs.arizona.edu/reports/2003/
  1096. %X In the embedded domain, memory usage and energy consumption are
  1097. critical constraints. Embedded processors such as the ARM and MIPS
  1098. provide a 16-bit instruction set (called Thumb in the case of the
  1099. ARM cpu family) in addition to the 32-bit instruction set to address
  1100. these concerns.  Using 16-bit instructions one can achieve code size
  1101. reduction and I-cache energy savings at the cost of performance.
  1102.     This paper presents a novel approach that enhances the performance
  1103. of 16-bit Thumb  code. We have observed that throughout Thumb code
  1104. there exist Thumb instruction pairs that are equivalent to a single
  1105. ARM instruction. We have developed enhancements to the processor
  1106. microarchitecture and the Thumb instruction set to exploit this property.
  1107. We enhance the Thumb instruction set by incorporating Augmenting
  1108. eXtensions(AX).  A Thumb instruction pair that can be combined into a
  1109. single ARM instruction is replaced by an AXThumb instruction pair by the
  1110. compiler. The AX instruction is coalesced with the immediately following
  1111. Thumb instruction to generate a single ARM instruction at decode time.
  1112. The enhanced microarchitecture ensures that coalescing does not introduce
  1113. pipeline delays or increase cycle time thereby resulting in reduction of
  1114. both instruction counts and cycle counts. Using AX instructions and
  1115. coalescing hardware we are also able to support efficient predicated
  1116. execution in 16 bit mode.
  1117. %K keywords
  1118. %Y
  1119.  
  1120. %A Trebisky, Tom
  1121. %T The Skidoo Real-Time Operating System
  1122. %D Monday, November 25, 2002
  1123. %Z Mon, 03 Jan 05 00:00:00 GMT
  1124. %R TR02-05
  1125. %I The Department of Computer Science, University of Arizona
  1126. %U ftp://ftp.cs.arizona.edu/reports/2002/TR02-05.ps.Z
  1127. %X Embedded systems have needs that are not adequately met by conventional 
  1128. operating systems. Skidoo is a new operating system especially tailored to 
  1129. support embedded systems. Independently scheduled threads are provided that 
  1130. synchronize using semaphores and condition variables. Threads share a common 
  1131. address space and communicate using shared variables. Fully preemptive scheduling meets the needs of hard real-time applications.
  1132. %K keywords
  1133. %Y
  1134.  
  1135. %A Baker, Scott
  1136. %A Hartman, John
  1137. %T The Mirage NFS Router
  1138. %D Monday, November 25, 2003
  1139. %Z Wed, 03 Jan 02 00:00:00 GMT
  1140. %R TR02-04
  1141. %I The Department of Computer Science, University of Arizona
  1142. %U ftp://ftp.cs.arizona.edu/reports/2002
  1143. %X Mirage is a system that aggregates multiple NFS servers into a
  1144. single, virtual NFS file server. It is interposed between the NFS
  1145. clients and servers, making the clients believe that they are
  1146. communicating with a single, large server. Mirage is an NFS router
  1147. because it routes an NFS request from a client to the proper NFS server,
  1148. and routes the reply back to the proper client. Mirage also prevents DoS
  1149. attacks on the NFS protocol, ensuring that all clients receive a fair
  1150. share of the servers\222 resources. Mirage is designed to run on an IP
  1151. router, providing virtualized NFS file service without affecting other
  1152. network traffic. Experiments with a Mirage prototype show that Mirage
  1153. effectively virtualizes an NFS server using unmodified clients and
  1154. servers, and it ensures that legitimate clients receive a fair share
  1155. of the NFS server even during a DoS attack.  Mirage imposes an
  1156. overhead of only 7% on a realistic NFS workload.
  1157. %K Mirage, router, NFS
  1158. %Y
  1159.  
  1160. %A Moon, Bongki
  1161. %A Shin, Hyoseop
  1162. %A Lee, Sukho
  1163. %T Adaptive and Incremental Processing for Distance Join Queries
  1164. %D Thursday, August 29, 2002
  1165. %Z Wed, 03 Jan 02 00:00:00 GMT
  1166. %R TR02-03
  1167. %I The Department of Computer Science, University of Arizona
  1168. %U ftp://ftp.cs.arizona.edu/reports/2002
  1169. %X A spatial distance join is a relatively new type of operation
  1170. introduced for spatial and multimedia database applications. 
  1171. Additional requirements for ranking and stopping cardinality are
  1172. often combined with the spatial distance join in on-line query
  1173. processing or internet search environments. These requirements
  1174. pose new challenges as well as opportunities for more efficient
  1175. processing of spatial distance join queries.  In this paper, we
  1176. first present an efficient k-distance join algorithm that uses
  1177. spatial indexes such as R-trees. Bi-directional node expansion
  1178. and plane-sweeping techniques are used for fast pruning of distant
  1179. pairs, and the plane-sweeping is further optimized by novel strategies
  1180. for selecting a sweeping axis and direction.
  1181. Furthermore, we propose adaptive multi-stage algorithms for k-distance
  1182. join and incremental distance join operations.  Our performance study
  1183. shows that the proposed adaptive multi-stage algorithms outperform
  1184. previous work by up to an order of magnitude for both k-distance
  1185. join and incremental distance join queries, under various operational
  1186. conditions.
  1187. %K spatial, cardinality, k-distance
  1188. %Y
  1189.  
  1190. %A Al-Bin-Ali, Fahd
  1191. %T Design and Implementation of an Inter-cell Management System:
  1192. The Sabino System
  1193. %D Tuesday, July 2, 2002
  1194. %Z Wed, 03 Jan 02 00:00:00 GMT
  1195. %R TR02-02
  1196. %I The Department of Computer Science, University of Arizona
  1197. %U ftp://ftp.cs.arizona.edu/reports/2002
  1198. %X Wireless networks based on IEEE 802.11 are becoming increasingly widely
  1199. deployed. However, 802.11 systems fail to make optimal use of the
  1200. available network resources because of a lack of coordination between
  1201. different system components, in particular, the absence of any form of
  1202. coordination between access points and mobile nodes. Consequently,
  1203. wireless network installations may not make optimal allocation of mobile
  1204. nodes to access points, leading to imbalances in the load distribution and
  1205. potentially reducing the network bandwidth available to users. This thesis
  1206. presents the Sabino system: a lightweight management architecture that
  1207. coordinates the actions of access points and mobile nodes to ensure, where
  1208. possible, a more balanced load distribution and hence better utilization
  1209. of system resources. Sabino as an architectural solution is applicable for
  1210. many other applications and future wireless deployments in which mobile
  1211. nodes have different Quality-of-Service requirements and are serviced by
  1212. different network technologies. Key aspects of the Sabino system include
  1213. easy and incremental deployment, flexible architectural topology, minimal
  1214. overhead and effective management of resources. This thesis presents
  1215. evidence of some of the problems in existing 802.11 systems and it
  1216. describes the design, the implementation and the evaluation of the Sabino
  1217. system as an effective solution to these problems.
  1218. %K keywords
  1219. %Y
  1220.  
  1221. %A Hartman, John
  1222. %T Activating Storage Systems with Agents
  1223. %D Thursday, June 13, 2002
  1224. %Z Wed, 03 Jan 02 00:00:00 GMT
  1225. %R TR02-01
  1226. %I The Department of Computer Science, University of Arizona
  1227. %U ftp://ftp.cs.arizona.edu/reports/2002
  1228. %X Swarm is a scalable, modular storage system that allows high-level
  1229. services to influence low-level storage functions such as data layout,
  1230. metadata management, and crash recovery via agents.  An agent is
  1231. a program that is attached to data in the storage system and invoked
  1232. when particular events occur during the data's lifetime.  For example,
  1233. when Swarm needs to write data to disk, agents attached to the data are
  1234. invoked to determine a layout policy.  Agents can be persistent, so that
  1235. they remain attached to the data they manage until the data are deleted;
  1236. this allows agents to continue to affect how the data are handled long
  1237. after the application or storage service that created the data has
  1238. terminated. Swarm and its agent mechanism are implemented as a Linux
  1239. kernel module.  In this paper, we present Swarm's agent architecture,
  1240. describe the types of agents that Swarm supports and the infrastructure
  1241. used to support them, and discuss their performance overhead and security
  1242. implications.  We describe how several storage services and applications
  1243. use agents, and the benefits they derive from doing so.
  1244. %K keywords
  1245. %Y
  1246.  
  1247. %A Cappos, Justin
  1248. %A Homer, Patrick
  1249. %T DsCats: Animating Data Structures for CS 2 and CS 3 Courses
  1250. %D Wednesday, March 14, 2001
  1251. %Z Mon, 03 Jan 01 00:00:00 GMT
  1252. %R TR01-02
  1253. %I The Department of Computer Science, University of Arizona
  1254. %U ftp://ftp.cs.arizona.edu/reports/2001/TR01-02.ps.Z
  1255. %X A new data structure animation tool called DsCats is available for
  1256. classroom use. This tool supports educator presentations, student
  1257. experimentation, and programming assignments. It implements a
  1258. user-centered approach supporting a wide range of detail levels, the
  1259. ability to jump to any point in the animation, and on the fly
  1260. variations in the data structure during animations. The tool is
  1261. written in Java with modularity and expandability in mind.
  1262. %K keywords
  1263. %Y
  1264.  
  1265. %A Collberg, Christian
  1266. %T A Fuzzy Visual Query Language for a Domain-Specific Web Search Engine
  1267. %D Tuesday, March 13, 2001
  1268. %Z Tue, 02 Jan 01 00:00:00 GMT
  1269. %R TR01-01
  1270. %I The Department of Computer Science, University of Arizona
  1271. %U ftp://ftp.cs.arizona.edu/reports/2001
  1272. %X Algovista is a web-based search engine that assists programmers to
  1273. find algorithms and implementations that solve specific problems.
  1274. Algovista is not keyword based but rather requires users to provide -
  1275. in a very simple textual language - input/output samples that describe
  1276. the behavior of their needed algorithm. Unfortunately, even this simple
  1277. language has proven too challenging for casual users.
  1278. To overcome this problem and make Algovista more accessible to novice
  1279. programmers, we are designing and prototyping a visual language for
  1280. creating Algovista queries. Since web users do not have the patience
  1281. to learn fancy query languages (be they textual or visual), our goal
  1282. is to make this language and its implementation natural enough to
  1283. require virtually no explanation or user training.
  1284. %K Algovista, web-based, algorithm, language
  1285. %Y
  1286.  
  1287. %A Gupta, Neelam
  1288. %A Bass, Len
  1289. %T Designing Software to Reduce Cost of Testing
  1290. %D Thursday, July 6, 2000
  1291. %Z Wed, 03 Jan 00 00:00:00 GMT
  1292. %R TR00-06
  1293. %I The Department of Computer Science, University of Arizona
  1294. %U ftp://ftp.cs.arizona.edu/reports/2000/
  1295. %X Software testing is an important and expensive component of the
  1296. software development life cycle. The testing community has always treated
  1297. the design of the software to be tested as an input over which they have
  1298. no control. In this paper, we propose a new approach to reduce the cost
  1299. of integration testing by influencing the design of the system to be tested.
  1300. We consider the simple pipe and filter architecture style and analyse its
  1301. testability for integration testing. Our analysis shows that the size of
  1302. test suite required for integration testing is a linear function of the
  1303. number of modules in pipe and filter architecture style. In contrast, the
  1304. size of test suite required for a general design, with arbitrary communication
  1305. among its modules, is an exponential function of the number the modules in
  1306. the design. This illustrates that the cost of the testing stage can be
  1307. significantly reduced by appropriate selection of the architecture style
  1308. during the design stage.
  1309. %K software archictecture style, software testing, pipe and filter
  1310. %Y
  1311.  
  1312. %A Hiltunen, Matti
  1313. %A Jaiprakash, Sumita
  1314. %A Schlichting, Richard
  1315. %A Ugarte, Carlos
  1316. %T Fine-Grain Configurability for Secure Communication
  1317. %D Friday, June 16, 2000
  1318. %Z Wed, 03 Jan 00 00:00:00 GMT
  1319. %R TR00-05
  1320. %I The Department of Computer Science, University of Arizona
  1321. %U ftp://ftp.cs.arizona.edu/reports/2000/
  1322. %X Current solutions for providing communication security in network
  1323. applications allow customization of certain security attributes and
  1324. techniques, but in limited ways and without the benefit of a single
  1325. unifying framework. Here, the design of a highly-customizable
  1326. extensible service called SecComm is described in which attributes
  1327. such as authenticity, privacy, integrity, and non-repudiation can be
  1328. customized in arbitrary ways. With SecComm, applications can open
  1329. secure communication connections in which only those attributes
  1330. selected from among a wide range of possibilities are enforced, and
  1331. are enforced using the strength or technique desired. SecComm has
  1332. been implemented using Cactus, a system for building configurable
  1333. communication services.  In Cactus, different properties and techniques
  1334. are implemented as software modules called micro-protocols that
  1335. interact using an event-driven execution paradigm. This non-hierarchical
  1336. design approach has a high degree of flexibility, yet provides enough
  1337. structure and control that it is easy to build collections of
  1338. micro-protocols realizing a large number of diverse properties.
  1339. This paper gives an overview of the design and implementation
  1340. of SecComm, and gives initial performance figures for a prototype
  1341. implementation running on a cluster of Pentiums using the Mach MK 7.3
  1342. operating system.
  1343. %K keywords
  1344. %Y
  1345.  
  1346. %A Debray, Saumya
  1347. %A Evans, William
  1348. %A Muth, Robert
  1349. %A De Sutter, Bjorn
  1350. %T Compiler Techniques for Code Compaction
  1351. %D Wednesday, March 15, 2000
  1352. %Z Wed, 03 Jan 00 00:00:00 GMT
  1353. %R TR00-04
  1354. %I The Department of Computer Science, University of Arizona
  1355. %U ftp://ftp.cs.arizona.edu/reports/2000/
  1356. %X In recent years there has been an increasing trend towards the incorporation
  1357. of computers into a variety of devices where the amount of memory
  1358. available is limited.  This makes it desirable to try to reduce the size of
  1359. applications where possible.  This paper explores the use of compiler
  1360. techniques to accomplish code compaction to yield smaller executables.
  1361. The main contribution of this paper is to show that careful, aggressive,
  1362. interprocedural optimization, together with procedural abstraction of
  1363. repeated code fragments, can yield significantly better reductions in
  1364. code size than previous approaches, which have generally focused on
  1365. abstraction of repeated instruction sequences.  We also show how ``equivalent''
  1366. code fragments can be detected and factored out using conventional
  1367. compiler techniques, and without having to resort to
  1368. purely linear treatments of code sequences as in suffix-tree-based approaches,
  1369. thereby setting up a framework for code compaction that can be more flexible in
  1370. its treatment of what code fragments are considered equivalent.
  1371. Our ideas have been implemented in the form of a binary-rewriting tool
  1372. that reduces the size of executables by about 30% on the average.
  1373. %K keywords
  1374. %Y
  1375.  
  1376. %A Collberg, Christian
  1377. %A Thomborson, Clark
  1378. %T Watermarking, Tamper-Proofing, and Obfuscation -- Tools for Software Protecti
  1379. on
  1380. %D Thursday, Feb 10, 2000
  1381. %Z Wed, 03 Jan 00 00:00:00 GMT
  1382. %R TR00-03
  1383. %I The Department of Computer Science, University of Arizona
  1384. %U ftp://ftp.cs.arizona.edu/reports/2000/
  1385. %X abstract
  1386. %K keywords
  1387. %Y
  1388.  
  1389. %A Collberg, Christian
  1390. %A Davey, Sean
  1391. %A Proebsting, Todd
  1392. %T Language-Agnostic Program for Rendering for Presentation, Debugging and Visua
  1393. lization
  1394. %D Thursday, Feb 10, 2000
  1395. %Z Wed, 03 Jan 00 00:00:00 GMT
  1396. %R TR00-02
  1397. %I The Department of Computer Science, University of Arizona
  1398. %U ftp://ftp.cs.arizona.edu/reports/2000/
  1399. %X abstract
  1400. %K keywords
  1401. %Y
  1402.  
  1403. %A Collberg, Christian
  1404. %A Proebsting, Todd
  1405. %T AlgoVista - A Search Engine for Computer Scientists
  1406. %D Thursday, January 27, 2000
  1407. %Z Mon, 03 Jan 00 00:00:00 GMT
  1408. %R TR00-1
  1409. %I The Department of Computer Science, University of Arizona
  1410. %U ftp://ftp.cs.arizona.edu/reports/2000/TR
  1411. %X We describe AlgoVista, a web-based search engine designed to allow
  1412. applied computer scientists to classify problems and find algorithms
  1413. and implementations that solve these problems. Unlike other search engines,
  1414. AlgoVista is not keyword based. Rather, users provide a set of input==>output
  1415. samples that describe the behavior of the problem they wish to classify.
  1416. This type of  query-by-example requires no knowledge of specialized
  1417. terminology, only an ability to formalize the problem.
  1418. The search mechanism of AlgoVista is based on a novel application of program
  1419. checking, a technique developed as an alternative to program verification
  1420. and testing.
  1421. %K AlgoVista, web-based, keyword
  1422. %Y
  1423.  
  1424. %A Hyoseop Shin
  1425. %A Bongki Moon
  1426. %A Sukho Lee
  1427. %T Adaptive Multi-Stage Distance Join Processing
  1428. %D Monday, October 18, 1999
  1429. %Z Wed, 08 Jan 99 00:00:00 GMT
  1430. %R TR99-14
  1431. %I The Department of Computer Science, University of Arizona
  1432. %U ftp://ftp.cs.arizona.edu/reports/1999/TR99-14.ps
  1433. %X A spatial distance join is a relatively new type of operation
  1434. introduced for spatial and multimedia database applications.
  1435. Additional requirements for ranking and stopping cardinality are
  1436. often combined with the spatial distance join in on-line query processing
  1437. or internet search environments. These requirements pose new challenges
  1438. as well as opportunities for more efficient processing of
  1439. spatial distance join queries.
  1440. In this paper, we first present an efficient $k$-distance join algorithm
  1441. that uses spatial indexes such as R-trees. Bi-directional node expansion
  1442. and plane-sweeping techniques are used for fast pruning of distant pairs,
  1443. and the plane-sweeping is further optimized by novel strategies for
  1444. selecting a sweeping axis and direction.
  1445. Furthermore, we propose adaptive multi-stage algorithms
  1446. for $k$-distance join and incremental distance join operations.
  1447. Our performance study shows that the proposed adaptive multi-stage algorithms
  1448. outperform previous work by up to an order of magnitude
  1449. for both $k$-distance join and incremental distance join queries,
  1450. under various operational conditions.
  1451. %K keywords
  1452. %Y
  1453.  
  1454. %A Muth, Robert
  1455. %A Debray, Saumya
  1456. %T On the Complexity of Flow-Sensitive Dataflow Analyses
  1457. %D Wednesday, August 4, 1999
  1458. %Z Wed, 08 Jan 99 00:00:00 GMT
  1459. %R TR99-12
  1460. %I The Department of Computer Science, University of Arizona
  1461. %U ftp://ftp.cs.arizona.edu/reports/1999/TR99-12.ps
  1462. %X This paper attempts to address the question of why certain dataflow
  1463. analysis problems can be solved efficiently, but not others.  We focus
  1464. on flow-sensitive analyses, and give a simple and general result that
  1465. shows that analyses that require the use of relational attributes for
  1466. precision must be PSPACE-hard in general.  We then show that if the
  1467. language constructs are slightly strengthened to allow a computation to
  1468. maintain a very limited summary of what happens along an execution path,
  1469. inter-procedural analyses become EXPTIME-hard.  We discuss applications
  1470. of our results to a variety of analyses discussed in the literature.
  1471. Our work elucidates the reasons behind the complexity results given by
  1472. a number of authors, improves on a number of such complexity results,
  1473. and exposes conceptual commonalities underlying such results that are
  1474. not readily apparent otherwise.
  1475. %K PSPACE-hard, EXPTIME-hard
  1476. %Y
  1477.  
  1478. %A Verkhedkar, Sameer A.
  1479. %T A Highly Customizable System Monitoring and Control Tool
  1480. %D Monday, July 19, 1999
  1481. %Z Wed, 08 Jan 99 00:00:00 GMT
  1482. %R TR99-11
  1483. %I The Department of Computer Science, University of Arizona
  1484. %U ftp://ftp.cs.arizona.edu/reports/1999/TR99-11.ps
  1485. %X The management of a large collection of machines connected by a
  1486. network and the software running on them is a difficult task. For
  1487. example, processes may fail causing service disruptions, or users
  1488. may exceed their quota of system resources causing shortages. If the
  1489. site has a large number of machines, keeping track of all such
  1490. problems can be very cumbersome. This thesis presents a system monitoring
  1491. tool that addresses these problems. The tool monitors different aspects
  1492. of the system state, such as processes running on each machine and their
  1493. resource usage, and reports the information to the administrator via a
  1494. graphical user interface(GUI). The tool can also be used for controlling
  1495. remote machines through the GUI by starting or stopping processes, and for
  1496. automatically restarting failed processes. Since the monitoring requirements
  1497. differ for every system, the monitoring tool is highly customizable
  1498. and extensible at a fine-grain level. This is achieved by implementing
  1499. the tool as a collection of modules called micro-protocols that can be
  1500. configured in various combinations to provide customized variants of the
  1501. monitoring service. The implementation is based on Cactus, a framework
  1502. for developing middleware offering fine-grain customizability for Quality
  1503. of Service(QoS) attributes related to dependability, real-time and security
  1504. in distributed systems. This thesis describes the design and implementation
  1505. of an architecture for system administration based on a higly customizable
  1506. system monitoring tool, and validates the Cactus approach for developing
  1507. highly customizable software at the application layer.
  1508. %K thesis
  1509. %Y
  1510.  
  1511. %A Moon, Bongki
  1512. %A Jagadish, H.V.
  1513. %A Faloutsos, Christos
  1514. %A Saltz, Joel H.
  1515. %T Analysis of the Clustering Properties of Hilbert Space-filling Curve
  1516. %D May 26, 1999
  1517. %Z Wed, 08 Jan 99 00:00:00 GMT
  1518. %R TR99-10
  1519. %I The Department of Computer Science, University of Arizona
  1520. %U ftp://ftp.cs.arizona.edu/reports/1999/TR99-10.ps
  1521. %X Several schemes for linear mapping of multidimensional space have
  1522. been proposed for many applications such as access methods for
  1523. spatio-temporal databases, image compression and so on. In all
  1524. these applications, one of the most desired properties from such
  1525. linear mappings is clustering, which means the locality between
  1526. objects in the multidimensional space is preserved in the linear
  1527. space. It is widely believed that the Hilbert space-filling curve
  1528. achieves the best clustering [1, 16]. In this paper we provide
  1529. closed-form formulas of the number of clusters required by a given
  1530. query region of an arbitrary shape (e.g., polygons and polyhedra)
  1531. for Hilbert space-filling curve. Both the asymptotic solution for
  1532. a general case and the exact solution for a special case generalize
  1533. the previous work [16], and they agree with the empirical results
  1534. that the number of clusters depends on the hyper-surface area of
  1535. the query region and not on it's hyper-volume. We have also shown
  1536. that Hilbert curve achieves better clustering than the z curve.
  1537. From the practical point of view, the formulas given in this paper
  1538. provide a simple measure which can be used to predict the required
  1539. disk access behaviors and hence the total access time.
  1540. %K Hilbert, clustering, linear space
  1541. %Y
  1542.  
  1543. %A Hiltunen, Matti
  1544. %A Jaiprakash, Sumita
  1545. %A Schlichting, Richard
  1546. %T Exploiting Fine-Grain Configurability for Secure Communication
  1547. %D Wednesday, April 28, 1999
  1548. %Z Wed, 08 Jan 99 00:00:00 GMT
  1549. %R TR99-08
  1550. %I The Department of Computer Science, University of Arizona
  1551. %U ftp://ftp.cs.arizona.edu/reports/1999/TR99-08.ps
  1552. %X Current protocols such as IPSec and TLS that provide communication
  1553. security for network applications allow customization of certain
  1554. security attributes and techniques, but in limited ways and without
  1555. the benefit of a single unifying framework. Here, the design of a
  1556. highly-customizable extensible service called SecComm is described
  1557. in which attributes such as authenticity, privacy, integrity, and
  1558. non-repudiation can be customized in arbitrary ways. With SecComm,
  1559. applications can open secure communication connections in which only
  1560. those attributes selected from among a wide range of possibilities
  1561. are enforced, and are enforced using the strength or technique desired.
  1562. SecComm is being implemented using the Mach MK 7.3 operating system
  1563. and Cactus, a system for building configurable communication services.
  1564. In Cactus, different properties and techniques are implemented as
  1565. software modules called micro-protocols that interact using an
  1566. event-driven execution paradigm. This design approach has a high degree
  1567. of flexibility, yet provides enough structure and control that it is
  1568. easy to build collections of micro-protocols realizing a large number
  1569. of diverse properties.
  1570. %K fine-grain, SecComm, Cactus
  1571. %Y
  1572.  
  1573. %A Debray, Saumya
  1574. %A Evans, William
  1575. %A Muth, Robert
  1576. %T Compiler Techniques for Code Compression
  1577. %D Friday, April 23, 1999
  1578. %Z Wed, 08 Jan 99 00:00:00 GMT
  1579. %R TR99-07
  1580. %I The Department of Computer Science, University of Arizona
  1581. %U ftp://ftp.cs.arizona.edu/reports/TR99-07.ps
  1582. %X In recent years there has been an increasing trend towards the
  1583. incorporation of computers into a variety of devices where the amount
  1584. of memory available is limited. This makes it desirable to try and reduce
  1585. the size of applications where possible. This paper explores the use of
  1586. compiler techniques to accomplish code compression to yield smaller
  1587. executables. The main contribution of this paper is that, by showing how
  1588. "equivalent" code fragments can be detected and factored out without
  1589. having to report to purely linear treatments of code sequences as in
  1590. suffix-tree-based approaches, it sets up a framework for code compression
  1591. that can be more flexible in it's treatment of what code fragments are
  1592. considered equivalent. Our ideas have been implemented in the form of a
  1593. binary-rewriting tool that is able to achieve signaficantly better
  1594. compression that previous approaches.
  1595. %K keywords
  1596. %Y
  1597.  
  1598. %A Hartman, John H.
  1599. %A Murdock, Ian
  1600. %A Spalink, Tammo
  1601. %T The Swarm Scalable Storage System
  1602. %D Thursday, April 1, 1999
  1603. %Z Wed, 08 Jan 99 00:00:00 GMT
  1604. %R TR99-06
  1605. %I The Department of Computer Science, University of Arizona
  1606. %U ftp://ftp.cs.arizona.edu/reports/1999/TR99-06.ps
  1607. %X Swarm is a storage system that provides scalable, reliable, and
  1608. cost-effective data storage.  Swarm is based on storage servers,
  1609. rather than file servers; the storage servers are optimized for
  1610. cost-performance and aggregated to provide high-performance data
  1611. access.  Swarm uses a <I>striped log</I> abstraction to store data
  1612. on the storage servers.  This abstraction simplifies storage
  1613. allocation, improves file access performance, balances server loads,
  1614. provides fault-tolerance through computed redundancy, and simplifies
  1615. crash recovery.  We have developed a Swarm prototype using a cluster
  1616. of Linux-based personal computers as the storage servers and clients;
  1617. the clients access the servers via the Swarm-based Sting file system.
  1618. Our performance measurements show that a single Swarm client can write
  1619. to two storage servers at 3.0 MB/s., while four clients can write to
  1620. eight servers at 16.0 MB/s.
  1621. %K Swarm, scalable, storage
  1622. %Y
  1623.  
  1624. %A Chiu, Wanda
  1625. %A Hartman, John H.
  1626. %T Building Caches using Multi-Threaded State Machines
  1627. %D Monday, February 15, 1999
  1628. %Z Wed, 08 Jan 99 00:00:00 GMT
  1629. %R TR99-05
  1630. %I The Department of Computer Science, University of Arizona
  1631. %U ftp://ftp.cs.arizona.edu/reports/1999/TR99-05.ps
  1632. %X Designing a client-side cache for a distributed file system is
  1633. complicated by concurrent accesses by applications, network communication
  1634. with the server, and complex relationships between the data in the
  1635. cache. Despite these difficulties, caches are usually built using threads
  1636. or finite state machines as the programming model, even though both are
  1637. inadequate for the task. We have created an infrastructure for cache
  1638. development based on multi-threaded state machines, which attempts to
  1639. capitalize on the benefits of both programming models. The state machine
  1640. allows the global state of the cache to be carefully controlled,
  1641. allowing interactions between concurrent cache operations to be
  1642. reasoned about and verified. Threads allow individual operations to
  1643. maintain their own local state, and propagate that state across transitions
  1644. of the state machine. We  created a prototype of this infrastructure and
  1645. used it to implement a write-through file block cache that provides
  1646. multiple-reader/single-writer access to its blocks; although this is
  1647. a relatively simple cache protocol, it is much easier to implement
  1648. using multi-threaded state machines than using either threads or finite
  1649. state machines alone.
  1650. %K state machines, caches, multi-threaded
  1651. %Y
  1652.  
  1653. %A Hiltunen, Matti A.
  1654. %A Immanuel, Vijaykumar
  1655. %A Schlichting, Richard D.
  1656. %T Supporting Customized Failure Models for Distributed Software
  1657. %D Thursday, February 11, 1999
  1658. %Z Wed, 08 Jan 99 00:00:00 GMT
  1659. %R TR99-04
  1660. %I The Department of Computer Science, University of Arizona
  1661. %U ftp://ftp.cs.arizona.edu/reports/1999/TR99-04.ps
  1662. %X The cost of employing software fault-tolerance techniques in distributed
  1663. systems is strongly related to the type of failures to be tolerated.  For
  1664. example, in terms of the amount of redundancy required and execution time,
  1665. tolerating a processor crash is much cheaper than tolerating arbitrary
  1666. (or Byzantine) failures. The tradeoff, of course, is that making stronger
  1667. assumptions about failures lessens the degree of fault coverage provided by
  1668. the system.  This paper describes an approach to constructing configurable
  1669. services for distributed systems that allows easy customization of the
  1670. type of failures to tolerate.  For example, using our approach, it is
  1671. possible to configure custom services across a spectrum of possibilities,
  1672. from a very efficient but unreliable server group that does not tolerate
  1673. any failures, to a less efficient but reliable group that tolerates crash,
  1674. omission, timing, or arbitrary failures. The approach is based on building
  1675. configurable services as collections of software modules called micro-protocols.
  1676. Each micro-protocol implements a different semantic property or property
  1677. variant, and interacts with other micro-protocols using an event-driven
  1678. model provided by a runtime system.  The net result is an enhanced ability
  1679. to explicitly manage the tradeoff between the level of reliability and
  1680. cost.  In addition to facilitating the choice of failure model, our approach
  1681. allows service properties such as message ordering and delivery atomicity
  1682. to be customized for each application.
  1683. %K keywords
  1684. %Y
  1685.  
  1686. %A Miller, Susan J.
  1687. %A Myers, Gene
  1688. %T The FAKtory DNA Sequence Fragment Assembly System
  1689. %D Wednesday, February 3, 1999
  1690. %Z Wed, 08 Jan 99 00:00:00 GMT
  1691. %R TR99-03
  1692. %I The Department of Computer Science, University of Arizona
  1693. %U ftp://ftp.cs.arizona.edu/reports/1999/TR99-03.ps
  1694. %X FAKtory is a software environment for supporting DNA sequencing
  1695. projects. FAKtory runs on machines configured with the UNIX operating
  1696. system. It is called FAKtory because it employs our FAKII Fragment
  1697. Assembly Kernel that is a C-library of routines incorporating our best
  1698. algorithms for solving the shotgun assembly problem. The system is highly
  1699. configurable and can perform fragment clipping, prescreening, and tagging
  1700. functions, shotgun assebmly with or without constraints, and sequence
  1701. finishing. An extensible input/output mechanism permits FAKtory to be
  1702. inserted into any informatics environment.
  1703. %K keywords
  1704. %Y
  1705.  
  1706. %A Myers, Gene
  1707. %T The GAF Data Exchange Format
  1708. %D Wednesday, February 3, 1999
  1709. %Z Wed, 08 Jan 99 00:00:00 GMT
  1710. %R TR99-02
  1711. %I The Department of Computer Science, University of Arizona
  1712. %U ftp://ftp.cs.arizona.edu/reports/1999/TR99-02.ps
  1713. %X GAF is a General Assembly Format for exchanging data in a sequencing
  1714. project. It provides constructs for specifying sequences,quality numbers,
  1715. assemblies, multi-alignments, overlaps between fragments, and constraints
  1716. between them. It is designed for coding the information at any point in
  1717. the assembly process, so for an example, a GAF file can specify just a
  1718. collection of fragments, a collection of fragments and assigned quality
  1719. numbers, a collection of fragments and their overlaps, an assembly of some
  1720. fragments, assemblies of cooperative software processes handling different
  1721. aspects of an overall sequencing informatics pipeline. A very simple
  1722. translation (using a simple awk script) can convert the CAF format
  1723. introduced by the Sanger group into a subset of the GAF format.
  1724. %K keywords
  1725. %Y
  1726.  
  1727. %A Miller, Susan J.
  1728. %A Jain, Mudita
  1729. %A Anson, Eric
  1730. %A Myers, Gene
  1731. %T Interface for the FAKII Fragment Assembly Kernel
  1732. %D Wednesday, February 3, 1999
  1733. %Z Wed, 08 Jan 99 00:00:00 GMT
  1734. %R TR99-01
  1735. %I The Department of Computer Science, University of Arizona
  1736. %U ftp://ftp.cs.arizona.edu/reports/1999/TR99-01.ps
  1737. %X This document describes the C programming language interface to our FAKII
  1738. Fragment Assembly Kernel library. Inputs to the Fragment Assembly Kernel
  1739. are (1)DNA fragment sequences from potentially inaccurate sequencing
  1740. experiments, and (2) optional constraints on fragment assembly such as
  1741. known fragment overlaps or relative fragment orientation. Fragment sequence
  1742. version control is supported. The Fragment Assembly Kernel produces the
  1743. most probable reconstructions of the original Dna sequence from the fragments,
  1744. subject to any specified constraints. Each fragment assembly includes
  1745. multiple sequence alignment and concsensu sequences. Multiple sequence
  1746. alignment editing capabilities are provided to allow manual correction
  1747. of sequence errors.
  1748. %K keywords
  1749. %Y
  1750.  
  1751. %A Debray, Saumya
  1752. %A Muth, Robert
  1753. %A Watterson, Scott
  1754. %T Link-time Improvement of Scheme Programs
  1755. %D Wednesday, December 16, 1998
  1756. %Z Wed, 08 Jan 98 00:00:00 GMT
  1757. %R TR98-16
  1758. %I The Department of Computer Science, University of Arizona
  1759. %U ftp://ftp.cs.arizona.edu/reports/1998/TR98-16.ps.Z
  1760. %X Optimizing compilers typically limit the scope of their analyses and
  1761. optimizations to individual modules.  This has two drawbacks: first,
  1762. library code cannot be optimized together with their callers, which
  1763. implies that reusing code through libraries incurs a penalty; and
  1764. second, the results of analysis and optimization cannot be propagated from
  1765. an application module written in one language to a module written in
  1766. another.  A possible solution is to carry out (additional) program
  1767. optimization at link time.  This paper describes our experiences with
  1768. such optimization using two different optimizing Scheme compilers,
  1769. and several benchmark programs, via alto, a link-time optimizer we
  1770. have developed for the DEC Alpha architecture.  Experiments indicate
  1771. that significant performance improvements are possible via link-time
  1772. optimization even when the input programs have already been subjected to
  1773. high levels of compile-time optimization.
  1774. %K optimizing compilers, link-time
  1775. %Y
  1776.  
  1777. %A Soo, Michael
  1778. %T Constructing a Temporal Database Management System
  1779. %D Tuesday, December 15, 1998
  1780. %Z Wed, 08 Jan 98 00:00:00 GMT
  1781. %R TR98-15
  1782. %I The Department of Computer Science, University of Arizona
  1783. %U ftp://ftp.cs.arizona.edu/reports/
  1784. %X abstract
  1785. %K dissertation, not available online
  1786. %Y
  1787.  
  1788. %A Muth, Robert
  1789. %A Debray, Saumya
  1790. %A Watterson, Scott
  1791. %A de Bosschere, Koen
  1792. %T alto: A Link-Time Optimizer for the DEC Alpha
  1793. %D Wednesday, December 9, 1998
  1794. %Z Wed, 08 Jan 98 00:00:00 GMT
  1795. %R TR98-14
  1796. %I The Department of Computer Science, University of Arizona
  1797. %U ftp://ftp.cs.arizona.edu/reports/1998/TR98-14.ps.Z
  1798. %X Traditional optimizing compilers are limited in the scope of their
  1799. optimizations by the fact that only a single function, or possibly a
  1800. single module, is available for analysis and optimization.  In particular,
  1801. this means that library routines cannot be optimized to specific calling
  1802. contexts.  Other optimization opportunities, exploiting information not
  1803. available before linktime such as addresses of variables and the final code
  1804. layout, are often ignored because linkers are traditionally unsophisticated.
  1805. A possible solution is to carry out whole-program optimization at link time.
  1806. This paper describes {\tt alto}, a link-time optimizer for the DEC Alpha
  1807. architecture.  It is able to realize significant performance improvements
  1808. even for programs compiled with a good optimizing compiler with a high level
  1809. of optimization.  The resulting code is considerably faster that that
  1810. obtained using the OM link-time optimizer, even when the latter is used in
  1811. conjunction with profile-guided and inter-file compile-time optimizations.
  1812. %K supersedes TR96-15
  1813. %Y
  1814.  
  1815. %A Spalink, Tammo
  1816. %A Hartman, John
  1817. %A Gibson, Garth
  1818. %T The Effect of Mobile Code on File Service
  1819. %D Monday, November 16, 1998
  1820. %Z Wed, 08 Jan 98 00:00:00 GMT
  1821. %R TR98-12
  1822. %I The Department of Computer Science, University of Arizona
  1823. %U ftp://ftp.cs.arizona.edu/reports/1998/TR98-12.ps.Z/
  1824. %X Mobile code promises to improve the functionality and performance of
  1825. applications, but may have a detrimental effect on overall system
  1826. performance.  In this paper we consider the effect of moving an
  1827. application from a client to a file server, both on the application
  1828. and the server.  Under what circumstances does application performance
  1829. improve, and does it come at the expense of other (non-mobile)
  1830. background applications using the same server?  We use a trace-driven
  1831. simulation to measure the effect of mobile code, allowing system
  1832. parameters such as the size of the server memory and server speed
  1833. relative to client speed to be varied. We found that several factors
  1834. influence the benefit of mobile code. Server memory does not appear to
  1835. be a significant problem; relatively small server caches have a high
  1836. hit rate even when shared with mobile code. The relative CPU
  1837. performance of the client and server has a bigger effect on system
  1838. performance: mobile code should not be run on the server if its CPU is
  1839. a bottleneck.
  1840. %K mobile code
  1841. %Y
  1842.  
  1843. %A Moon, Bongki 
  1844. %A Vega Lopez, Ines Fernando
  1845. %A Immanuel, Vijaykumar
  1846. %T Scalable Algorithms for Large-Scale Temporal Aggregation
  1847. %D Monday, November 2, 1998
  1848. %Z Wed, 08 Jan 98 00:00:00 GMT
  1849. %R TR98-11
  1850. %I The Department of Computer Science, University of Arizona
  1851. %U ftp://ftp.cs.arizona.edu/reports/1998/TR98-11.ps.Z/
  1852. %X The ability to model time-varying natures is essential to
  1853. many database applications such as data warehousing and mining.
  1854. However, the temporal aspects provide many unique characteristics
  1855. and challenges for query processing and optimization.
  1856. Among the challenges is computing temporal aggregates, which is complicated
  1857. by having to compute temporal grouping.
  1858. In this paper, we introduce a variety of temporal aggregation algorithms
  1859. that overcome major drawbacks of previous work.
  1860. First, for small-scale aggregations, both the worst-case and average-case
  1861. processing time have been improved significantly.
  1862. Second, for large-scale aggregations, the proposed algorithms can deal with
  1863. a database that is substantially larger than the size of available memory.
  1864. Third, the parallel algorithm designed on a shared-nothing architecture
  1865. achieves scalable performance by delivering nearly linear scale-up and speed-up.
  1866. The contributions made in this paper are particularly important because
  1867. the rate of increase in database size and response time requirements
  1868. has out-paced advancements in processor and mass storage technology.
  1869. %K large-scale temporal aggregation
  1870. %Y
  1871.  
  1872. %A Peterson, Larry L.
  1873. %A Spatscheck, Oliver
  1874. %T Defending Against Denial of Service Attacks in Scout
  1875. %D Thursday, September 24, 1998
  1876. %Z Wed, 08 Jan 98 00:00:00 GMT
  1877. %R TR98-10
  1878. %I The Department of Computer Science, University of Arizona
  1879. %U ftp://ftp.cs.arizona.edu/reports/1998/TR98-10.ps.Z/
  1880. %X We describe a two-dimensional architecture for defending against denial
  1881. of service attacks. In one dimension, the architecture accounts for all
  1882. resources consumed by each I/O path in the system; this accounting mechanism
  1883. is implemented as an extension to the path object in the Scout operating
  1884. system. In the second dimension, the various modules that define each path
  1885. can be configured in separate protection domains; we implement hardware
  1886. enforced protection domains, although other implementations are possible.
  1887. The resulting system---which we call Escort---is the first example of a
  1888. system that simultaneously does end-to-end resource accounting (thereby
  1889. protecting against denial of service attacks) and supports multiple
  1890. protection domains (thereby allowing untrusted modules to be isolated from
  1891. each other). The paper describes the Escort architecture and its
  1892. implementation in Scout, and reports a collection of experiments that
  1893. measure the costs and benefits of using Escort to protect a web server
  1894. from denial of service attacks.
  1895. %K Scout, Escort, Defending
  1896. %Y
  1897.  
  1898. %A Gendrano, Jose Alvin
  1899. %A Huang, Bruce C.
  1900. %A Rodrigue, Jim M.
  1901. %A Moon, Bongki
  1902. %A Snodgrass, Richard T.
  1903. %T Parallel Algorithms for Computing Temporal Aggregates
  1904. %D Monday, August 31, 1998
  1905. %Z Wed, 08 Jan 98 00:00:00 GMT
  1906. %R TR98-09
  1907. %I The Department of Computer Science, University of Arizona
  1908. %U ftp://ftp.cs.arizona.edu/reports/1998/TR98-09.ps.Z/
  1909. %X The ability to model the temporal dimension is essential to many
  1910. applications. Furthermore, the rate of increase in database size and
  1911. response time requirements has out-paced advancements in processor and
  1912. mass storage technology, leading to the need for parallel temporal database
  1913. management systems.  In this paper, we introduce a variety of parallel
  1914. temporal aggregation algorithms for a shared-nothing architecture based on
  1915. the sequential Aggregation Tree algorithm.  Via an empirical study, we found
  1916. that the number of processing nodes, the partitioning of the data, the
  1917. placement of results, and the degree of data reduction effected by the
  1918. aggregation impacted the performance of the algorithms in different ways.
  1919. We designed the Time Division Merge algorithm to produce distributed result
  1920. placement, as differentiated from the centralized result strategies used by
  1921. the other proposed algorithms.  For centralized results and high data
  1922. reduction, we found that the Pairwise Merge algorithm was preferred regardless
  1923. of the number of processing nodes, but for low data reduction it was only
  1924. preferred up to 32 nodes, while a variant of Time Division Merge was best
  1925. for larger configurations.
  1926. %K keywords
  1927. %Y
  1928.  
  1929. %A Baker, Scott M.
  1930. %A Moon, Bongki
  1931. %T Scalable Web Server Design for Distributed Data Management
  1932. %D Wednesday, August 19, 1998
  1933. %Z Wed, 08 Jan 98 00:00:00 GMT
  1934. %R TR98-08
  1935. %I The Department of Computer Science, University of Arizona
  1936. %U ftp://ftp.cs.arizona.edu/reports/1998/TR98-08.ps.Z/
  1937. %X Traditional techniques for a distributed web server design rely on
  1938. manipulation of central resources, such as routers or DNS services,
  1939. to distribute requests designated for a single IP address to
  1940. multiple web servers.
  1941. The goal of the Distributed Cooperative Web Server (DCWS)
  1942. system development is to explore application-level techniques for
  1943. distributing web content.  We achieve this by dynamically manipulating
  1944. the hyperlinks stored within the web documents themselves.  The DCWS
  1945. system effectively eliminates the bottleneck of centralized resources,
  1946. while balancing the load among distributed web servers.  DCWS servers
  1947. may be located in different networks, or even different continents and
  1948. still balance load effectively.  DCWS system design is fully compatible
  1949. with existing HTTP protocol semantics and existing web client software
  1950. products.
  1951. %K DCWS, HTTP
  1952. %Y
  1953.  
  1954. %A Datta, Anindya
  1955. %A Moon, Bongki
  1956. %A Ramamritham, Krithi 
  1957. %A Thomas, Helen 
  1958. %A Viguier, Igor 
  1959. %T Have Your Data and Index It, too
  1960. %D Monday, August 17, 1998
  1961. %Z Wed, 08 Jan 98 00:00:00 GMT
  1962. %R TR98-07
  1963. %I The Department of Computer Science, University of Arizona
  1964. %U ftp://ftp.cs.arizona.edu/reports/1998/TR98-07.ps.Z/
  1965. %X Two possible strategies may be utilized to enhance the efficiency
  1966. of processing OLAP queries: (a) precomputation strategies (e.g., view
  1967. materialization, realizing data cubes), and (b) ad-hoc strategies.
  1968. While a significant amount of work has been done in developing
  1969. precomputation strategies, it is generally recognized that it is
  1970. difficult to materialize the answers to all possible queries. Thus,
  1971. ad-hoc querying must be supported in data warehouses. This realization
  1972. has sparked an interest in exploring indexing strategies suitable
  1973. for OLAP queries. There appears to have been relatively little work
  1974. done in ad-hoc query support for data 
  1975. warehouses~\cite{og:95,oq:97,sarawagi:97,kr:98}.
  1976.     In this paper we propose {\em DataIndexes} as a new paradigm for
  1977. storing the base data.  {\em An attractive feature of DataIndexes is that
  1978. they serve as indexes as well as the store of base data.} Thus, DataIndexes
  1979. actually define a physical design strategy for a data warehouse where the
  1980. indexing, for all intents and purposes, comes for ``free''. We also present
  1981. two efficient algorithms for performing star-joins with DataIndexes. In
  1982. addition, we present a mathematical analysis of all the indexes presented
  1983. by O'Neil and Quass as well as our DataIndexes and present analytical
  1984. expressions categorizing the cost of query evaluation using these structures
  1985. for range selections and star-joins, two common classes of queries in OLAP.
  1986. These aid in performing an analysis yielding precise ``break-even" points
  1987. for comparing these indexing alternatives. Overall, it turns out that
  1988. DataIndexes are very attractive in a wide variety of cases in terms of
  1989. enhancing the performance of range and star-join queries in data warehouses.
  1990. %K data, index, OLAP
  1991. %Y
  1992.  
  1993. %A Hiltunen, Matti
  1994. %A Schlichting, Richard D.
  1995. %A Han, Xiaonan
  1996. %A Cardozo, Melvin M.
  1997. %A Das, Rajsekhar
  1998. %T Real-Time Dependable Channels: Customizing QoS Attributes for Distributed
  1999. Systems
  2000. %D Wednesday, July 1, 1998
  2001. %Z Wed, 08 Jan 98 00:00:00 GMT
  2002. %R TR98-06
  2003. %I The Department of Computer Science, University of Arizona
  2004. %U ftp://ftp.cs.arizona.edu/reports/1998/TR98-06.ps.Z/
  2005. %X Communication services that provide enhanced Quality of Service
  2006. (QoS) guarantees related to dependability and real time are important
  2007. for many applications in distributed systems. This paper presents
  2008. real-time dependable (RTD) channels, a communication-oriented abstraction
  2009. that can be configured to meet the QoS requirements of a variety of
  2010. distributed applications. This customization ability is based on using
  2011. CactusRT, a system that supports the construction of middleware services
  2012. out of software modules called micro-protocols. Each micro-protocol
  2013. implements a different semantic property or property variant, and
  2014. interacts with other micro-protocols using an event-driven model
  2015. supported by the CactusRT runtime system. In addition to RTD channels,
  2016. CactusRT and its implementation are described. This prototype executes
  2017. on a cluster of Pentium PCs running the OpenGroup/RI MK 7.3 Mach
  2018. real-time operating system and CORDS, a system for building network
  2019. protocols based on the x-kernel.
  2020. %K keywords
  2021.  
  2022. %A Sarkar, Prasenjit
  2023. %T Title
  2024. %D Wednesday, July 1, 1998
  2025. %Z Wed, 08 Jan 98 00:00:00 GMT
  2026. %R TR98-05
  2027. %I The Department of Computer Science, University of Arizona
  2028. %U ftp://ftp.cs.arizona.edu/reports/1998/TR98-05.ps.Z/
  2029. %X abstract
  2030. %K dissertation
  2031. %Y
  2032.  
  2033. %A Yeatts, Andrey
  2034. %T A Graphical User Interface Design Paradigm Based on Production Rules
  2035. %D Tuesday, June 9, 1998
  2036. %Z Wed, 08 Jan 97 00:00:00 GMT
  2037. %R TR98-04
  2038. %I The Department of Computer Science, University of Arizona
  2039. %U 
  2040. %X abstract
  2041. %K PhD dissertation
  2042. %Y not available online
  2043.  
  2044. %A Peterson, Larry
  2045. %T Title
  2046. %D Friday, March 13, 1998
  2047. %Z Wed, 08 Jan 98 00:00:00 GMT
  2048. %R TR98-03
  2049. %I The Department of Computer Science, University of Arizona
  2050. %U
  2051. %X abstract
  2052. %K keywords
  2053. %Y
  2054.  
  2055. %A Sundaram, Rajesh
  2056. %T Design and Implementation of the Swarm Storage Server
  2057. %D Tuesday, March 10, 1998
  2058. %Z Wed, 08 Jan 98 00:00:00 GMT
  2059. %R TR98-02
  2060. %I The Department of Computer Science, University of Arizona
  2061. %U ftp://ftp.cs.arizona.edu/reports/1998/TR98-02.ps.Z/
  2062. %X The Swarm storage system uses log-based striping to achieve high
  2063. performance. Clients collect application writes in a log and stripe the
  2064. log across multiple storage servers to aggregate server bandwidth. The
  2065. Swarm storage server has been designed to meet various requirements of the
  2066. Swarm storage system. These include high performance for data-intensive
  2067. operations, rapid crash recovery, security support and atomic interface
  2068. routines. The design of the Swarm storage server is simple enough to
  2069. allow its implementation as a network appliance.
  2070. %K Swarm, log-based, atomic interface routines
  2071. %Y
  2072.  
  2073. %A Spatscheck, Oliver
  2074. %A Hansen, Jorgen S.
  2075. %A Hartman, John H.
  2076. %A Peterson, Larry
  2077. %T Optimizing TCP Forwarder Performance
  2078. %D Monday, February 9, 1998
  2079. %Z Mon, 09 Feb 98 00:00:00 GMT
  2080. %R TR98-01
  2081. %I The Department of Computer Science, University of Arizona
  2082. %U ftp://ftp.cs.arizona.edu/reports/1998/TR98-01.ps.Z/
  2083. %X A TCP forwarder is a network node that establishes and
  2084. forwards data between a pair of TCP connections.  For example, a
  2085. firewall that places a proxy between a TCP connection to an external
  2086. host and a TCP connection to an internal host---for the purpose of
  2087. implementing access control to a resource on the internal host---is an
  2088. example of a TCP forwarder. Once the proxy approves the access, it
  2089. simply forwards data from one connection to the other.  We use the
  2090. term {\it TCP forwarding} to describe indirect TCP communication via a
  2091. proxy in general.  This paper characterizes the behavior of TCP
  2092. forwarding, and illustrates the role TCP forwarding plays in common
  2093. network services like firewalls and HTTP proxies. We introduce an
  2094. optimization technique, called {\it connection splicing}, that can
  2095. applied to a TCP forwarder, and reports the results of a performance
  2096. study designed to evaluate its impact.  Connection splicing has the
  2097. effect of improving the performance of TCP forwarding by a factor of
  2098. two to four, making it competitive with the performance of an IP
  2099. router running on the same hardware.
  2100. %K TCP, network, node, internal host, firewalls
  2101. %Y
  2102.  
  2103. %A Mosberger, David
  2104. %T Message Library Design Notes
  2105. %D Tuesday, November 25, 1997
  2106. %Z Wed, 08 Jan 97 00:00:00 GMT
  2107. %R TR97-19
  2108. %I The Department of Computer Science, University of Arizona
  2109. %U ftp://ftp.cs.arizona.edu/reports/1997/TR97-19.ps.Z
  2110. %X This document describes the current implementation of the x -kernel
  2111. message library. The focus is on its data structures and the underlying
  2112. principles. This document does not describe the message librarys
  2113. in-terface or how it is used. Please refer to the x -kernel Programmers
  2114. Manual [1] and the x -kernel Tutorial [2] for that purpose.
  2115. %K x-kernel
  2116. %Y
  2117.  
  2118. %A Mosberger, David
  2119. %T Map Library Design Notes
  2120. %D Tuesday, November 25, 1997
  2121. %Z Wed, 08 Jan 97 00:00:00 GMT
  2122. %R TR97-18
  2123. %I The Department of Computer Science, University of Arizona
  2124. %U ftp://ftp.cs.arizona.edu/reports/1997/TR97-18.ps.Z
  2125. %X This document describes the current implementation of the x-kernel map
  2126. library. The focus is on its un-derlying data structures and algorithms.
  2127. This document does not describe the map librarys interface or how it is
  2128. used. Please refer to the x-kernel Programmers Manual [1] and the
  2129. x-kernel Tutorial [2] for that purpose.
  2130. %K x-kernel
  2131. %Y
  2132.  
  2133. %A Spatscheck, Oliver
  2134. %A Peterson, Larry
  2135. %T Escort: A Path-Based OS Security Architecture
  2136. %D Monday, November 17, 1997
  2137. %Z Wed, 08 Jan 97 00:00:00 GMT
  2138. %R TR97-17
  2139. %I The Department of Computer Science, University of Arizona
  2140. %U ftp://ftp.cs.arizona.edu/reports/1997/TR97-17.ps.Z
  2141. %X Escort is the security architecture for Scout, a configurable
  2142. operating system designed for network appliances. Scout is unique in
  2143. that it is designed around {\it paths}---a communication-centric
  2144. abstraction that encapsulates information flows through the
  2145. system---rather than the more traditional processes and servers. Scout
  2146. uses paths to make end-to-end resource allocation decisions. Escort
  2147. extends this idea to isolate these information flows, as well as to
  2148. provide end-to-end accountability. This paper introduces the Escort
  2149. security architecture, shows how it can be used to enforce common
  2150. security policies, and evaluates its design according to several
  2151. well-established criteria.
  2152. %K Escort, Scout
  2153. %Y
  2154.  
  2155. %A Hartman, John H.
  2156. %A Peterson, Larry P.
  2157. %A Bavier, Andy
  2158. %A Bigot, Peter
  2159. %A Bridges, Patrick
  2160. %A Montz, Brady
  2161. %A Piltz, Rob
  2162. %A Proebsting, Todd
  2163. %A Spatscheck, Oliver
  2164. %T Joust: A Platform for Communication-Oriented Liquid Software
  2165. %D Monday, November 17, 1997
  2166. %Z Wed, 08 Jan 97 00:00:00 GMT
  2167. %R TR97-16
  2168. %I The Department of Computer Science, University of Arizona
  2169. %U ftp://ftp.cs.arizona.edu/reports/1997/TR97-16.ps.Z
  2170. %X Joust is a software platform for liquid software---code that flows
  2171. easily from machine to machine.  Liquid software makes it easier to
  2172. maintain, debug, update, and customize networked systems.  One of the
  2173. most interesting applications of liquid software is to interject it
  2174. into the nodes of a network, allowing network functionality, such as
  2175. routing, to be customized.  Additional features, such as
  2176. special-purpose congestion control and filtering algorithms, are also
  2177. easily added.  The challenge is to develop a communication-oriented
  2178. platform for liquid software, one in which the focus is the efficient
  2179. transfer of data, not high-performance computation.  To this end we
  2180. have designed and implemented Joust, which consists of a complete
  2181. re-implementation of the Java virtual machine (including both the
  2182. runtime system and a just-in-time compiler), running on the Scout
  2183. operating system (a configurable, communication-oriented OS).  The
  2184. result is a configurable, high-performance platform for running
  2185. communication-oriented liquid software.  We present the results of
  2186. implementing three different liquid software applications on Joust,
  2187. including a prototype architecture for active networks.
  2188. %K Joust, Liquid Software, Java
  2189. %Y
  2190.  
  2191. %A Bavier, Andy
  2192. %A Montz, Brady
  2193. %A Peterson, Larry
  2194. %T Predicting MPEG Execution Times 
  2195. %D Monday, November 3, 1997
  2196. %Z Wed, 08 Jan 97 00:00:00 GMT
  2197. %R TR97-15
  2198. %I The Department of Computer Science, University of Arizona
  2199. %U ftp://ftp.cs.arizona.edu/reports/1997/TR97-15.ps.Z
  2200. %X This paper reports on a set of experiments that measure the amount of
  2201. CPU processing needed to decode MPEG-compressed video in software.
  2202. These experiments were designed to discover indicators that could be
  2203. used to predict how many cycles are required to decode a given
  2204. frame. Such predictors can be used to do more accurate CPU scheduling.
  2205. We found that by considering both frame type and size, it is possible
  2206. to construct a linear model of MPEG decoding with $R^2$ values of 0.97
  2207. and higher. Moreover, this model can be used to predict decoding times
  2208. at both the frame and packet level that are almost always accurate to
  2209. within 25% of the actual decode times. This is a surprising result
  2210. given the large variability in MPEG decoding times, and suggests that
  2211. it is feasible to design systems that make quality of service
  2212. guarantees for MPEG-encoded video, rather than less variable
  2213. encodings, such as JPEG.
  2214. %K keywords
  2215. %Y
  2216.  
  2217. %A Lambright, H. Dan
  2218. %T Automated Verification of Mobile Code
  2219. %D October 24, 1997
  2220. %Z Wed, 08 Jan 97 00:00:00 GMT
  2221. %R TR97-14
  2222. %I The Department of Computer Science, University of Arizona
  2223. %U ftp://ftp.cs.arizona.edu/reports/1997/TR97-14.ps.Z
  2224. %X In this thesis, we introduce a new technique to automate the verification of
  2225. mobile code. Using dataflow analysis techniques, the verifier can check
  2226. whether data passed between trusted software components is illegally modified
  2227. by untrusted mobile code. We show that this analysis is powerful enough to
  2228. make significant guarantees about whether the program will access system
  2229. resources safely. Furthermore, by rendering the verification transparent to
  2230. the user, the security system is not vulnerable to human error, or dependent
  2231. on the user's technical abilities. Other verification techniques do not share
  2232. these advantages. We describe what requirements enable this analysis, explore
  2233. its limitations, and present prototype software that implements the idea.
  2234. %K dissertation
  2235. %Y
  2236.  
  2237. %A Debray, Saumya
  2238. %A Muth, Robert
  2239. %A Weippert, Matthew
  2240. %T Alias Analysis of Executable Code
  2241. %D July 18, 1997
  2242. %Z Wed, 08 Jan 97 00:00:00 GMT
  2243. %R TR97-13
  2244. %I The Department of Computer Science, University of Arizona
  2245. %U ftp://ftp.cs.arizona.edu/reports/1997/TR97-13.ps.Z
  2246. %X Recent years have seen increasing interest in systems that reason about and
  2247. manipulate executable code.  Such systems can generally benefit from
  2248. information about aliasing.  Unfortunately, most existing alias analyses
  2249. are formulated in terms of high-level language features, and are unable
  2250. to cope with features, such as pointer arithmetic, that pervade executable
  2251. programs.  This paper describes a simple algorithm that can be used to
  2252. obtain aliasing information for executable code.
  2253. In order to be practical, the algorithm is careful to keep its memory
  2254. requirements low, sacrificing precision where necessary to achieve this
  2255. goal.  Experimental results indicate that it is nevertheless able to
  2256. provide a reasonable amount of information about memory
  2257. references across a variety of benchmark programs.
  2258. %K keywords
  2259. %Y
  2260.  
  2261. %A Bhatti, Nina T.
  2262. %A Hiltunen, Matti A.
  2263. %A Schlichting, Richard D.
  2264. %A Chiu, Wanda
  2265. %T Coyote: A System for Constructing Fine-Grain Configurable Communication
  2266. Services
  2267. %D July 7, 1997
  2268. %Z Wed, 08 Jan 97 00:00:00 GMT
  2269. %R TR97-12
  2270. %I The Department of Computer Science, University of Arizona
  2271. %U ftp://ftp.cs.arizona.edu/reports/1997/TR97-12.ps.Z
  2272. %X Communication-oriented abstractions such as atomic multicast, group RPC,
  2273. and protocols for location-independent mobile computing can simplify the
  2274. development of complex applications built on distributed systems.  This
  2275. paper describes Coyote, a system that supports the construction of highly
  2276. modular and configurable versions of such abstractions. Coyote extends the
  2277. notion of protocol objects and hierarchical composition found in existing
  2278. systems with support for finer-grain objects called micro-protocols that
  2279. implement individual semantic properties of the target service.  A customized
  2280. service is constructed by selecting micro-protocols based on their semantic
  2281. guarantees and configuring them together with a standard runtime system to
  2282. form a composite protocol implementing the service. Micro-protocols within
  2283. a composite protocol can share data and are executed using an event-driven
  2284. paradigm that enhances configurability. The overall approach is described
  2285. and illustrated with examples of services that have been constructed using
  2286. Coyote, including atomic multicast, group RPC, membership, and mobile
  2287. computing protocols. A prototype implementation based on extending
  2288. {\it x}-kernel version 3.2 running on Mach MK82 with support for
  2289. micro-protocols is also presented, together with performance results from
  2290. a suite of micro-protocols from which over 60 variants of group RPC can be
  2291. constructed.
  2292. %K keywords
  2293. %Y
  2294.  
  2295. %A Jain, Mudita
  2296. %T Algorithms for Physical Mapping Using Unique Probes
  2297. %D June 9, 1997
  2298. %Z Wed, 08 Jan 97 00:00:00 GMT
  2299. %R TR97-11
  2300. %I The Department of Computer Science, University of Arizona
  2301. %U 
  2302. %X DNA molecules are sequences of characters over a four letter alphabet.
  2303. Determining the text of the DNA sequence contained in human cells is the goal
  2304. of the Human Genome Project. The structure of a DNA sequence is reconstructed
  2305. from a set of shorter fragments sampled from it at unknown locations, as it
  2306. is usually too long to be determined directly. We consider the problem when
  2307. the fragments are very long, and each fragment has a fingerprint consisting
  2308. of the presence of two or three pre-selected, smaller sequences called probes
  2309. within it. These probes have a unique location along the original DNA sequence.
  2310. The fingerprints contain false negative and false positive errors, and the
  2311. fragments may be chimeric. A physical map of a DNA sequence is a reconstruction
  2312. of the order of the probes and fragments along it. In short, given a collection
  2313. of fragments, with fingerprints for each fragment taken from a collection of
  2314. probles, and parameters that bound the rates of false negatives, false
  2315. positives, and chimeras in the input data, the problem is to find the most
  2316. likely probe ordering.
  2317.     Physical mapping in NP-complete when the input data contains errors.
  2318. To contstruct physical maps we first determine neighbourhoods of probes and
  2319. clones that are highly likely to be adjacent on the original DNA sequence.
  2320. We then use a new, versatile integer programming formulation of the problem,
  2321. to derive heuristics for ordering probes within neighbourhoods. This
  2322. formulation provides a single, uniform representation for diverse data such
  2323. as end-clone probes and in-situ hybridization, and provides a natural medium
  2324. for the integration of previously constructed maps with newer data. We also
  2325. present an ordering heuristic based upon end-clone data. Finally, we connect
  2326. these local permutations into a larger, more global probe permutation. For
  2327. this we use heuristics that have at their core previously mapped data. All
  2328. heuristics are implemented and evaluated by comparing the computed probe
  2329. orderings to the original probe orderings for simulated data.
  2330. %K dissertation; not available online
  2331. %Y
  2332.  
  2333. %A Han, Xiaonan Han
  2334. %A Hiltunen, Matti A.
  2335. %A Schlichting, Richard D.
  2336. %T Supporting Configurable Real-Time Communication Services
  2337. %D June 5, 1997
  2338. %Z Wed, 08 Jan 97 00:00:00 GMT
  2339. %R TR97-10 
  2340. %I The Department of Computer Science, University of Arizona
  2341. %U ftp://ftp.cs.arizona.edu/reports/1997/TR97-10.ps.Z
  2342. %X abstract
  2343. %K keywords
  2344. %Y
  2345.  
  2346. %A Evans, William
  2347. %A Kirkpatrick, David
  2348. %A Townsend, Gregg
  2349. %T Right Triangular Irregular Networks
  2350. %D May 30, 1997
  2351. %Z Wed, 08 Jan 97 00:00:00 GMT
  2352. %R TR97-09
  2353. %I The Department of Computer Science, University of Arizona
  2354. %U ftp://ftp.cs.arizona.edu/reports/1997/TR97-09.ps.Z
  2355. %X We describe a hierarchical data structure for representing a digital
  2356. terrain (height field) which contains approximations of the terrain at
  2357. different levels of detail. The approximations are based on triangulations
  2358. of the underlying two-dimensional space using right-angled triangles.
  2359. The methods we discuss allow the approximation to precisely represent
  2360. the surface in certain areas while coarsely approximating the surface
  2361. in others. Thus, for example, the area close to an observer may be
  2362. represented with greater detail than areas which lie outside their field
  2363. of view.
  2364. We discuss the application of this hierarchical data structure to
  2365. the problem of interactive terrain visualization.  We point out some of
  2366. the advantages of this method in terms of memory usage and speed.
  2367. %K keywords
  2368. %Y
  2369.  
  2370. %A Coffman, Jr., E.G.
  2371. %A Downey, Peter J.
  2372. %A Winkler, Peter
  2373. %T A Note on Packing Rectangles in Groups
  2374. %D May 15, 1997
  2375. %Z Wed, 08 Jan 97 00:00:00 GMT
  2376. %R TR97-07
  2377. %I Department of Computer Science, The University of Arizona
  2378. %U ftp://ftp.cs.arizona.edu/reports/1997/TR97-07.ps.Z
  2379. %X Rectangles from a list of length n are packed into a
  2380. unit width strip.  The rectangles have dimensions independently chosen
  2381. from a uniform distribution on [0, 1], and the packing objective is to
  2382. minimize the expected height of the packing of n items.
  2383. The packing algorithms of interest must operate on-line, as well as adhere
  2384. to a constraint reminiscent of the Tetris game: rectangles arrive from
  2385. the top and must be moved at arrival without overlap within the strip
  2386. to reach their final placement.  This paper assumes no rotation of rectangles.
  2387. The Group Packing algorithm GP_3 packs rectangles densely in groups of 3
  2388. at a time, starting a new level at the highest point reached by any
  2389. rectangle in the group.  The GP_3 algorithm achieves an asymptotic
  2390. expected height of (0.38541 ... ) n.  This is slightly worse than
  2391. the bound (0.38134 ... ) n achieved by Next Fit Level (NFL) packing.
  2392. %K two-dimensional bin-packing, strip packing, on-line algorithms, lower bounds
  2393. %Y
  2394.  
  2395. %A Mosberger-Tang, David
  2396. %T SCOUT: A Path-based Operating System
  2397. %D May 13, 1997
  2398. %Z Wed, 08 Jan 97 00:00:00 GMT
  2399. %R TR97-06
  2400. %I The Department of Computer Science, University of Arizona
  2401. %U ftp://ftp.cs.arizona.edu/reports/1997/TR97-06.ps.Z
  2402. %X Scout is a new operating system architecture that is designed
  2403. specifically to accommodate the needs of communication-centric
  2404. systems. An important class of such systems is formed by information
  2405. appliances, which, broadly speaking, are devices whose primary task is
  2406. to facilitate communication. Appliances are typically relatively
  2407. small, special-purpose, and often mobile devices such as remote
  2408. controls, personal information managers, network-attached disks,
  2409. cameras, displays, or dedicated file-servers.
  2410. Scout has a modular structure that is complemented by a new
  2411. abstraction called the path. The modular structure enables the
  2412. efficient building of systems that are tailored precisely to the
  2413. requirements of a particular appliance.  Paths address issues related
  2414. to the performance and quality with which a communication service is
  2415. rendered. A path can be visualized as a vertical slice through a
  2416. layered system or viewed abstractly as a bidirectional flow of
  2417. data. As such, a path typically traverses multiple modules in a Scout
  2418. system. This means that paths provide additional context to the
  2419. modules that process data that is being communicated through the
  2420. system. This context often makes it possible to implement data
  2421. processing more efficiently or to improve the quality with which
  2422. resource management, such as CPU scheduling or memory allocation, is
  2423. realized.
  2424. This dissertation develops the path abstraction from first principles
  2425. and then introduces the various aspects of the Scout
  2426. architecture. Aside from the path abstraction, Scout uses a novel
  2427. approach for network packet classification.  With the Scout
  2428. architecture defined, two studies are presented that provide an
  2429. in-depth look at how to use Scout and its path abstraction. The first
  2430. study employs the path abstraction to reduce processing latency in the
  2431. networking subsystem. Evaluating these path optimizations also
  2432. provides important insights on the performance behavior of networking
  2433. subsystems on modern RISC machines. The second study employs the path
  2434. abstraction to improve resource management for an information
  2435. appliance that involves a networked TV displaying MPEG encoded video.
  2436. %K dissertation
  2437. %Y
  2438.  
  2439. %A Gopal, Burra
  2440. %T Integrating Content-Based Access Mechanisms with Hierarchical File Systems
  2441. %D April 18, 1997
  2442. %Z Wed, 08 Jan 97 00:00:00 GMT
  2443. %R TR97-05
  2444. %I The Department of Computer Science, University of Arizona
  2445. %U ftp://ftp.cs.arizona.edu/reports/1997/TR97-05.ps.Z
  2446. %X We describe a new file system that provides, at the same time,
  2447. both name and content based access to files. To make this possible,
  2448. we introduce the concept of a semantic directory. Every
  2449. semantic directory has a query associated with it. When a user
  2450. creates a semantic directory, the file system automatically creates
  2451. a set of pointers to the files in the file system that satisfy
  2452. the query associated with the directory. This set of pointers is
  2453. called the query-result of the directory. To access the files
  2454. that satisfy the query, users just need to de-reference the
  2455. appropriate pointers. Users can also create files and sub-directories
  2456. within semantic directories in the usual way. Hence, users can
  2457. organize files in a hierarchy and access them by specifying path names,
  2458. and at the same time, retrieve files by asking queries that
  2459. describe their content.
  2460.     Our file system also provides facilities for query-refinement and customization. When a user creates a new semantic sub-directory within a semantic directory, the file system ensures that the query-result of the sub-directory is a subset of the query-result of its parent. Hence, users can create a hierarchy of semantic directories to refine their queries. Users can also edit the set of pointers in a semantic directory, and thereby modify its query-result without modifying its query or the files in the file system. In this way, users can customize the results of queries according to their personal tastes, and use customized results to refine queries in the future.  That is, users do not have to depend solely on the query language to achieve these objectives.
  2461.     Our file system has many other features, including semantic mount-points that allow users to access information in other file systems by content.  The file system does not depend on the query language used for content-based access. Hence, it is possible to integrate any content-based access mechanism into our file system.
  2462. %K dissertation
  2463. %Y
  2464.  
  2465. %A Coffman, E.G., Jr.
  2466. %A Downey, Peter
  2467. %A Winkler, Peter
  2468. %T Packing Rectangles in a Strip
  2469. %D April 8, 1997
  2470. %Z Wed, 08 Jan 97 00:00:00 GMT
  2471. %R TR97-04
  2472. %I The Department of Computer Science, University of Arizona
  2473. %U ftp://ftp.cs.arizona.edu/reports/1997/TR97-04.ps.Z
  2474. %X Rectangles with dimensions independently chosen from
  2475. a uniform distribution on [0, 1] are packed on-line into a
  2476. unit width strip under a constraint like that of the Tetris game:
  2477. rectangles arrive from the top and must be moved inside the strip
  2478. to reach their place; once placed, they cannot be moved again.
  2479. Cargo loading applications impose similar constraints.
  2480. This paper assumes that rectangles must be moved without rotation.
  2481. For n rectangles, the resulting packing
  2482. height is shown to have an asymptotic expected value of at least
  2483. (0.31382733 ... )n under any on-line packing algorithm.  An on-line
  2484. algorithm is presented that achieves an asymptotic expected height of
  2485. (0.36976421 ... )n.  This algorithm improves the bound achieved in
  2486. Next Fit Level (NFL) packing, by compressing the items packed on
  2487. two successive levels of an NFL packing via on-line movement
  2488. admissible under the Tetris-like constraint.
  2489. %K two-dimensional bin-packing, strip packing, on-line algorithms, lower bounds
  2490. %Y
  2491.  
  2492. %A Brakmo, Lawrence
  2493. %T End-To-End Congestion Detection and Avoidance in Wide Area Networks
  2494. %D 03/10/97
  2495. %Z Wed, 08 Jan 97 00:00:00 GMT
  2496. %R TR97-03
  2497. %I The Department of Computer Science, University of Arizona
  2498. %U 
  2499. %X As human dependence on wide area networks like the Internet increases,
  2500. so does contention for the network's resources. This contention has
  2501. noticeably affected the performance of these networks, reducing their
  2502. usability. This dissertation addresses this problem in two ways.
  2503.     First, it describes TCP Vegas, a new implementation of TCP that
  2504. is distinguished from current TCP implementations by containing a new
  2505. congestion detection and avoidance mechanism. This mechanism was
  2506. designed to work in currently available wide area networks and achieves
  2507. between 37% and 71% better throughput on the Internet, with one-fifth
  2508. to one-half the losses, as compared to the current implementation of
  2509. TCP.
  2510.     Second is describes x-Sim, a network simulator based on the x-kernel,
  2511. that is able to simulate the topologies and traffic patterns of large
  2512. scale networks. The usefulness of the simulator to analyze and debug
  2513. network components is illustrated throughout this dissertation.
  2514. %K dissertation; not available online
  2515. %Y
  2516.  
  2517. %A Orman, Hilarie
  2518. %T The Oakley Key Determination Protocol
  2519. %D February 17, 1997
  2520. %Z Wed, 08 Jan 97 00:00:00 GMT
  2521. %R TR97-02
  2522. %I The Department of Computer Science, University of Arizona
  2523. %U ftp://ftp.cs.arizona.edu/reports/1997/TR97-02.ps.Z
  2524. %X This document describes a protocol, named OAKLEY, by which two authenticated
  2525. parties can agree on secure and secret keying material.  The basic mechanism is
  2526. the Diffie-Hellman key exchange algorithm.
  2527.     The OAKLEY protocol supports Perfect Forward Secrecy, compatibility
  2528. with the ISAKMP protocol for managing security associations, user-defined
  2529. abstract group structures for use with the Diffie-Hellman algorithm, key
  2530. updates, and incorporation of keys distributed via out-of-band mechanisms.
  2531. %K keywords
  2532. %Y
  2533.  
  2534. %A Proebsting, Todd A.
  2535. %A Townsend, Gregg
  2536. %A Bridges, Patrick
  2537. %A Hartman, John H. 
  2538. %A Newsham, Tim 
  2539. %A Watterson, Scott A.
  2540. %T Toba: Java For Applications: A Way Ahead of Time (WAT) Compiler
  2541. %D January 8, 1997
  2542. %Z Wed, 08 Jan 97 00:00:00 GMT
  2543. %R TR97-01
  2544. %I The Department of Computer Science, University of Arizona
  2545. %U ftp://ftp.cs.arizona.edu/reports/1997/TR97-01.ps.Z
  2546. %X Toba is a system for generating efficient standalone Java applications.
  2547. Toba includes a Java-bytecode-to-C compiler, a garbage collector, a threads
  2548. package, and Java API support. Toba-compiled Java applications execute
  2549. 1.5--10 times faster than interpreted and Just-In-Time compiled applications.
  2550. %K keywords
  2551. %Y
  2552.  
  2553. %A Bhatti, Nina
  2554. %T A System for Constructing Configurable High-level Protocols
  2555. %D Wednesday, December 4, 1996
  2556. %Z Wed, 23 Oct 96 00:00:00 GMT
  2557. %R TR96-22
  2558. %I The Department of Computer Science, University of Arizona
  2559. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-22.ps.Z
  2560. %X Distributed applications often require sophisticated communication services
  2561. such as multicast, membership, group RPC (GRPC), transactions, or support for
  2562. mobility.  These services form a large portion of the supporting software for
  2563. distributed applications, yet the specific requirements of the service vary
  2564. from application to application.  Constructing communication services that
  2565. are useful for multiple diverse applications while still being manageable
  2566. and efficient is a major challenge.
  2567. This dissertation focuses on improving the construction of complex
  2568. communication services.  The contributions of the dissertation are a new
  2569. model for the construction of such services and the design and implementation
  2570. of a supporting network subsystem. In this model, a communication service is
  2571. decomposed into distinct micro-protocols, each implementing a specific semantic
  2572. property.  Micro-protocols have well-defined interfaces that use events to
  2573. coordinate actions and communicate state changes, which results in a highly
  2574. modular and configurable implementation. 
  2575. This model augments, rather than replaces, the conventional hierarchical
  2576. protocol model.  In this implementation, a conventional {\it x}-kernel
  2577. protocol is replaced with a composite protocol in which micro-protocol objects
  2578. are linked with a standard runtime system that externally presents the standard
  2579. {\it x}-kernel interface.  Internally, the runtime system provides common
  2580. message services, enforces a uniform interface between micro-protocols, detects
  2581. and generates events, and synchronously or asynchronously executes event
  2582. handlers.
  2583. The viability of the approach is demonstrated by performance tests for several
  2584. different configurations of a suite of micro-protocols for a group RPC service.
  2585. The micro-protocols in this suite implement multiple semantic properties of
  2586. procedure call termination, message ordering, reliability, collation of
  2587. responses, call semantics, membership, and failure. The tests were conducted
  2588. while running within the {\it x}-kernel as a user level task on the Mach
  2589. operating system.
  2590. Additional micro-protocols for mobile computing applications validate the
  2591. generality of the model.  We designed micro-protocols for quality of service
  2592. (QoS), transmitting and renegotiating QoS parameters during handoffs, as well
  2593. as for mobility management, covering cell detection, handoff, and
  2594. disconnection.  This suite of micro-protocols can be configured to accommodate
  2595. a range of different service requirements or even to mimic existing mobile
  2596. architectures such as those found in the Crosspoint, PARC TAB, InfoPad, or
  2597. DataMan projects.
  2598. %K dissertation 
  2599. %Y
  2600.  
  2601. %A Kagedal, Andreas
  2602. %A Debray, Saumya
  2603. %T A Practical Approach to Structure Reuse of Arrays in Single Assignment
  2604. Languages
  2605. %D December 2, 1996
  2606. %Z Wed, 23 Oct 96 00:00:00 GMT
  2607. %R TR96-21
  2608. %I The Department of Computer Science, University of Arizona
  2609. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-21.ps.Z
  2610. %X Array updates in single assignment languages generally require some
  2611. copying of the array, and thus tend to be more expensive than in
  2612. imperative languages.  As a result, programs in single assignment
  2613. languages sometimes suffer from a performance handicap compared to
  2614. those in imperative languages.  Traditional attempts to address this
  2615. problem have typically involved either complex compile-time analyses,
  2616. which tend to be slow and fragile; or new language constructs, which
  2617. do not always interface with already existing code.  In this paper, we
  2618. propose a new approach to this problem, based on a simple and
  2619. straightforward program transformation, that we believe addresses the
  2620. shortcomings of both of these approaches: it is easy to understand,
  2621. efficiently implemented, does not require new language constructs, and
  2622. yet is applicable to most commonly encountered programs.
  2623. %K keywords
  2624. %Y
  2625.  
  2626. %A Debray, Saumya
  2627. %A Proebsting, Todd
  2628. %T Title
  2629. %D December 2, 1996
  2630. %Z Wed, 23 Oct 96 00:00:00 GMT
  2631. %R TR96-20
  2632. %I The Department of Computer Science, University of Arizona
  2633. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-20.ps.Z
  2634. %X abstract
  2635. %K keywords
  2636. %Y
  2637.  
  2638. %A Debray, Saumya
  2639. %T Resource-Bounded Partial Evaluation
  2640. %D November 18, 1996
  2641. %Z Wed, 23 Oct 96 00:00:00 GMT
  2642. %R TR96-19
  2643. %I The Department of Computer Science, University of Arizona
  2644. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-19.ps.Z
  2645. %X Most partial evaluators do not take the availability of machine-level
  2646. resources, such as registers or cache, into consideration when making their
  2647. specialization decisions.  The resulting resource contention can lead to
  2648. severe performance degradation---causing, in extreme cases, the specialized
  2649. code to run slower than the unspecialized code.  In this paper we consider
  2650. how resource availability considerations can be incorporated within a
  2651. partial evaluator.  We develop an abstract formulation of the problem, show
  2652. that optimal resource-bounded partial evaluation is NP-complete, and discuss
  2653. simple heuristics that can be used to address the problem in practice.
  2654. %K keywords
  2655. %Y
  2656.  
  2657. %A Muth, Robert
  2658. %A Debray, Saumya
  2659. %T On the complexity of Function Pointer May-Alias Analysis
  2660. %D October 25, 1996
  2661. %Z Wed, 23 Oct 96 00:00:00 GMT
  2662. %R TR96-18
  2663. %I The Department of Computer Science, University of Arizona
  2664. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-18.ps.Z
  2665. %X This paper considers the complexity of interprocedural function pointer
  2666. may-alias analysis, i.e., determining the set of functions that a function
  2667. pointer (in a language such as C) can point to at a point in a program.
  2668. This information is necessary, for example, in order to construct the
  2669. control flow graphs of programs that use function pointers, which in turn is
  2670. fundamental for most dataflow analyses and optimizations.  We show that the
  2671. general problem is complete for deterministic exponential time.  We then
  2672. consider two natural simplifications to the basic (precise) analysis and
  2673. examine their complexity.  The approach described can be used to readily
  2674. obtain similar complexity results for related analyses such as reachability
  2675. and recursiveness.
  2676. %K keywords
  2677. %Y
  2678.  
  2679. %A Tong, Bo-Ming
  2680. %A Leung, Ho-Fung
  2681. %T Load Balancing in a Distributed-Memory Or-Parallel System
  2682. %D Date issued
  2683. %Z Wed, 23 Oct 96 00:00:00 GMT
  2684. %R TR 96-17
  2685. %I The Department of Computer Science, University of Arizona
  2686. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-17.ps.Z
  2687. %X We consider or-parallel logic programming implementations on parallel
  2688. machines with no shared-memory. Traditional implementation techniques as
  2689. employed in Aurora and Muse are not applicable.  In our or-parallel execution
  2690. model, all processors perform identical work initially.  At each choice point,
  2691. processors are divided evenly among alternatives of the choice point.
  2692. Backtracking is employed if there are not enough processors for such a
  2693. division. As execution proceeds, the division of processors among alternatives
  2694. becomes uneven. In this paper, we present two different methods of load
  2695. balancing called equalization and apportion, aimed at improving the degree
  2696. of parallelism.  Equalization and apportion reallocates all processors to the
  2697. or-parallel branches by copying heaps through a interprocessor communication
  2698. network.
  2699. %K keywords
  2700. %Y
  2701.  
  2702. %A Pagels, Michael A.
  2703. %T Chimaera: A High-Bandwidth Network Interface Supporting Cooperative Tasks
  2704. %D Date issued
  2705. %Z Wed, 23 Oct 96 00:00:00 GMT
  2706. %R TR96-16
  2707. %I The Department of Computer Science, University of Arizona
  2708. %U 
  2709. %X abstract
  2710. %K not available online
  2711. %Y
  2712.  
  2713. %A DeBosschere, Koen
  2714. %A Debray, Saumya
  2715. %T alto: A Link-Time Optimizer for the DEC Alpha
  2716. %D Date issued
  2717. %Z Wed, 23 Oct 96 00:00:00 GMT
  2718. %R TR96-15
  2719. %I The Department of Computer Science, University of Arizona
  2720. %U 
  2721. %X abstract
  2722. %K see TR98-14
  2723. %Y
  2724.  
  2725. %A Ogurtsov, Nick
  2726. %A Orman, Hilarie
  2727. %A Schroeppel, Richard 
  2728. %A O'Malley, Sean
  2729. %A Spatscheck, Oliver
  2730. %T Covert Channel Elimination Protocols
  2731. %D Date issued
  2732. %Z Wed, 23 Oct 96 00:00:00 GMT
  2733. %R TR96-14
  2734. %I The Department of Computer Science, University of Arizona
  2735. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-14.ps.Z
  2736. %X With the increasing growth of electronic communications, it is becoming
  2737. important to provide a mechanism for enforcing various security policies
  2738. on network communications. This paper discusses our implementation of
  2739. several previously proposed protocols that enforce theell LaPadula
  2740. security model. We also introduce a new protocol called "Quantized Pump"
  2741. that offers several advantages, and present experimental results to
  2742. support our claims.
  2743. %K keywords
  2744. %Y
  2745.  
  2746. %A Afjeh, Abdollah A.
  2747. %A Homer, Patrick T.
  2748. %A Lewandowski, Henry 
  2749. %A Reed, John A.
  2750. %A Schlichting, Richard D.
  2751. %T Implementing Monitoring and Zooming in a Distributed Jet Engine Simulation
  2752. %D Date issued
  2753. %Z Wed, 23 Oct 96 00:00:00 GMT
  2754. %R TR96-13
  2755. %I The Department of Computer Science, University of Arizona
  2756. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-13.ps.Z
  2757. %X The NASA Numerical Propulsion System Simulation (NPSS) project is
  2758. exploring the use of computer simulation to facilitate the design of
  2759. new jet engines. Several key issues raised in this research are being
  2760. examined in an NPSS-related research project: zooming, monitoring and
  2761. control, and support for heterogeneity. The design and implementation
  2762. of a simulation executive that addresses each of these issues is described.
  2763. In this work, the strategy of zooming, which allows codes that model at
  2764. different levels of fidelity to be integrated within a single simulation,
  2765. is applied to the fan component of a turbofan propulsion system. A
  2766. prototype monitoring and control system supports experimentation with
  2767. expert system techniques for active control of the simulation. An
  2768. interconnection system provides a transparent means of connecting
  2769. the heterogeneous systems that comprise the prototype.
  2770. %K keywords
  2771. %Y
  2772.  
  2773. %A Hiltunen, Matti A.
  2774. %T Configurable Fault-Tolerant Distributed Services
  2775. %D Date issued
  2776. %Z Wed, 23 Oct 96 00:00:00 GMT
  2777. %R TR96-12
  2778. %I The Department of Computer Science, University of Arizona
  2779. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-12.ps.Z
  2780. %X Fault tolerance---that is, the ability of a system to continue providing its
  2781. specified service despite failures---is becoming more important as computers
  2782. are increasingly used in application areas such as process control, air-traffic
  2783. control, and banking. Distributed systems, consisting of computers connected
  2784. by a network, are an important platform for many fault-tolerant systems.
  2785. Unfortunately, it is difficult to construct fault-tolerant distributed
  2786. software, so communication services such as multicast, RPC, membership, and
  2787. transactions have been proposed as simplifying abstractions. However, although
  2788. numerous versions of these services have been defined, no single implementation
  2789. provides a perfect match for all applications and all execution environments.
  2790.     This dissertation presents an approach to constructing highly
  2791. configurable fault-tolerant services. A new model is proposed where a service
  2792. is composed out of micro-protocol objects, each of which implements an
  2793. individual semantic property of the overall service. This makes it easy
  2794. to construct different customized versions of a service with properties
  2795. tailored to the specifics of an application. The model allows micro-protocols
  2796. to cooperate using user-definable events and shared variables, making the
  2797. model more flexible than existing approaches. Three prototype implementations
  2798. of the model are also described.
  2799.     In addition, a new approach is introduced for specifying abstract
  2800. properties of services using temporal logic over message ordering graphs,
  2801. which are abstract representations of collections of messages on each site.
  2802. Furthermore, the problem of which combinations of properties or corresponding
  2803. micro-protocols are feasible is addressed by defining relations that identify
  2804. those combinations that result in a functioning service. Dependency and
  2805. configuration graphs are presented as tools for constructing operational
  2806. configurations.
  2807.     This new approach is used to develop configurable membership and
  2808. group RPC services. Furthermore, the system diagnosis problem is contrasted
  2809. with membership, and new membership and system diagnosis algorithms are
  2810. derived based on the observations. Finally, the dissertation presents an
  2811. application of the event-driven model to adaptive systems that dynamically
  2812. change their behavior as a result of changes in the execution environment
  2813. or user requirements.
  2814. %K keywords
  2815. %Y
  2816.  
  2817. %A Hartman, John
  2818. %A Manber, Udi
  2819. %A Peterson, Larry L.
  2820. %A Proebsting, Todd
  2821. %T Liquid Software: A New Paradigm for Networked Systems
  2822. %D Date issued
  2823. %Z Wed, 23 Oct 96 00:00:00 GMT
  2824. %R TR96-11
  2825. %I The Department of Computer Science, University of Arizona
  2826. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-11.ps.Z
  2827. %X This paper introduces the idea of dynamically moving functionality in a
  2828. network-between clients and servers, and between hosts at the edge of the
  2829. network and nodes inside the network. At the heart of moving functionality
  2830. is the ability to support mobile code-code that is not tied to any single
  2831. machine, but instead can easily move from one machine to another. Mobile
  2832. code has been studied mostly for application-level code. This paper explores
  2833. its use for all facets of the network, and in a much more general way.
  2834. Issues of efficiency, interface design, security, and resource allocation,
  2835. among others, are addressed. We use the term liquid software to describe
  2836. the complete picture-liquid software is an entire infrastructure for
  2837. dynamically moving functionality throughout a network. We expect liquid
  2838. software to enble new paradigms, such as active networks that allow users
  2839. and applications to customize the network by interjecting code into it.
  2840. %K keywords
  2841. %Y
  2842.  
  2843. %A Freeh, Vincent W.
  2844. %A Andrews, Gregory R.
  2845. %T Dynamically Controlling False Sharing in a Distributed Shared Memory
  2846. %D Date issued
  2847. %Z Wed, 23 Oct 96 00:00:00 GMT
  2848. %R TR96-10
  2849. %I The Department of Computer Science, University of Arizona
  2850. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-10.ps.Z
  2851. %X Distributed shared memory (DSM) alleviates the need to program message
  2852. passing explicitly on a distributed-memory machine. In order to reduce memory 
  2853. latency, a DSM replicates copies of data. This paper examines several current
  2854. approaches to controlling thrashing caused by false sharing in a DSM. Then it
  2855. introduces a novel memory consistency protocol, writer-owns, which detects
  2856. and eliminates false sharing at run time. In iterative computations, where
  2857. the data is accessed similarly every iteration, the writer-owns protocol can
  2858. have tremendous benefits because the overhead of eliminating false sharing
  2859. is only incurred once. Performance results show that the writer-owns protocol
  2860. is competitive with and often better than existing approaches.
  2861. %K keywords
  2862. %Y
  2863.  
  2864. %A Downey, Peter J.
  2865. %T The Price of Synchrony
  2866. %D Date issued
  2867. %Z Wed, 23 Oct 96 00:00:00 GMT
  2868. %R TR96-09
  2869. %I The Department of Computer Science, University of Arizona
  2870. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-09.ps.Z
  2871. %X abstract
  2872. %K keywords
  2873. %Y
  2874.  
  2875. %A Bigot, Peter A.
  2876. %T pC*: Efficient and Portable Runtime Support for Data-Parallel Languages
  2877. %D Date issued
  2878. %Z Wed, 23 Oct 96 00:00:00 GMT
  2879. %R TR96-08
  2880. %I The Department of Computer Science, University of Arizona
  2881. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-08.ps.Z
  2882. %X A variety of historically-proven computer languages have recently been
  2883. extended to support parallel computation in a \emph{data-parallel}
  2884. framework.  The performance capabilities of modern microprocessors have made
  2885. the ``cluster-of-workstations'' model of parallel computing more attractive,
  2886. by permitting organizations to network together workstations to solve
  2887. problems in concert, without the need to buy specialized and expensive
  2888. supercomputers or mainframes.
  2889.      For the most part, research on these extended languages has focused on
  2890. compile-time analyses which detect data dependencies and use user-provided
  2891. hints to distribute data and encode the necessary communication operations
  2892. between nodes in a multiprocessor system.  These analyses have shown their
  2893. value when the necessary hints are provided, but require more information at
  2894. compile-time than may be available in large-scale real-world programs.
  2895.      This dissertation focuses on elements important to an efficient and
  2896. portable implementation of runtime support for data-parallel languages, to
  2897. the near absence of any reliance on compile-time information.  We consider
  2898. issues ranging from data distribution and global/local address conversion,
  2899. through a communication framework intended to support modern networked
  2900. computers, and optimizations for a variety of communications patterns common
  2901. to data-parallel programs.  The discussion is grounded in a complete
  2902. implementation of a data-parallel language, C*, on stock workstations
  2903. connected with standard network hardware.  The performance of the resulting
  2904. system is evaluated on a set of eight benchmark programs by comparing it to
  2905. optimized sequential solutions to the same problems, and to the reference
  2906. implementation of C* on the Connection Machine CM5 supercomputer.  Our
  2907. implementation, denoted pC* for ``portable C*'', generally performs within
  2908. a factor of four of the optimized sequential algorithms.  In addition, the
  2909. optimizations developed in this dissertation permit a cluster of twelve
  2910. workstations connected with Ethernet to outperform a sixty-four node CM5
  2911. in absolute performance on three of the eight benchmarks.
  2912.      Though we specifically address the issues of runtime support for C*,
  2913. the material in this dissertation applies equally well to a variety of other
  2914. parallel systems, especially the data-parallel features of Fortran 90 and
  2915. High Performance Fortran.
  2916. %K keywords
  2917. %Y
  2918.  
  2919. %A Myers, Eugene
  2920. %T Title
  2921. %D Date issued
  2922. %Z Wed, 23 Oct 96 00:00:00 GMT
  2923. %R TR96-07
  2924. %I The Department of Computer Science, University of Arizona
  2925. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-07.ps.Z
  2926. %X abstract
  2927. %K keywords
  2928. %Y
  2929.  
  2930. %A Suzuki, Masato
  2931. %A Katayama, Takuya
  2932. %A Schlichting, Richard
  2933. %T FTAG: A Functional and Attribute Based Model for Writing Fault-Tolerant
  2934. Software
  2935. %D Date issued
  2936. %Z Wed, 23 Oct 96 00:00:00 GMT
  2937. %R TR96-06
  2938. %I The Department of Computer Science, University of Arizona
  2939. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-06.ps.Z
  2940. %X Programs constructed using techniques that allow software or operational
  2941. faults to be tolerated are typically written using an imperative
  2942. computational model.  Here, an alternative is described in which such
  2943. programs are written using a functional and attribute based model called
  2944. FTAG (Fault-Tolerant Attribute Grammars).  The basic model is introduced
  2945. first, followed by a description of mechanisms that allow a variety of
  2946. standard fault-tolerance techniques to be realized in a straightforward
  2947. way.  Techniques that can be accommodated include replication and checkpointing
  2948. to tolerate operational faults, and recovery blocks and N-version programming
  2949. to tolerate software faults.  Several examples are given to illustrate these
  2950. techniques, including a replicated name server and a fault-tolerant sort that
  2951. uses recovery blocks.  A formal description of FTAG that precisely specifies
  2952. the semantics of the model is also presented.  Finally, a software
  2953. architecture describing how FTAG can be implemented in a computer system
  2954. containing multiple processors is given.
  2955. %K keywords
  2956. %Y
  2957.  
  2958. %A Mosberger, David
  2959. %A Peterson, Larry L.
  2960. %T Making Paths Explicit in the Scout Operating System
  2961. %D Date issued
  2962. %Z Wed, 23 Oct 96 00:00:00 GMT
  2963. %R TR96-05
  2964. %I The Department of Computer Science, University of Arizona
  2965. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-05.ps.Z
  2966. %X This paper makes a case for paths as an explicit abstraction
  2967. in operating system design. Paths provide a unifying infrastructure
  2968. for several OS mechanisms that have been introduced in the last several
  2969. years, including fbufs, integrated layer processing, packet classifiers,
  2970. code specialization, and migrating threads. This paper articulates
  2971. the potential advantages of a path-based OS structure, describes the
  2972. specific path architecture implemented in the Scout OS, and demonstrates
  2973. the advantages in a particular application domain---receiving, decoding,
  2974. and displaying MPEG-compressed video.
  2975. %K keywords
  2976. %Y
  2977.  
  2978. %A Larson, Susan
  2979. %A Jain, Mudita
  2980. %A Anson, Eric
  2981. %A Myers, Eugene
  2982. %T An Interface for a Fragment Assembly Kernel
  2983. %D Date issued
  2984. %Z Wed, 23 Oct 96 00:00:00 GMT
  2985. %R TR96-04a
  2986. %I The Department of Computer Science, University of Arizona
  2987. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-04a.ps.Z
  2988. %X This document describes the C programming language interface to our
  2989. Fragment Assembly Kernel library.  Inputs to the Fragment Assembly Kernel
  2990. are (1) DNA fragment sequences from potentially inaccurate sequencing
  2991. experiments, and (2) optional constraints on fragment assembly such as
  2992. known fragment overlaps or relative fragment orientation.  Fragment
  2993. sequence version control is supported.  The Fragment Assembly Kernel
  2994. produces the most probable reconstructions of the original DNA sequence
  2995. from the fragments, subject to any specified constraints.  Each fragment
  2996. assembly includes multiple sequence alignment and consensus sequences.
  2997. Multiple sequence alignment editing capabilities are provided to allow
  2998. manual correction of sequence errors.
  2999. %K keywords
  3000. %Y
  3001.  
  3002. %A Mosberger, David
  3003. %A Peterson, Larry L.
  3004. %A Bridges, Patrick G.
  3005. %A O'Malley, Sean
  3006. %T Analysis of Techniques to Improve Protocol Processing Latency
  3007. %D Date issued
  3008. %Z Wed, 23 Oct 96 00:00:00 GMT
  3009. %R TR96-03
  3010. %I The Department of Computer Science, University of Arizona
  3011. %U ftp://ftp.cs.arizona.edu/reports/1996/TR96-03.ps.Z
  3012. %X This paper describes several techniques designed to improve protocol
  3013. latency, and reports on their effectiveness when measured on a modern
  3014. RISC machine employing the DEC Alpha processor. We found that the memory
  3015. system---which has long been known to dominate network throughput---is
  3016. also a key factor in protocol latency.  In particular, improving instruction
  3017. cache effectiveness can greatly reduce protocol processing overheads. 
  3018. An important metric in this context is the memory cycles per instructions
  3019. (mCPI), which is the average number of cycles that an instruction stalls
  3020. waiting for a memory access to complete.  The techniques presented in this
  3021. paper reduce the mCPI by up to a factor of 5.8.  In analyzing the
  3022. effectiveness of the techniques, we also present a detailed study of the
  3023. protocol processing behavior of two protocol stacks---TCP/IP and RPC---on
  3024. a modern RISC processor.
  3025. %K keywords
  3026. %Y
  3027.  
  3028. %A Author
  3029. %T Title
  3030. %D Date issued
  3031. %Z Wed, 23 Oct 96 00:00:00 GMT
  3032. %R TR96-02
  3033. %I The Department of Computer Science, University of Arizona
  3034. %U ftp://ftp.cs.arizona.edu/reports
  3035. %X abstract
  3036. %K keywords
  3037. %Y
  3038.  
  3039. %A Author
  3040. %T Title
  3041. %D Date issued
  3042. %Z Wed, 23 Oct 96 00:00:00 GMT
  3043. %R TR96-01
  3044. %I The Department of Computer Science, University of Arizona
  3045. %U ftp://ftp.cs.arizona.edu/reports/1996
  3046. %X abstract
  3047. %K keywords
  3048. %Y
  3049.