Greedy hot-potato routing on the two-dimensional mesh

Summary We propose hot-potato (or, deflection) packet routing algorithms on the two-dimensional mesh. The algorithms are strongly greedy in the sense that they attempt to send packets in good directions whenever possible. Furthermore, the routing operations are simple and independent of the time that has elapsed. The first algorithm gives the best evacuation time known for delivering all the packets to their destinations. A batch ofk packets with maximal source-to-destination distanced _max is delivered in 2(k-1)+d _max. The second algorithm improves this bound tok+d _max when all packets are destined to the same node. This also implies a new bound for the multitarget case, which is the first to take into account the number of in-edges of a node. The third algorithm is designed for routing permutations with source-to-destination distance at most three, in which case the algorithm terminates in at most seven steps. We also show a lower bound of five steps for this problem. Ishai Ben-Aroya received the B.A. and M.Sc. in computer science from the Technion (Israel Institute of Technology). He is currently working with Microsoft Israel R&D group. His main interests include Routing Algorithms, Cryptography and Computer Security. Tamar Eilam received the B.A. degree in Computer Science from the Technion IIL in 1995, and is currently studying towards her M.A. degree. Assaf Schuster received his B.A., M.A. and Ph.D. degrees in Computer Science from the Hebrew University of Jerusalem (the last one in 1991). He is currently a lecturer at the Technion IIL. His main interests include Networks and Routing Algorithms, Parallel and Distributed Computation, Optical Computation and Communication, Dynamically Reconfiguring Networks, and Greedy Hot Potato Routing.This work was supported in part by the French-Israeli grant for cooperation in Computer Science, and by a grant from the Israeli Ministry of Science. An extended abstract appeared in proc. 2nd European Symposium on Algorithms, September 1994     

On Locally Decodable Codes, Self-Correctable Codes, and t-Private PIR

A k-query locally decodable code (LDC) allows to probabilistically decode any bit of an encoded message by probing only k bits of its corrupted encoding. A stronger and desirable property is that of self-correction, allowing to efficiently recover not only bits of the message but also arbitrary bits of its encoding. In contrast to the initial constructions of LDCs, the recent and most efficient constructions are not known to be self-correctable. The existence of self-correctable codes of comparable efficiency remains open.     

The effect of time and temperature on the mechanical behavior of epoxy composites

A crosslinked epoxy resin consisting of a 60/40 weight ratio of Epon 815 and Versamid 140 and composites of this material with glass beads, unidirectional glass fibers and air (foams) were tested in tension, compression and flexure to determine the effect of time and temperature on the elastic properties, yield properties and modes of failure. Unidirectional continuous fiber-filled samples were tested at different fiber orientation angles with respect to the stress axis. Strain rates ranged from 10^?4 to 10 in./in.-min and the temperature from ?1 to 107°C. Isotherms of tangent modulus versus strain rate were shifted to form master modulus curves. The moduli of the filled composites and the foams were predictable over the entire strain rate range. It was concluded that the time-temperature shift factors for tangent moduli and the time-temperature shift factors for stress relaxation were identical and were independent of the type and concentration of filler as well as the mode of loading. The material was found to change from a brittle-to-ductile-to-rubbery failure mode with the transition temperatures being a function of strain rate, filler content, filler type and fiber orientation angle, indicating that the transition is perhaps dependent on the state of stress. In the ductile region, an approximately linear relationship between yield stress and log strain is evident in all cases. The isotherms of yield stress versus log strain rate were shifted to form a practically linear master plot that can be used to predict the yield stress of the composites at any temperature and strain rate in the ductile region. The time-temperature shift factors for yielding were found to be independent of the type, concentration and orientation of filler and the mode of loading. Thus, the composite shift factors seem to be a property of the matrix and not dependent on the state of stress. The compressive-to-tensile yield stress ratio was practically invariant with strain rate for the unfilled matrix, while fillers and voids raised this ratio and caused it to increase with a decrease in strain rate. The yield strain of the composites is less than the unfilled matrix and is a function of fiber orientation and strain rate.     

Delayed yielding of epoxy resin under tension,compression, and flexure. I. Behavior under constant strain rate

Series of loading tests were carried out on epoxy resin specimens, at varying constant strain rates, under tension, compression, and flexure. The stress–strain relationship revealed a distinct yielding stage followed shortly by a post-yielding region of decreasing load. In all cases, results indicate linearity between yield stress and log strain rate, in accordance with Eyring's theory of viscous flow. For specimens unloaded close to the yield point, photoelastic observations revealed a residual pattern parallel to the theoretical principal shear stresses. These results, supported by additional data from other works, indicate a viscoplastic deviatoric stress-biased diffusional mechanism as the dominant factor in the yielding of an amorphous crosslinked epoxy system.     

Delayed yielding of epoxy resin. II. Behavior under constant stress

Creep tests were carried out on epoxy resin specimens at room temperature and at different high stress levels under tension, compression, and flexure. Compared with the behavior at constant strain rate (CSR) reported in Part I of this work, creep strain–time curves revealed a distinct delayed yielding region of constant minimum rate (secondary creep) followed by a post-yielding region of increasing slope (tertiary creep). In all cases, results indicate linearity between creep stress and log secondary creep rate, which is almost coincident with the corresponding relationship between yield stress and strain rate obtained in subsequent CSR loading cycles with the same specimens. The similarity in behavior under both the creep and CSR modes conforms to Eyring's theory of non-Newtonian viscous flow at high stress levels and low temperature. Theoretical analysis yields reasonable values of the activation volume, which is unaffected by the loading and test modes or by loading history, and could thus be regarded as an intrinsic parameter of the microstructure, inherently related to the viscoplastic process involved. The above considerations indicate a deviatoric stress-biased diffusional mechanism as the predominant factor in the yielding of an amorphous glassy epoxy system.     

The effect of cyclic loading on residual stresses and strains in a bonded joint

The mechanical performance of a structural bonded joint is mainly dependent on the interlaminar stresses and strains, the high concentration of which is close to the free edges of the adhesive. Under cyclic loading these stresses and strains are expected to be intensified and to accumulate. The present study deals with the distribution of the residual stresses and strains along the interlaminar adhesive layer under cyclic loading and how it is affected by geometrical edge conditions. A numerical non-linear finite element method was applied, the adhesive layer being regarded as an elasto-plastic bi-linear material with kinematic hardening (Bauschinger effect) which accounts for cyclic plasticity. Findings indicate that lateral normal residual strains in the edge of the adhesive layer are the major component which increases significantly with cycling and are probably responsible for failure initiation and propagation. It was also found that a significant reduction of stress concentration at the adhesive edge may be achieved by a modification of the free-edge geometry of both the adhesive and the adherend phases.     

Oriented short glass-fiber composites. IV. Dependence of mechanical properties on the distribution of fiber orientations

Short glass fiber-epoxy laminates of controlled fiber orientation and distribution were loaded to failure under uniaxial tension. The mechanical characteristics of specimens with different orientation patterns, which were determined experimentally, were compared with analytical predictions based on “Laminate Analogy” methods. Results show good agreement between empirical data and prediction in the case of stiffness, stress-strain relationship and strength based on ultimate strain criteria. A methodology is proposed according to which a well-defined, orthotropic, short fiber reinforced plastic system can be prepared, analyzed, and optimized by tailoring it according to the loading pattern in a similar manner to that of the well-established, continuous fiber reinforced laminates.