Steward: Scaling Byzantine Fault-Tolerant Replication to Wide Area Networks

This paper presents the first hierarchical Byzantine fault-tolerant replication architecture suitable to systems that span multiple wide-area sites. The architecture confines the effects of any malicious replica to its local site, reduces message complexity of wide-area communication, and allows read-only queries to be performed locally within a site for the price of additional standard hardware. We present proofs that our algorithm provides safety and liveness properties. A prototype implementation is evaluated over several network topologies and is compared with a flat Byzantine fault-tolerant approach. The experimental results show considerable improvement over flat Byzantine replication algorithms, bringing the performance of Byzantine replication closer to existing benign fault-tolerant replication techniques over wide area networks.     

Hierarchical edge bundles: visualization of adjacency relations in hierarchical data

A compound graph is a frequently encountered type of data set. Relations are given between items, and a hierarchy is defined on the items as well. We present a new method for visualizing such compound graphs. Our approach is based on visually bundling the adjacency edges, i.e., non-hierarchical edges, together. We realize this as follows. We assume that the hierarchy is shown via a standard tree visualization method. Next, we bend each adjacency edge, modeled as a B-spline curve, toward the polyline defined by the path via the inclusion edges from one node to another. This hierarchical bundling reduces visual clutter and also visualizes implicit adjacency edges between parent nodes that are the result of explicit adjacency edges between their respective child nodes. Furthermore, hierarchical edge bundling is a generic method which can be used in conjunction with existing tree visualization techniques. We illustrate our technique by providing example visualizations and discuss the results based on an informal evaluation provided by potential users of such visualizations     

Grigorii Valentinovich Samsonov

Obituaries

Grigorii Valentinovich Samsonov     

The parallel complexity of scheduling with precedence constraints

We study the problem of parallel computation of a schedule for a system of n unit-length tasks on m identical machines, when the tasks are related by a set of precedence constraints. We present NC algorithms for computing an optimal schedule in the case where m, the number of available machines, does not vary with time and the precedence constraints are represented by a collection of outtrees. The algorithms run on an exclusive read, exclusive write (EREW) PRAM. Their complexities are O(log n) and O((log n)²) parallel time using O(n²) and O(n) processors, respectively. The schedule computed by our algorithms is a height-priority schedule. As a complementary result we show that it is very unlikely that computing such a schedule is in NC when any of the above conditions is significantly relaxed. We prove that the problem is P-complete under logspace reductions when the precedence constraints are a collection of intrees and outtrees, or for a collection of outtrees when the number of available machines is allowed to increase with time. The time span of a height-priority schedule for an arbitrary precedence constraints graph is at most 2 − 1/(m − 1) times longer than the optimal (N. E Chen and C. L. Liu, Proc. 1974 Sagamore Computer Conference on Parallel Processing, T. Fend (Ed.), Springer-Verlag, Berlin, 1975, pp. 1–16). Whereas it is P-complete to produce the classical height-priority schedules even for very restricted precedence constraints graphs, we present a simple NC parallel algorithm which produces a different schedule that is only 2 − 1/m times the optimal.     

The perceived effect of breakdown and repair on the performance of multiprocessor systems

It is argued that classical measures of computer system performance, for example mean response time, are inadequate in the context of fault-tolerant system design. Alternative, perception-based measures are proposed and theorems established describing their properties. Focus is directed upon the homogeneous M/M/m system in which total processor power is constrained by budget and processors are subject to failure and repair. A numerical technique for extracting both classical and perception-based measures from the associated two-dimensional Markov process is offered, along with bounds on time and space required for its execution. It is seen that the perception-based approach to system design can call for twice as many processors as the classical approach.     

Genetic Dissection of Light-Regulated Adventitious Root Induction in Arabidopsis thaliana Hypocotyls

Photomorphogenic responses of etiolated seedlings include the inhibition of hypocotyl elongation and opening of the apical hook. In addition, dark-grown seedlings respond to light by the formation of adventitious roots (AR) on the hypocotyl. How light signaling controls adventitious rooting is less well understood. Hereto, we analyzed adventitious rooting under different light conditions in wild type and photomorphogenesis mutants in Arabidopsis thaliana. Etiolation was not essential for AR formation but raised the competence to form AR under white and blue light. The blue light receptors CRY1 and PHOT1/PHOT2 are key elements contributing to the induction of AR formation in response to light. Furthermore, etiolation-controlled competence for AR formation depended on the COP9 signalosome, E3 ubiquitin ligase CONSTITUTIVELY PHOTOMORPHOGENIC (COP1), the COP1 interacting SUPPRESSOR OF PHYA-105 (SPA) kinase family members (SPA1,2 and 3) and Phytochrome-Interacting Factors (PIF). In contrast, ELONGATED HYPOCOTYL5 (HY5), suppressed AR formation. These findings provide a genetic framework that explains the high and low AR competence of Arabidopsis thaliana hypocotyls that were treated with dark, and light, respectively. We propose that light-induced auxin signal dissipation generates a transient auxin maximum that explains AR induction by a dark to light switch.     

Distributed algorithms for barrier coverage using relocatable sensors

We study the barrier coverage problem using relocatable sensor nodes. We assume each sensor can sense an intruder or event inside its sensing range. Sensors are initially located at arbitrary positions on the barrier and can move along the barrier. The goal is to find final positions for sensors so that the entire barrier is covered. In recent years, the problem has been studied extensively in the centralized setting. In this paper, we study a barrier coverage problem in the distributed and discrete setting. We assume that we have n identical sensors located at grid positions on the barrier, and that each sensor repeatedly executes a Look-Compute-Move cycle: based on what it sees in its vicinity, it makes a decision on where to move, and moves to its next position. We make two strong but realistic restrictions on the capabilities of sensors: they have a constant visibility range and can move only a constant distance in every cycle. In this model, we give the first two distributed algorithms that achieve barrier coverage for a line segment barrier when there are enough nodes in the network to cover the entire barrier. Our algorithms are synchronous, and local in the sense that sensors make their decisions independently based only on what they see within their constant visibility range. One of our algorithms is oblivious whereas the other uses two bits of memory at each sensor to store the type of move made in the previous step. We show that our oblivious algorithm terminates within \(\varTheta (n^2)\) steps with the barrier fully covered, while the constant-memory algorithm is shown to take \(\varTheta (n)\) steps to terminate in the worst case. Since any algorithm in which a sensor can only move a constant distance in one step requires \(\varOmega (n)\) steps on some inputs, our second algorithm is asymptotically optimal.     

330 GHz FMCW Image Sensor for Homeland Security Applications

A single-pixel imaging remote sensor operating at 330 GHz is described. It is based on a frequency modulated continuous wave (FMCW) and aimed at detection of concealed objects for ranges up to 40 m. The system consists of 2 horn-lens antennas integrated with a homodyne transceiver. The synthesized linear FMCW signal at X-band is multiplied by a factor of 32 to generate the transmitted signal. An intermediate frequency (IF) signal obtained in the output port of the 2-nd harmonic mixer is employed for image processing. Distance measurements were made by performing data acquisition unit based on LabView interface and resulting in a range resolution about 1 cm. Examples of 2D and 3D images reconstructed with this sensor are presented.     

Parameterized Two-Player Nash Equilibrium

We study the problem of computing Nash equilibria in a two-player normal form (bimatrix) game from the perspective of parameterized complexity. Recent results proved hardness for a number of variants, when parameterized by the support size. We complement those results, by identifying three cases in which the problem becomes fixed-parameter tractable. Our results are based on a graph-theoretic representation of a bimatrix game, and on applying graph-theoretic tools on this representation.