On the Fractal Nature of WWW and Its Application to Cache Modeling

The World Wide Web (WWW or Web) is growing rapidly on the Internet. Web users want fast response time and easy access to a enormous variety of information across the world. Thus, performance is becoming a main issue in the Web. Fractals have been used to study fluctuating phenomena in many different disciplines, from the distribution of galaxies in astronomy to complex physiological control systems. The Web is also a complex, irregular, and random system. In this paper, we look at the document reference pattern at Internet Web servers and use fractal-based models to understand aspects (e.g. caching schemes) that affect the Web performance.

Distributed Parallel Computing in Mermera: Mixing Noncoherent Shared Memories

Programmers of parallel processes that communicate through shared globally distributed data structures (DDS) face a difficult choice. Either they must explicitly program DDS management, by partitioning or replicating it over multiple distributed memory modules, or be content with a high latency coherent (sequentially consistent) memory abstraction that hides the DDS' distribution. We present Mermera, a new formalism and system that enable a smooth spectrum of noncoherent shared memory behaviors to coexist between the above two extremes. Our approach allows us to define known noncoherent memories in a new simple way, to identify new memory behaviors, and to characterize generic mixed-behavior computations. The latter are useful for programming using multiple behaviors that complement each others' advantages. On the practical side, we show that the large class of programs that use asynchronous iterative methods (AIM) can run correctly on slow memory, one of the weakest, and hence most efficient and fault-tolerant, noncoherence conditions. An example AIM program to solve linear equations, is developed to illustrate: (1) the need for concurrently mixing memory behaviors, and, (2) the performance gains attainable via noncoherence. Other program classes tolerate weak memory consistency by synchronizing in such a way as to yield executions indistinguishable from coherent ones. AIM computations on noncoherent memory yield noncoherent, yet correct, computations. We report performance data that exemplifies the potential benefits of noncoherence, in terms of raw memory performance, as well as application speed.

Basis Token Consistency: A Practical Mechanism for Strong Web Cache Consistency

With web caching and cache-related services like CDNs and edge services playing an increasingly significant role in the modern internet, the problem of the weak consistency and coherence provisions in current web protocols is becoming increasingly significant and drawing the attention of the standards community [LCD01]. Toward this end, we present definitions of consistency and coherence for web-like environments, that is, distributed client-server information systems where the semantics of interactions with resource are more general than the read/write operations found in memory hierarchies and distributed file systems. We then present a brief review of proposed mechanisms which strengthen the consistency of caches in the web, focusing upon their conceptual contributions and their weaknesses in real-world practice. These insights motivate a new mechanism, which we call "Basis Token Consistency" or BTC; when implemented at the server, this mechanism allows any client (independent of the presence and conformity of any intermediaries) to maintain a self-consistent view of the server's state. This is accomplished by annotating responses with additional per-resource application information which allows client caches to recognize the obsolescence of currently cached entities and identify responses from other caches which are already stale in light of what has already been seen. The mechanism requires no deviation from the existing client-server communication model, and does not require servers to maintain any additional per-client state. We discuss how our mechanism could be integrated into a fragment-assembling Content Management System (CMS), and present a simulation-driven performance comparison between the BTC algorithm and the use of the Time-To-Live (TTL) heuristic.

Cache-and-Relay Streaming Media Delivery for Asynchronous Clients

We consider the problem of delivering popular streaming media to a large number of asynchronous clients. We propose and evaluate a cache-and-relay end-system multicast approach, whereby a client joining a multicast session caches the stream, and if needed, relays that stream to neighboring clients which may join the multicast session at some later time. This cache-and-relay approach is fully distributed, scalable, and efficient in terms of network link cost. In this paper we analytically derive bounds on the network link cost of our cache-and-relay approach, and we evaluate its performance under assumptions of limited client bandwidth and limited client cache capacity. When client bandwidth is limited, we show that although finding an optimal solution is NP-hard, a simple greedy algorithm performs surprisingly well in that it incurs network link costs that are very close to a theoretical lower bound. When client cache capacity is limited, we show that our cache-and-relay approach can still significantly reduce network link cost. We have evaluated our cache-and-relay approach using simulations over large, synthetic random networks, power-law degree networks, and small-world networks, as well as over large real router-level Internet maps.

The Cache Inference Problem and its Application to Content and Request Routing

In many networked applications, independent caching agents cooperate by servicing each other's miss streams, without revealing the operational details of the caching mechanisms they employ. Inference of such details could be instrumental for many other processes. For example, it could be used for optimized forwarding (or routing) of one's own miss stream (or content) to available proxy caches, or for making cache-aware resource management decisions. In this paper, we introduce the Cache Inference Problem (CIP) as that of inferring the characteristics of a caching agent, given the miss stream of that agent. While CIP is insolvable in its most general form, there are special cases of practical importance in which it is, including when the request stream follows an Independent Reference Model (IRM) with generalized power-law (GPL) demand distribution. To that end, we design two basic "litmus" tests that are able to detect LFU and LRU replacement policies, the effective size of the cache and of the object universe, and the skewness of the GPL demand for objects. Using extensive experiments under synthetic as well as real traces, we show that our methods infer such characteristics accurately and quite efficiently, and that they remain robust even when the IRM/GPL assumptions do not hold, and even when the underlying replacement policies are not "pure" LFU or LRU. We exemplify the value of our inference framework by considering example applications.

Variable Rate Working Memories for Phonetic Categorization and Invariant Speech Perception

Speech can be understood at widely varying production rates. A working memory is described for short-term storage of temporal lists of input items. The working memory is a cooperative-competitive neural network that automatically adjusts its integration rate, or gain, to generate a short-term memory code for a list that is independent of item presentation rate. Such an invariant working memory model is used to simulate data of Repp (1980) concerning the changes of phonetic category boundaries as a function of their presentation rate. Thus the variability of categorical boundaries can be traced to the temporal in variance of the working memory code.

Working Memories for Storage and Recall of Arbitrary Temporal Sequences

A working memory model is described that is capable of storing and recalling arbitrary temporal sequences of events, including repeated items. These memories encode the invariant temporal order of sequential events that may be presented at widely differing speeds, durations, and interstimulus intervals. This temporal order code is designed to enable all possible groupings of sequential events to be stably learned and remembered in real time, even as new events perturb the system.

Involuntary Memories and Dissociative Amnesia: Assessing Key Assumptions in PTSD Research.

Autobiographical memories of trauma victims are often described as disturbed in two ways. First, the trauma is frequently re-experienced in the form of involuntary, intrusive recollections. Second, the trauma is difficult to recall voluntarily (strategically); important parts may be totally or partially inaccessible-a feature known as dissociative amnesia. These characteristics are often mentioned by PTSD researchers and are included as PTSD symptoms in the DSM-IV-TR (American Psychiatric Association, 2000). In contrast, we show that both involuntary and voluntary recall are enhanced by emotional stress during encoding. We also show that the PTSD symptom in the diagnosis addressing dissociative amnesia, trouble remembering important aspects of the trauma is less well correlated with the remaining PTSD symptoms than the conceptual reversal of having trouble forgetting important aspects of the trauma. Our findings contradict key assumptions that have shaped PTSD research over the last 40 years.

Functional neuroimaging of emotionally intense autobiographical memories in post-traumatic stress disorder.

Post-traumatic stress disorder (PTSD) affects regions that support autobiographical memory (AM) retrieval, such as the hippocampus, amygdala and ventral medial prefrontal cortex (PFC). However, it is not well understood how PTSD may impact the neural mechanisms of memory retrieval for the personal past. We used a generic cue method combined with parametric modulation analysis and functional MRI (fMRI) to investigate the neural mechanisms affected by PTSD symptoms during the retrieval of a large sample of emotionally intense AMs. There were three main results. First, the PTSD group showed greater recruitment of the amygdala/hippocampus during the construction of negative versus positive emotionally intense AMs, when compared to controls. Second, across both the construction and elaboration phases of retrieval the PTSD group showed greater recruitment of the ventral medial PFC for negatively intense memories, but less recruitment for positively intense memories. Third, the PTSD group showed greater functional coupling between the ventral medial PFC and the amygdala for negatively intense memories, but less coupling for positively intense memories. In sum, the fMRI data suggest that there was greater recruitment and coupling of emotional brain regions during the retrieval of negatively intense AMs in the PTSD group when compared to controls.

The coherence of memories for trauma: evidence from posttraumatic stress disorder.

Participants with posttraumatic stress disorder (PTSD) and participants with a trauma but without PTSD wrote narratives of their trauma and, for comparison, of the most-important and the happiest events that occurred within a year of their trauma. They then rated these three events on coherence. Based on participants' self-ratings and on naïve-observer scorings of the participants' narratives, memories of traumas were not more incoherent than the comparison memories in participants in general or in participants with PTSD. This study comprehensively assesses narrative coherence using a full two (PTSD or not) by two (traumatic event or not) design. The results are counter to most prevalent theoretical views of memory for trauma.

Autobiographical Memories for Very Negative Events: The Effects of Thinking about and Rating Memories.

In three related experiments, 250 participants rated properties of their autobiographical memory of a very negative event before and after writing about either their deepest thoughts and emotions of the event or a control topic. Levels of emotional intensity of the event, distress associated with the event, intrusive symptoms, and other phenomenological memory properties decreased over the course of the experiment, but did not differ by writing condition. We argue that the act of answering our extensive questions about a very negative event led to the decrease, thereby masking the effects of expressive writing. To show that the changes could not be explained by the mere passage of time, we replicated our findings in a fourth experiment in which all 208 participants nominated a very negative event, but only half the participants rated properties of their memory in the first session. Implications for reducing the effects of negative autobiographical memories are discussed.

Component Neural Systems for the Creation of Emotional Memories during Free Viewing of a Complex, Real-World Event.

To investigate the neural systems that contribute to the formation of complex, self-relevant emotional memories, dedicated fans of rival college basketball teams watched a competitive game while undergoing functional magnetic resonance imaging (fMRI). During a subsequent recognition memory task, participants were shown video clips depicting plays of the game, stemming either from previously-viewed game segments (targets) or from non-viewed portions of the same game (foils). After an old-new judgment, participants provided emotional valence and intensity ratings of the clips. A data driven approach was first used to decompose the fMRI signal acquired during free viewing of the game into spatially independent components. Correlations were then calculated between the identified components and post-scanning emotion ratings for successfully encoded targets. Two components were correlated with intensity ratings, including temporal lobe regions implicated in memory and emotional functions, such as the hippocampus and amygdala, as well as a midline fronto-cingulo-parietal network implicated in social cognition and self-relevant processing. These data were supported by a general linear model analysis, which revealed additional valence effects in fronto-striatal-insular regions when plays were divided into positive and negative events according to the fan's perspective. Overall, these findings contribute to our understanding of how emotional factors impact distributed neural systems to successfully encode dynamic, personally-relevant event sequences.

Mental hoop diaries: emotional memories of a college basketball game in rival fans.

The rivalry between the men's basketball teams of Duke University and the University of North Carolina-Chapel Hill (UNC) is one of the most storied traditions in college sports. A subculture of students at each university form social bonds with fellow fans, develop expertise in college basketball rules, team statistics, and individual players, and self-identify as a member of a fan group. The present study capitalized on the high personal investment of these fans and the strong affective tenor of a Duke-UNC basketball game to examine the neural correlates of emotional memory retrieval for a complex sporting event. Male fans watched a competitive, archived game in a social setting. During a subsequent functional magnetic resonance imaging session, participants viewed video clips depicting individual plays of the game that ended with the ball being released toward the basket. For each play, participants recalled whether or not the shot went into the basket. Hemodynamic signal changes time locked to correct memory decisions were analyzed as a function of emotional intensity and valence, according to the fan's perspective. Results showed intensity-modulated retrieval activity in midline cortical structures, sensorimotor cortex, the striatum, and the medial temporal lobe, including the amygdala. Positively valent memories specifically recruited processing in dorsal frontoparietal regions, and additional activity in the insula and medial temporal lobe for positively valent shots recalled with high confidence. This novel paradigm reveals how brain regions implicated in emotion, memory retrieval, visuomotor imagery, and social cognition contribute to the recollection of specific plays in the mind of a sports fan.

People who expect to enter psychotherapy are prone to believing that they have forgotten memories of childhood trauma and abuse.

We asked 1004 undergraduates to estimate both the probability that they would enter therapy and the probability that they experienced but could not remember incidents of potentially life-threatening childhood traumas or physical and sexual abuse. We found a linear relation between the expectation of entering therapy and the belief that one had, but cannot now remember, childhood trauma and abuse. Thus individuals who are prone to seek psychotherapy are also prone to accept a suggested memory of childhood trauma or abuse as fitting their expectations. In multiple regressions predicting the probability of forgotten memories of childhood traumas and abuse, the expectation of entering therapy remained as a substantial predictor when self-report measures of mood, anxiety, post-traumatic stress disorder symptom severity, and trauma exposure were included.

A comparison of dimensional models of emotion: evidence from emotions, prototypical events, autobiographical memories, and words.

The intensity and valence of 30 emotion terms, 30 events typical of those emotions, and 30 autobiographical memories cued by those emotions were each rated by different groups of 40 undergraduates. A vector model gave a consistently better account of the data than a circumplex model, both overall and in the absence of high-intensity, neutral valence stimuli. The Positive Activation - Negative Activation (PANA) model could be tested at high levels of activation, where it is identical to the vector model. The results replicated when ratings of arousal were used instead of ratings of intensity for the events and autobiographical memories. A reanalysis of word norms gave further support for the vector and PANA models by demonstrating that neutral valence, high-arousal ratings resulted from the averaging of individual positive and negative valence ratings. Thus, compared to a circumplex model, vector and PANA models provided overall better fits.