Scalable and dynamic quorum systems

We investigate issues related to the probe complexity of quorum systems and their implementation in a dynamic environment. Our contribution is twofold. The first regards the algorithmic complexity of finding a quorum in case of random failures. We show a tradeoff between the load of a quorum system and its probe complexity for non adaptive algorithms. We analyze the algorithmic probe complexity of the Paths quorum system suggested by Naor and Wool in [29], and present two optimal algorithms. The first is a non adaptive algorithm that matches our lower bound. The second is an adaptive algorithm with a probe complexity that is linear in the cardinality of the smallest quorum set. We supply a constant degree network in which these algorithms could be executed efficiently. Thus the Paths quorum system is shown to have good balance between many measures of quality. Our second contribution is presenting Dynamic Paths - a suggestion for a dynamic and scalable quorum system, which can operate in an environment where elements join and leave the system. The quorum system could be viewed as a dynamic adaptation of the Paths system, and therefore has low load high availability and good probe complexity. We show that it scales gracefully as the number of elements grows.Published online: 10 December 2004Moni Naor: Incumbent of the Judith Kleeman ProfessorialChair.Research supported in part by the RAND/APX grant from the EU Program IST     

光学检测系统的优化和评估的新方法

PCB厂商使用自动光学检测仪的目的是为了检测到重要的缺陷,而对于一些特殊设计和装饰性设计则不需要检测。如果要达到这一效果,就必须适当调整系统的检测参数。提供一种衡量AOI侦测性能的新颖方法。此种方法可以尽可能的减少漏测或误报产生的几率,通过考量漏测与误报的各自的成本,客户可据此结果来决定特定的机器的配备。关于自动检测设备选型机制示意图和方法,相关的实用工具及生产领域的简易实施方法也作了说明。     

NSOM the fourth dimension: Integrating nanometric spatial and femtosecond time resolution

Photonic devices are becoming the cornerstone of next generation systems for computing and information processing. This paper reports on the first steps in the development of methods to understand these devices with nanometric (10^?7 cm) spatial and femtosecond (10^?15 s) time resolution. The basis of this achievement is the dramatic developments that have occurred in the past few years in a new area of optics called near-field optics. Near-field optics is a form of lensless optics with a resolution that is subwavelength and which is independent of the wavelength of the light being employed. We report in this paper the transmission of pulses with tens of femtosecond duration through subwavelength, near-field optical elements. We also report on a femtosecond near-field optical light source with cross-correlating capabilities and on the growth of GaAs in the tip of micropipettes for use as an ultra-fast electro-optical switch which can cross-correlate optical, electrical, and electro-optical effects. These developments are especially relevant in the investigation of photonic devices since such devices can alter their characteristics as a function of size in the mesoscopic regime from just below lens-based optical resolutions to dimensions that approach atomic scales of ～1 nm (10^?7 cm). In view of the fact that these devices and the processes that govern them also exhibit ultrafast speeds, the combination of state of the art femtosecond laser spectroscopy with the unique features of near-field optics is a critical step in advancing our next generation understandings of such materials and structures so that their full potential in information processing can be achieved.     

微波辅助polyol法制备纳米金属镍及磁性研究

采用微波辅助polyol法成功地制备了直径范围在5～10nm、100～180nm的单分散Ni球,对其磁性进行了测量分析.用XRD和EDAX,接着用TEM和MFM分别对制备的样品进行测试,并用VSM和SQUID进一步讨论了铁磁/反铁磁的界面耦合效应.XRD显示该样品是面心立方结构,EDAX数据表明制备过程中镍球被轻微氧化,MFM和TEM观察结果显示样品金属镍是比较理想的球型,VSM测试结果表明Ni纳米球具有典型的铁磁性.     

Two algorithms for barrier synchronization

We describe two new algorithms for implementing barrier synchronization on a shared-memory multicomputer. Both algorithms are based on a method due to Brooks. We first improve Brooks' algorithm by introducing double buffering. Our dissemination algorithm replaces Brook's communication pattern with an information dissemination algorithm described by Han and Finkel. Our tournament algorithm uses a different communication pattern and generally requires fewer total instructions. The resulting algorithms improve Brook's original barrier by a factor of two when the number of processes is a power of two. When the number of processes is not a power of two, these algorithms improve even more upon Brooks' algorithm because absent processes need not be simulated. These algorithms share with Brooks' barrier the limitation that each of then processes meeting at the barrier must be assigned identifiersi such that 0i<n.     

单分散Ni球制备及Ni／NiO的磁性研究

使用微波辅助Poly方法制备了直径范围在100nm～180nm单分散的Ni球，用磁力显微镜（MFM）测其磁结构。进一步对Ni球表面氧化获得了高度球化的NicoreNiOshell结构，采用XRD，TEM，XPS和EDAX对其进行了测量分析，并用VSM和SQUID进一步讨论了铁磁／反铁磁的界面耦合效应。同时，估算了磁性交换偏置耦合场与颗粒尺寸的关系。     

The expansion and mixing time of skip graphs with applications

We prove that with high probability a skip graph contains a 4-regular expander as a subgraph and estimate the quality of the expansion via simulations. As a consequence, skip graphs contain a large connected component even after an adversarial deletion of nodes. We show how the expansion property can be used to sample a node in the skip graph in a highly efficient manner. We also show that the expansion property can be used to load balance the skip graph quickly. Finally, it is shown that the skip graph could serve as an unstructured P2P system, making it a good candidate for a hybrid P2P system. J. Aspnes was supported in part by NSF grants CCR-0098078, CNS-0305258, and CNS-0435201. The research described here was conducted while the second author was at the Weizmann Institute of Science.     

Finding Maximum Induced Matchings in Subclasses of Claw-Free and <Emphasis Type="Italic">P</Emphasis><Subscript>5</Subscript>-Free Graphs,and in Graphs with Matching and Induced Matching of Equal Maximum Size

In a graph G a matching is a set of edges in which no two edges have a common endpoint. An induced matching is a matching in which no two edges are linked by an edge of G. The maximum induced matching (abbreviated MIM) problem is to find the maximum size of an induced matching for a given graph G. This problem is known to be NP-hard even on bipartite graphs or on planar graphs. We present a polynomial time algorithm which given a graph G either finds a maximum induced matching in G, or claims that the size of a maximum induced matching in G is strictly less than the size of a maximum matching in G. We show that the MIM problem is NP-hard on line-graphs, claw-free graphs, chair-free graphs, Hamiltonian graphs and r-regular graphs for r \geq 5. On the other hand, we present polynomial time algorithms for the MIM problem on (P ₅,D _m )-free graphs, on (bull, chair)-free graphs and on line-graphs of Hamiltonian graphs.