Efficient multicast search under delay and bandwidth constraints

The issue of a multicast search for a group of users is discussed in this study. Given the condition that the search is over only after all the users in the group are found, this problem is called the Conference Call Search (CCS) problem. The goal is to design efficient CCS strategies under delay and bandwidth constraints. While the problem of tracking a single user has been addressed by many studies, to the best of our knowledge, this study is one of the first attempts to reduce the search cost for multiple users. Moreover, as oppose to the single user tracking, for which one can always reduce the expected search delay by increasing the expected search cost, for a multicast search the dependency between the delay and the search cost is more complicated, as demonstrated in this study. We identify the key factors affecting the search efficiency, and the dependency between them and the search delay. Our analysis shows that under tight bandwidth constraints, the CCS problem is NP-hard. We therefore propose a search method that is not optimal, but has a low computational complexity. In addition, the proposed strategy yields a low search delay as well as a low search cost. The performance of the proposed search strategy is superior to the implementation of an optimal single user search on a group of users. Amotz Bar-Noy received the B.Sc. degree in 1981 in Mathematics and Computer Science and the Ph.D. degree in 1987 in Computer Science, both from the Hebrew University, Israel. From October 1987 to September 1989 he was a post-doc fellow in Stanford University, California. From October 1989 to August 1996 he was a Research Staff Member with IBM T. J. Watson Research Center, New York. From February 1995 to September 2001 he was an associate Professor with the Electrical Engineering-Systems department of Tel Aviv University, Israel. From September 1999 to December 2001 he was with AT research labs in New Jersey. Since February 2002 he is a Professor with the Computer and Information Science Department of Brooklyn College - CUNY, Brooklyn New York. Zohar Naor received the Ph.D. degree in Computer Science from Tel Aviv University, Tel Aviv, Israel, in 2000. Since 2003 he is with the University of Haifa, Israel. His areas of interests include wireless networks, resource management of computer networks, mobility, search strategies, and multiple access protocols.     

Constructing Pseudo-Random Permutations with a Prescribed Structure

We show how to construct pseudo-random permutations that satisfy a certain cycle restriction, for example that the permutation be cyclic (consisting of one cycle containing all the elements) or an involution (a self-inverse permutation) with no fixed points. The construction can be based on any (unrestricted) pseudo-random permutation. The resulting permutations are defined succinctly and their evaluation at a given point is efficient. Furthermore, they enjoy a fast forward property, i.e. it is possible to iterate them at a very small cost. Received 10 August 2000 and revised 30 September 2000 Online publication 9 April 2001     

Fair online load balancing

We revisit from a fairness point of view the problem of online load balancing in the restricted assignment model and the 1-∞ model. We consider both a job-centric and a machine-centric view of fairness, as proposed by Goel et al. (In: Symposium on discrete algorithms, pp. 384–390, 2005). These notions are equivalent to the approximate notion of prefix competitiveness proposed by Kleinberg et al. (In: Proceedings of the 40th annual symposium on foundations of computer science, p. 568, 2001), as well as to the notion of approximate majorization, and they generalize the well studied notion of max-min fairness. We resolve a question posed by Goel et al. (In: Symposium on discrete algorithms, pp. 384–390, 2005) proving that the greedy strategy is globally O(log?m)-fair, where m denotes the number of machines. This result improves upon the analysis of Goel et al. (In: Symposium on discrete algorithms, pp. 384–390, 2005) who showed that the greedy strategy is globally O(log?n)-fair, where n is the number of jobs. Typically, n?m, and therefore our improvement is significant. Our proof matches the known lower bound for the problem with respect to the measure of global fairness. The improved bound is obtained by analyzing, in a more accurate way, the more general restricted assignment model studied previously in Azar et al. (J. Algorithms 18:221–237, 1995). We provide an alternative bound which is not worse than the bounds of Azar et al. (J. Algorithms 18:221–237, 1995), and it is strictly better in many cases. The bound we prove is, in fact, much more general and it bounds the load on any prefix of most loaded machines. As a corollary from this more general bound we find that the greedy algorithm results in an assignment that is globally O(log?m)-balanced. The last result generalizes the previous result of Goel et al. (In: Symposium on discrete algorithms, pp. 384–390, 2005) who proved that the greedy algorithm yields an assignment that is globally O(log?m)-balanced for the 1-∞ model.     

Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles

We consider cryptographic and physical zero-knowledge proof schemes for Sudoku, a popular combinatorial puzzle. We discuss methods that allow one party, the prover, to convince another party, the verifier, that the prover has solved a Sudoku puzzle, without revealing the solution to the verifier. The question of interest is how a prover can show: (i) that there is a solution to the given puzzle, and (ii) that he knows the solution, while not giving away any information about the solution to the verifier. In this paper we consider several protocols that achieve these goals. Broadly speaking, the protocols are either cryptographic or physical. By a cryptographic protocol we mean one in the usual model found in the foundations of cryptography literature. In this model, two machines exchange messages, and the security of the protocol relies on computational hardness. By a physical protocol we mean one that is implementable by humans using common objects, and preferably without the aid of computers. In particular, our physical protocols utilize items such as scratch-off cards, similar to those used in lotteries, or even just simple playing cards. The cryptographic protocols are direct and efficient, and do not involve a reduction to other problems. The physical protocols are meant to be understood by “lay-people” and implementable without the use of computers. Research of R. Gradwohl was supported by US-Israel Binational Science Foundation Grant 2002246. Research of M. Naor was supported in part by a grant from the Israel Science Foundation. Research of B. Pinkas was supported in part by the Israel Science Foundation (grant number 860/06). Research of G.N. Rothblum was supported by NSF grant CNS-0430450 and NSF grant CFF-0635297.     

Molecular recognition in the sphingosine 1-phosphate receptor family

Computational modeling and its application in ligand screening and ligand receptor interaction studies play important roles in structure-based drug design. A series of sphingosine 1-phosphate (S1P) receptor ligands with varying potencies and receptor selectivities were docked into homology models of the S1P(1-5) receptors. These studies provided molecular insights into pharmacological trends both across the receptor family as well as at single receptors. This study identifies ligand recognition features that generalize across the S1P receptor family, features unique to the S1P(4) and S1P(5) receptors, and suggests significant structural differences of the S1P(2) receptor. Docking results reveal a previously unknown sulfur-aromatic interaction between the S1P(4) C5.44 sulfur atom and the phenyl ring of benzimidazole as well as pi-pi interaction between F3.33 of S1P(1,4,5) and aromatic ligands. The findings not only confirm the importance of a cation-pi interaction between W4.64 and the ammonium of S1P at S1P(4) but also predict the same interaction at S1P(5). S1P receptor models are validated for pharmacophore development including database mining and new ligand discovery and serve as tools for ligand optimization to improve potency and selectivity.     

Electrodeposition of rhenium-nickel alloys from aqueous solutions

Rhenium-nickel alloys were deposited on copper substrates in a small three-electrode cell, under galvanostatic conditions. The bath solution consisted of ammonium perrhenate, citric acid and nickel sulfamate. The effects of bath composition and deposition time were studied. The Faradaic efficiency (FE) and partial deposition current densities were calculated based on mass gain and elemental analysis using energy dispersive spectroscopy. The surface morphology was characterized by scanning electron microscopy. The thickness of the coating was measured on metallographic cross-sections. The results are discussed with emphasis on routes to increase the Faradaic efficiency and rhenium content in the coating. A plausible mechanism for the electrodeposition of rhenium-nickel alloys is presented.     

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     

Approximating the Advertisement Placement Problem

The advertisement placement problem deals with space and time sharing by advertisements on the Internet. Consider a Web page containing a rectangular display area (e.g., a banner) in which advertisements may appear. The display area can be utilized efficiently by allowing several small ads to appear simultaneously side by side, as well as by cycling through a schedule of ads, allowing different ads to be displayed at different times. A customer wishing to purchase advertising space specifies an ad size and a display count, which is the number of times their ad should appear during each cycle. The scheduler may accept or reject any given advertisement, but must be able to schedule all accepted ads within the given time and space constraints. Each advertisement has a non-negative profit associated with it, and the objective is to schedule a maximum-profit subset of ads. We present a (3 + )-approximation algorithm for the general problem, as well as (2 + )-approximation algorithms for two special cases.     

Certificate revocation and certificate update

We present a solution for the problem of certificate revocation. This solution represents certificate revocation lists by authenticated dictionaries that support: (1) efficient verification whether a certificate is in the list or not and (2) efficient updates (adding/removing certificates from the list). The suggested solution gains in scalability, communication costs, robustness to parameter changes, and update rate. Comparisons to the following solutions (and variants) are included: “traditional” certificate revocation lists (CRLs), Micali's (see Tech. Memo MIT/LCS/TM-542b, 1996) certificate revocation system (CRS), and Kocher's (see Financial Cryptography-FC'98 Lecture Notes in Computer Science. Berlin: Springer-Verlag, 1998, vol.1465, p.172-7) certificate revocation trees (CRT). We also consider a scenario in which certificates are not revoked, but frequently issued for short-term periods. Based on the authenticated dictionary scheme, a certificate update scheme is presented in which all certificates are updated by a common message. The suggested solutions for certificate revocation and certificate update problems are better than current solutions with respect to communication costs, update rate, and robustness to changes in parameters, and are compatible, e.g., with X.500 certificates     

LATS: a load-adaptive threshold scheme for tracking mobile users

Mobile user tracking is a major issue. We propose a novel approach for user tracking, in which the tracking activity is adapted to both user and system activity. The basic idea is to make the user-location update-rate dependent not only on the user activity (such as the call profile and mobility pattern). Rather, it is also made dependent on the signaling load, which reflects the actual cost of the update operation. Thus, at low-signaling load locations, the users are to transmit location update messages more frequently. To carry out this approach, we propose a load-adaptive threshold scheme (LATS): the network determines for each cell a registration threshold level (which depends on the cell load) and announces it, as a broadcast message, to the users. The user computes its own registration priority and then transmits a registration message only if its priority exceeds the announced threshold level. Thus, whenever the local load on the cell is low, the registration activity increases, while in loaded cells the registration activity decreases. Our analysis shows that the LATS reduces the paging cost, in comparison with other dynamic methods, without increasing the wireless cost of registration. Moreover, if higher user density is coupled with less mobility (e.g., consider vehicles), then the LATS strategy offers further performance improvement. The load-adaptive strategy can be used in addition to any other dynamic tracking strategy. Furthermore, the computational complexity imposed on the user is identical to that required by an equivalent load-insensitive scheme