On the effect of the deployment setting on broadcasting in Euclidean radio networks

The paper studies broadcasting in radio networks whose stations are represented by points in the Euclidean plane (each station knows its own coordinates). In any given time step, a station can either receive or transmit. A message transmitted from station v is delivered to every station u at distance at most 1 from v, but u successfully hears the message if and only if v is the only station at distance at most 1 from u that transmitted in this time step. A designated source station has a message that should be disseminated throughout the network. All stations other than the source are initially idle and wake up upon the first time they hear the source message. It is shown in [17] that the time complexity of deterministic broadcasting algorithms depends on two parameters of the network, namely, its diameter (in hops) D and a lower bound d on the Euclidean distance between any two stations. The inverse of d is called the granularity of the network, denoted by g. Specifically, the authors of [17] present a deterministic broadcasting algorithm that works in time O (Dg) and prove that every broadcasting algorithm requires \(\varOmega \left( D \sqrt{g} \right) \) time. In this paper, we distinguish between the arbitrary deployment setting, originally studied in [17], in which stations can be placed everywhere in the plane, and the new grid deployment setting, in which stations are only allowed to be placed on a d-spaced grid. Does the latter (more restricted) setting provide any speedup in broadcasting time complexity? Although the O (Dg) broadcasting algorithm of [17] works under the (original) arbitrary deployment setting, it turns out that the \(\varOmega \left( D \sqrt{g} \right) \) lower bound remains valid under the grid deployment setting. Still, the above question is left unanswered. The current paper answers this question affirmatively by presenting a provable separation between the two deployment settings. We establish a tight lower bound on the time complexity of deterministic broadcasting algorithms under the arbitrary deployment setting proving that broadcasting cannot be completed in less than \(\varOmega (D g)\) time. For the grid deployment setting, we develop a deterministic broadcasting algorithm that runs in time \(O \left( D g^{5 / 6} \log g \right) \), thus breaking the linear dependency on g.     

Two hemispheres—two networks: a computational model explaining hemispheric asymmetries while reading ambiguous words

A computational model for reading that takes into account the different processing abilities of the two cerebral hemispheres is presented. This dual hemispheric reading model closely follows the original computational lines due to Kowamoto (J Mem Lang 32:474–516, 1993) but postulates a difference in architecture between the right and left hemispheres. Specifically it is assumed that orthographic, phonological and semantic units are completely connected in the left hemisphere, while there are no direct connections between phonological and orthographic units in the right hemisphere. It is claimed that this architectural difference results in hemisphere asymmetries in resolving lexical ambiguity and more broadly in the processing of written words. Simulation results bear this out. First, we show that the two networks successfully simulate the time course of lexical selection in the two cerebral hemispheres. Further, we were able to see a computational advantage of two separate networks, when information is transferred from the right hemisphere network to the left hemisphere network. Finally, beyond reproducing known empirical data, this dual hemispheric reading model makes novel and surprising predictions that were found to be consistent with new human data.     

Scintillation index for two Gaussian laser beams with different wavelengths in weak atmospheric turbulence

We study the propagation of the two lowest-order Gaussian laser beams with different wavelengths in weak atmospheric turbulence. Using the Rytov approximation and assuming a slow detector, we calculate the longitudinal and radial components of the scintillation index for a typical free-space laser communication setup. We find the optimal configuration of the two laser beams with respect to the longitudinal scintillation index. We show that the value of the longitudinal scintillation for the optimal two-beam configuration is smaller by more than 50% compared with the value for a single lowest-order Gaussian beam with the same total power. Furthermore, the radial scintillation for the optimal two-beam system is smaller by 35%-40% compared with the radial scintillation in the single-beam case. Further insight into the reduction of intensity fluctuations is gained by analyzing the self- and cross-intensity contributions to the scintillation index.     

On modeling the irregular fluctuations in microbial counts

Daily or other periodic microbial counts in many foods, particularly ground meats, poultry, and raw milk, show an irregular fluctuating pattern. The cause of the fluctuations is the interplay of many random factors that tend to promote or inhibit microbial growth. Therefore, the actual size of a microbial population can vary randomly around a typical level or around a trend determined, for example, by seasonal variations or changing sanitary conditions. Fluctuations around a fixed level can often be modeled as a sequence of independent counts having a lognormal or other parametric distribution. The independence of the counts and the type of distribution can be established by standard statistical tests. Once selected, the distribution function can be used to estimate the probability of encountering a population in any given size range. The model can be modified to describe sequences that include zero counts, which are the result of the organisms' absence, or of the failure of the method to detect them. In the case of fluctuations around a trend, a modified version of the model can be used to estimate the probability of deviations from the trend. A more thorough modification is required in order to account for fluctuating patterns that include outbursts of appreciable duration, like those caused by massive contamination of a water reservoir.     

Distributed algorithms for partitioning a swarm of autonomous mobile robots

A number of recent studies address systems of mobile autonomous robots from a distributed computing point of view. Although such systems employ robots that are relatively weak and simple (i.e., dimensionless, oblivious and anonymous), they are nevertheless expected to have strong fault tolerance capabilities as a group. This paper studies the partitioning problem, where n$n$ robots must divide themselves into k$k$ size-balanced groups, and examines the impact of common orientation on the solvability of this problem. First, deterministic crash-fault-tolerant algorithms are given for the problem in the asynchronous full-compass and semi-synchronous half-compass models, and a randomized algorithm is given for the semi-synchronous no-compass model. Next, the role of common orientation shared by the robots is examined. Necessary and sufficient conditions for the partitioning problem to be solvable are given in the different timing models. Finally, the problem is proved to be unsolvable in the no-compass synchronous model.     

The SRV constraint for 0/1 topological design

In density-based topological design, 0/1 solutions are often sought, that is, one expects that the final design includes either elements with full material or no material, excluding grey areas. The accepted technique for achieving binary values for the densities is to use a solid isotropic microstructure with penalization (SIMP) material for which Young’s modulus is a polynomial function of the otherwise continuous relative densities. This approach indeed enhances 0/1 solutions in a significant manner and as such it has achieved prominent status in topological design. Nevertheless, this paper proposes a possible alternative to the SIMP methodology for generating 0/1 structures. The design variables are still the densities of the finite elements but Young’s modulus is a linear function of these densities (in some sense, a SIMP material without penalty). In order to drive the solution to a 0/1 layout a new constraint, labeled the sum of the reciprocal variables (SRV), is introduced. The constraint stipulates that the SRV must be larger or equal to its value at a discrete design for a specified amount of material. It is understood that this implies a minimum gage on the design variables, a provision which is also present in the standard fixed-grid formulation to avoid singular stiffness matrices. The technique turned out to be very effective in conjunction with the method of moving asymptotes (MMA) when using topological design methods for finding optimal layouts of patches of piezo-electric (PZT) material in order to minimize the mechanical noise emanating from vibrating surfaces. It also performed satisfactorily in classical structural topological design instances, as can be seen in the numerical examples that illustrate this work.