Efficient elections in chordal ring networks

We study the message complexity of the problem of distributively electing a leader in chordal rings. Such networks consist of a basic ring with additional links, the extreme cases being the oriented ring and the complete graph with a full sense of direction. We present a general election algorithm for these networks, and prove its optimality. As a corollary, we show thatO(logn) chords at each processor suffice to obtain an algorithm that uses at mostO(n) messages; this improves and extends a previous work, where an algorithm, also usingO(n) messages, was suggested for the case where alln-1 chords exist (the oriented complete network).     

Determination of oxidizing anions in explosive mixtures by phase transfer

Inorganic oxidizing agents are used in various explosive mixtures that are analysed by analytical chemists. Among them are dynamites, ANFO, black powder, match heads, pyrotechnical devices and home-made bombs. The crucial step in post explosion analysis is the extraction and purification of the explosive residues from the debris. A unique, fast and selective extraction technique for inorganic oxidizing agents is described in this paper. The debris are first extracted with water to yield an aqueous solution of the ions. Oxidizing anions such as nitrate and chlorate, are selectively transfered into the organic phase by the use of lipophilic quarternary ammonium cations. Other anions such as carbonate, sulphate and nitrite are not extracted into the organic phase under these conditions. The extracted anions are then identified by infra-red spectrometry and chemical spot tests.     

A parallel implementation of Flat Concurrent Prolog

Flat Concurrent Prolog is a simple, practical, concurrent programming language which has an efficient uniprocessor implementation. This paper describes an initial parallel implementation of the language; it consists of an interpreter implemented on an Intel iPSC Hypercube. The parallel execution of concurrent logic programming languages involves many nontrivial implementation problems. Some of these problems are well known and have been treated extensively in the literature. The most difficult task is to integrate problem solutions in a coherent and efficient manner. The algorithm presented has been useful in providing insights into the major problems and includes a number of novel ideas to simplify implementation. It does not attempt to solve all the problems involved but rather provides a workable basis for current and future research. The algorithm is under ongoing refinement, simplification and improvement.     

Planar CMOS to multi-gate layout conversion for maximal fin utilization

Multi-gate transistors enable the pace of Moore's Law for another decade. In its 22 nm technology node Intel switched to multi-gate transistors called TriGate, whereas IBM, TSMC, Samsung and others will do so in their 20 nm and 14 nm nodes with multi-gate transistors called FinFET. Several recent publications studied the drawing of multi-gate transistors layout. Designing new VLSI cell libraries and blocks requires massive re-drawing of layout. Hard-IP reuse is an alternative method taking advantage of existing source layout by automatically mapping it into new target technology, which was used in Intel's Tick-Tock marketing strategy for several product generations. This paper presents a cell-level hard-IP reuse algorithm, converting planar transistors to multi-gate ones. We show an automatic, robust transformation of bulk diffusion polygons into fins, while addressing the key requirements of cell libraries, as maximizing performance and interface compatibility across a variety of driving strength. We present a layout conversion flow comprising time-efficient geometric manipulations and discrete optimization algorithms, while generating manually drawn layout quality. Those can easily be used in composing larger functional blocks.     

Computing occluding and transparent motions

Computing the motions of several moving objects in image sequences involves simultaneous motion analysis and segmentation. This task can become complicated when image motion changes significantly between frames, as with camera vibrations. Such vibrations make tracking in longer sequences harder, as temporal motion constancy cannot be assumed. The problem becomes even more difficult in the case of transparent motions.A method is presented for detecting and tracking occluding and transparent moving objects, which uses temporal integration without assuming motion constancy. Each new frame in the sequence is compared to a dynamic internal representation image of the tracked object. The internal representation image is constructed by temporally integrating frames after registration based on the motion computation. The temporal integration maintains sharpness of the tracked object, while blurring objects that have other motions. Comparing new frames to the internal representation image causes the motion analysis algorithm to continue tracking the same object in subsequent frames, and to improve the segmentation.     

Two-dimensional elastoplasticity: Approximation by mixed finite elements

Two-dimensional elastoplastic problems are used to assess the performance of a family of mixed finite elements in the non-linear regime. In particular, four-node bilinear quadrilateral elements that exhibit high accuracy in coarse meshes are used to simulate plane stress, plane strain, axisymmetric and (shear-deformable) plate bending problems. The excellent performance of these elements is demonstrated with a number of discriminating examples selected from the literature. In addition, agreement is observed in the limit load predicted by the axisymmetric solid and plate bending elements.     

Mass transfer and reaction kinetics in the ozone/tap water system

The mass transfer and the reaction kinetics of ozone in tap water were examined. The contacting system was a well-mixed reactor with perpendicular jets. The ozone residual range was the lowest detectable range. A simple mathematical model was proposed to describe the mechanism of the ozone in the reactor and was checked over the range of water flow rates from 2.170 to 3.080 l min⁻¹, gas flow rates from 0.667 to 1.333 l min⁻¹ and different temperature conditions. The proposed model describes quite accurately the mass-transfer behavior in the reactor and determines the operational parameters which control the reactor operation. There is a linear relationship between the ozone feed rate and ozone residual. Zero order kinetics best describe the autodecomposition of ozone in plain tap water. The mass transfer coefficient is about 1.14 min⁻¹. Without use of agitation, there is a large decrease in the value of the mass transfer coefficient, to about 0.250 min⁻¹. The magnitude of the reactor rate constant is between 0.05 and 0.13 mg min⁻¹ l.     

Self-stabilizing extensions for meassage-passing systems

Summary A self-stabilizing program eventually resumes normal behavior even if excution begins in, an abnormal initial state. In this paper, we explore the possibility of extending an arbitrary program into a self-stabilizing one. Our contributions are: (1) a formal definition of the concept of one program being aself-stabilizing extension of another; (2) a characterization of what properties may hold in such extensions; (3) a demonstration of the possibility of mechanically creating such extensions. The computtional model used is that of an asynchronous distributed message-passing system whose communication topology is an arbitrary graph. We contrast the difficulties of self-stabilization in thismodel with those of themore common shared-memory models. Shmuel Katz received his B.A. in Mathematics and Englisch Literature from U.C.L.A., and his M.Sc. and Ph.D. in Computer Science (1976) from the Weizmann Institute in Rechovot, Israel. From 1976 to 1981 he was a research at the IBM Israel Scientific Center. Presently, he is an Associate Professor in the Computer Science Department at the Technion in Haifa, Israel. In 1977–78 he visited for a year at the University of California, Berkeley, and in 1984–85 was at the University of Texas at Austin. He has been a consultant and vistor at the MCC Software Technology Program, and in 1988–89 was a visiting scientist at the IBM Watson Research Center. His research interests include the methodology of programming, specification methods, program verification and semantics, distributed programming, data structure, and programming languages. Kenneth J. Pery has performed research in the area of distributed computing since obtaining Masters and Doctorate degrees in Computer Science from Cornell Univesity. His current interest is in studying problems of a partical nature in a formal context. He was graduated from Princeton University in 1979 with a B.S.E. degree in Electrical Engineering and Computer Science.The Research of this author was partially supported by Research Grant 120-749 and the Argentinian Research Fund at the Technion     

FTIR Microscopic Studies on Normal, Polyp, and Malignant Human Colonic Tissues

Fourier-Transform Infrared Spectroscopy (FTIR) employs a unique approach tooptical diagnosis of tissue pathology based on the characteristic molecularvibrational spectra of the tissue. The biomolecular changes in the cellularand sub-cellular levels developing in abnormal tissue, including a majorityof cancer forms, manifest themselves in different optical signatures, whichcan be detected in infrared microspectroscopy. This report has two parts. Inthe first part, we report studies on normal, premalignant (polyp) andmalignant human colonic tissues from three patients with different stages ofmalignancy. Our method is based on microscopic infrared study (FTIR-microscopy)of thin tissue specimens and a direct comparison with traditional histopathologicalanalysis, which serves as a gold reference. The limited dataavailable showed normal colonic tissue has a stronger absorption thanpolypoid tumor and cancerous types over a wide region in a total of 100measurements. Detailed analysis showed that there is a significant decreasein total carbohydrate, phosphate and possibly creatine contents for polyp andcancerous tissue types in comparison to the controls. The same trend is maintainedin seven other patients studied. The second part consists of an analysis showingthe influence of various independent factors such as age, sex and grade of malignancy. Ourpreliminary results suggest that among the above three factors, age and gradeof malignancy have significant effect on the metabolites level, but sex has onlyminor effect on the measured spectra. Initial results on Linear DiscriminantAnalysis (LDA) showed good classification between normal and malignant cellsof human colonic tissues.