Counting networks with arbitrary fan-out

Summary It is shown that an acyclic smoothing network (and hence counting network) with fan-outn cannot be constructed from balancers of fan-outb ₁,...,b _k , if there exists a prime factorp ofn, such thatp does not divideb _i , for alli, 1ik. This holds regardless of the depth, fan-in or size of the network, as long as they are finite. On the positive side, a simple construction ofcyclic counting networks with fan-outn, for arbitraryn, is presented. An acyclic counting network with fan-in and fan-outp2 ^k , for any integerk0, is constructed out of 2-balancers andp-balancers. Eran Aharonson received the B.A. and M.Sc. degrees in Computer Science from the Technion, Israel Institute of Technology (Haifa, Israel) in 1989 and 1992, respectively. He is currently vice president for research and development at ART-Advanced Recognition Technolgies Ltd., a company dedicated to handwriting and voice recognition. His general research interests are distributed computation, theoretical computer science and pattern recognition. Hagit Attiya received the B.Sc. degree in Mathematics and Computer Science from the Hebrew University of Jerusalem, in 1981, the M.Sc. and Ph.D. degrees in Computer Science from the Hebrew University of Jerusalem, in 1983 and 1987, respectively. She is presently a senior lecturer at the department of Computer Science at the Technion, Israel Institute of Technology. Prior to this, she has been a post-doctoral research associate at the Laboratory for Computer Science at M.I.T. Her general research interests are distributed computation and theoretical computer science. More specific interests include fault-tolerance, timing-based and asynchronous algorithms.A preliminary version of this paper appears in proceedings of the3rd Annual ACM-SIAM Symposium on Discrete Algorithms, January 1992, pp. 104–113. This research was supported by Technion V.P.R.-B. and G. Greenberg Research Fund (Ottawa)Supported by Rashi Enterprise graduate fellowship     

Highly concurrent multi-word synchronization

The design of concurrent data structures is greatly facilitated by the availability of synchronization operations that atomically modify $k$ arbitrary items, such as $k$-read–modify–write ($k\text{<mi mathsize="small" is="true">RMW</mi>}$). Aiming to increase concurrency in order to exploit the parallelism offered by today’s multi-core and multi-processing architectures, we propose a highly concurrent software implementation of $k\text{<mi mathsize="small" is="true">RMW</mi>}$, with only constant space overhead. Our algorithm ensures that two operations delay each other only if they are within distance $O\left(k\right)$ in the conflict graph, induced by the operations’ data items.The algorithm uses double compare-and-swap (dcas). When dcas is not supported by the architecture, the algorithm of Attiya and Dagan (2001) [3] can be used to replace dcas with (unary) cas, with only a slight increase in the interference among operations.     

Is PTSD-Phenotype Associated with HPA-Axis Sensitivity?: The Endocannabinoid System in Modulating Stress Response in Rats

Endocannabinoids play a role in adaptation to stress and regulate the release of glucocorticoids in stressed and unstressed conditions. We recently found that basal corticosterone pulsatility may significantly impact the vulnerability for developing post-traumatic-stress-disorder (PTSD), suggesting that the endocannabinoid system may contribute to its development. To examine this, we exposed rats to predator scent stress (PSS). Behavioral reactions were recorded seven days post-PSS. Cerebrospinal fluid (CSF) was collected from anesthetized rats shortly after PSS exposure to determine the levels of 2-arachidonoyl glycerol (2-AG) and anandamide (AEA). To correlate between endocannabinoids and corticosterone levels, rats were placed in metabolic cages for urine collection. To assess the levels of endocannabinoids in specific brain regions, rats’ brains were harvested one day after behavioral analysis for staining and fluorescence quantification. Moreover, 2-AG was elevated in the CSF of PTSD-phenotype rats as compared with other groups and was inversely correlated with corticosterone urinary secretion. Eight days post-PSS exposure, hippocampal and hypothalamic 2-AG levels and hippocampal AEA levels were significantly more reduced in the PTSD-phenotype group compared to other groups. We posit that maladaptation to stress, which is propagated by an abnormal activation of endocannabinoids, mediates the subsequent stress-induced behavioral disruption, which, later, reduces neuronal the expression of endocannabinoids, contributing to PTSD symptomology.     

CORRELATION BETWEEN TRANSIENT ROTATIONAL VISCOMETRY AND A DYNAMIC OSCILLATORY TEST FOR VISCOELASTIC STARCH BASED SYSTEMS

Gelatinized starch formulations including lipids and xanthan gum, typical of viscoelastic foodstuffs, were analyzed using a rotational viscometer (transient conditions) and an oscillatory rheometer. Ultra-rapid and slow freezing processing conditions, which can modify product stability, were also tested. Transient shear stress curves showed a typical overshoot and a structural breakdown; the Bird-Leider model satisfactorily fitted these curves. Model parameters were correlated with characteristic peak stress (α_max), peak time (t_max) and relative overshoot corresponding to the α vs time curve. Relationships between transient shear stress data and dynamic measurements (G', G*, δ) for viscoelastic ranges were found for the starch-based systems and were used to assign a physical meaning to Bird-Leider parameters. Viscoelastic starch systems were grouped in different zones of the correlation diagrams based on structure properties like rigidity, stability to the applied strain and fluid characteristics after breakdown.     

Performance of linear MMSE multiuser detection combined with a standard IS-95 uplink

Current implementation of IS-95 based systems is performance limited due to the use of a “conventional” detection scheme, which is susceptive to inter-user interference. We focus on the uplink, and try to examine the performance enhancement achieved by a suboptimal linear multiuser MMSE pre-filter, applied in front of the “standard” detection mechanism. We demonstrate the limitations of this relatively simple approach, and the constellations in which it may show improved performance. This revised version was published online in July 2006 with corrections to the Cover Date.     

Computing in Totally Anonymous Asynchronous Shared Memory Systems

In the totally anonymous shared memory model of asynchronous distributed computing, processes have no identifiers and run identical programs. Moreover, processes have identical interface to the shared memory, and in particular, there are no single-writer registers. This paper assumes that processes do not fail, and the shared memory consists only of read/write registers, which are initialized to some default value. A complete characterization of the functions and agreement tasks that can be solved in this model is presented. Furthermore, it is shown that if a function is computable, then two registers are sufficient for some algorithm to compute it. Consensus is an important agreement task that can be computed. The paper proves logarithmic lower bounds on the number of registers and rounds needed for solving consensus in this model. A consensus protocol using a linear number of shared registers and rounds is also presented.     

Time and Space Lower Bounds for Implementations Using k-CAS

This paper presents lower bounds on the time and space complexity of implementations that use k-compare&swap (k-CAS) synchronization primitives. We prove that using k-CAS primitives can improve neither the time nor the space complexity of implementations of widely used concurrent objects, such as counter, stack, queue, and collect. Surprisingly, overly restrictive use of k-CAS may even increase the space complexity required by such implementations. We prove a lower bound of Omega (log_2 n) on the round complexity of implementations of a collect object using read, write, and k-CAS, for any k, where n is the number of processes in the system. There is an implementation of collect with O(log_2 n) round complexity that uses only reads and writes. Thus, our lower bound establishes that k-CAS is no stronger than read and write for collect implementation round complexity. For k-CAS operations that return the values of all the objects they access, we prove that the total step complexity of implementing key objects such as counters, stacks, and queues is Omega (n log_k n). We also prove that k-CAS cannot improve the space complexity of implementing many objects (including counter, stack, queue, and single-writer snapshot). An implementation has to use at least n base objects even if k-CAS is allowed, and if all operations (other than read) swap exactly k base objects, then it must use at least k cdot n base objects.     

The gray-code filter kernels

In this paper, we introduce a family of filter kernels, the gray-code kernels (GCK) and demonstrate their use in image analysis. Filtering an image with a sequence of gray-code kernels is highly efficient and requires only two operations per pixel for each filter kernel, independent of the size or dimension of the kernel. We show that the family of kernels is large and includes the Walsh-Hadamard kernels, among others. The GCK can be used to approximate any desired kernel and, as such forms, a complete representation. The efficiency of computation using a sequence of GCK filters can be exploited for various real-time applications, such as, pattern detection, feature extraction, texture analysis, texture synthesis, and more