Distributed envy minimization for resource allocation

Minimizing envy in distributed discrete resource or task allocation, is an unusual distributed optimization challenge, since the quality of the allocation for each of the agents is dependent, not only on its own allocation, but on the allocation of others as well. Thus, in order to perform distributed search for allocations with minimal envy there is a need to design innovative algorithms that can cope with the challenging constraint structure of an envy minimization problem. Distributed methods for minimizing envy among agents in indivisible resource allocation problems are presented. First, Distributed Envy Minimization Problems (DEMP) are formulated as Distributed Constraint Reasoning problems. When the DEMPs are large, and cannot be solved by a complete search an incomplete local search algorithm is presented. Each transfer of a good from one agent to another involves the change of state of more than one agent. Thus, a minimizing envy local search algorithm must build upon actions (transfers) that include multiple agents. Since DEMPs are particularly susceptible to local minima during local search, the paper proposes an algorithm that alternates between two different hill climbing search phases. The first phase uses one-transfer steps while the other exploits envy cycle elimination steps. An algorithm that minimizes envy while preserving efficiency, is proposed. The proposed algorithm finds a Pareto optimal allocation with low envy. In the context of resource allocation problems, a Pareto optimal solution is particularly desirable since it presents a stable solution. The proposed algorithm first finds a divisible Pareto optimal envy-free allocation using a Fisher market equilibrium. This allocation is transferred into an indivisible allocation of goods while maintaining the Pareto optimal characteristic of the allocation and a low envy level among agents.     

Octopus: A fault-tolerant and efficient ad-hoc routing protocol

Mobile ad-hoc networks (MANETs) are failure-prone environments; it is common for mobile wireless nodes to intermittently disconnect from the network, e.g., due to signal blockage. This paper focuses on withstanding such failures in large MANETs: we present Octopus, a fault-tolerant and efficient position-based routing protocol. Fault-tolerance is achieved by employing redundancy, i.e., storing the location of each node at many other nodes, and by keeping frequently refreshed soft state. At the same time, Octopus achieves a low location update overhead by employing a novel aggregation technique, whereby a single packet updates the location of many nodes at many other nodes. Octopus is highly scalable: for a fixed node density, the number of location update packets sent does not grow with the network size. And when the density increases, the overhead drops. Thorough empirical evaluation using the ns2 simulator with up to 675 mobile nodes shows that Octopus achieves excellent fault-tolerance at a modest overhead: when all nodes intermittently disconnect and reconnect, Octopus achieves the same high reliability as when all nodes are constantly up. A preliminary version of this paper appears in Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems (SRDS 2005) October 26–28, 2005, Orlando, Florida. Idit Keidar is a faculty member at the department of Electrical Engineering at the Technion Israel Institute of Technology, and a recipient of the national Alon Fellowship for new faculty members. She holds Ph.D., M.Sc. (summa cum laude), and B.Sc (summa cum laude) degrees from the Hebrew University of Jerusalem. She was a postdoctoral research associate at MIT’s laboratory for Computer Science, where she held post-doctoral fellowships from Rothschild Yad-Hanadiv and NSF CISE. Dr. Keidar has consulted for BBN Technologies (a Verizon Company) in the area of fault-tolerance and intrusion tolerance, and for Microsoft Research in the area of fault-tolerant storage systems. Dr. Keidar’s research focuses on reliability in distributed algorithms and system. She is the academic head of Software Systems Laboratory at the Technion. Dr. Keidar served as a member of the Steering Committee of the ACM Symposium on Principles of Distributed Computing (PODC), has served on numerous program committees of leading conferences in the area of distributed and parallel computing, has twice served as a vice-chair for the IEEE International Conference on Distributed Computing Systems (ICDCS), and once served as a vice-chair for Euro-Par. Yoav Barel is a Senior Business Line Manager at Sun Microsystems. He holds a B.Sc from the Technion—Israel Institute of Technology. Mr. Barel works with wireless carriers world wide and assists them in deploying innovative services based on cutting edge Java technologies. Roie Melamed is a research staff member at IBM Haifa Research Laboratory. He holds Ph.D. and B.A. (cum laude) degrees from the Technion—Israel Institute of Technology. Dr. Melamed’s research focuses on reliability in distributed systems.     

Submolecular potential profiling across organic monolayers

Potential profiles across molecular layers are constructed by means of noncontact electrically stimulated photoelectron spectroscopy, probing for the first time the molecule-substrate interface potential and resolving local screening effects across inner phenyl groups.     

EquiCast: Scalable multicast with selfish users

Peer-to-peer (P2P) networks suffer from the problem of “freeloaders”, i.e., users who consume resources without contributing anything in return. In this paper, we tackle this problem taking a game theoretic perspective by modeling the system as a non-cooperative game. We introduce EquiCast, a wide-area P2P multicast protocol for large groups of selfish nodes. EquiCast is the first P2P multicast protocol that is formally proven to enforce cooperation in selfish environments. Additionally, we prove that EquiCast incurs a low constant load on each user.     

Message delay and DisCSP search algorithms

Distributed constraint satisfaction problems (DisCSPs) are composed of agents, each holding its own variables, that are connected by constraints to variables of other agents. Due to the distributed nature of the problem, message delay can have unexpected effects on the behavior of distributed search algorithms on DisCSPs. This has been recently shown in experimental studies of asynchronous backtracking algorithms (Bejar et al., Artif. Intell., 161:117–148, 2005; Silaghi and Faltings, Artif. Intell., 161:25–54, 2005). To evaluate the impact of message delay on the run of DisCSP search algorithms, a model for distributed performance measures is presented. The model counts the number of non concurrent constraints checks, to arrive at a solution, as a non concurrent measure of distributed computation. A simpler version measures distributed computation cost by the non-concurrent number of steps of computation. An algorithm for computing these distributed measures of computational effort is described. The realization of the model for measuring performance of distributed search algorithms is a simulator which includes the cost of message delays. Two families of distributed search algorithms on DisCSPs are investigated. Algorithms that run a single search process, and multiple search processes algorithms. The two families of algorithms are described and associated with existing algorithms. The performance of three representative algorithms of these two families is measured on randomly generated instances of DisCSPs with delayed messages. The delay of messages is found to have a strong negative effect on single search process algorithms, whether synchronous or asynchronous. Multi search process algorithms, on the other hand, are affected very lightly by message delay.     

Wafer-scale assembly of highly ordered semiconductor nanowire arrays by contact printing

Controlled and uniform assembly of "bottom-up" nanowire (NW) materials with high scalability presents one of the significant bottleneck challenges facing the integration of nanowires for electronic applications. Here, we demonstrate wafer-scale assembly of highly ordered, dense, and regular arrays of NWs with high uniformity and reproducibility through a simple contact printing process. The assembled NW pitch is shown to be readily modulated through the surface chemical treatment of the receiver substrate, with the highest density approaching approximately 8 NW/mum, approximately 95% directional alignment, and wafer-scale uniformity. Such fine control in the assembly is attained by applying a lubricant during the contact printing process which significantly minimizes the NW-NW mechanical interactions, therefore enabling well-controlled transfer of nanowires through surface chemical binding interactions. Furthermore, we demonstrate that our printing approach enables large-scale integration of NW arrays for various device structures on both rigid silicon and flexible plastic substrates, with a controlled semiconductor channel width ranging from a single NW ( approximately 10 nm) up to approximately 250 microm, consisting of a parallel array of over 1250 NWs and delivering over 1 mA of ON current.     

Min-domain retroactive ordering for Asynchronous Backtracking

Ordering heuristics are a powerful tool in CSP search algorithms. Among the most successful ordering heuristics are heuristics which enforce a fail first strategy by using the Min-domain property (Haralick and Elliott, Artif Intel 14:263–313, 1980; Bessiere and Regin, Mac and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems. In Proc. CP 96, pp. 61–75, Cambridge, MA, 1996; Smith and Grant, Trying harder to fail first. In European Conference on Artificial Intelligence, pp. 249–253, 1998; Dechter, Constraint Processing. Morgan Kaufman, 2003). Ordering heuristics have been introduced recently to asynchronous backtracking (ABT), for distributed constraints satisfaction (DisCSP) (Zivan and Meisels, Dynamic ordering for asynchronous backtracking on discsps. In CP-2005, pp. 32–46, Sigtes (Barcelona), Spain, 2005). However, the pioneering study of dynamically ordered ABT, ABT_DO, has shown that a straightforward implementation of the Min-domain heuristic does not produce the expected improvement over a static ordering. The present paper proposes an asynchronous dynamic ordering which does not follow the standard restrictions on the position of reordered agents in ABT_DO. Agents can be moved to a position that is higher than that of the target of the backtrack. Combining the Nogood-triggered heuristic and the Min-domain property in this new class of heuristics results in the best performing version of ABT_DO. The new version of retroactively ordered ABT is faster by a large factor than the best form of ABT.     

Araneola: A scalable reliable multicast system for dynamic environments

This paper presents Araneola (Araneola means “little spider” in Latin.), a scalable reliable application-level multicast system for highly dynamic wide-area environments. Araneola supports multi-point to multi-point reliable communication in a fully distributed manner, while incurring constant load (in terms of message and space complexity) on each node. For a tunable parameter k≥3, Araneola constructs and dynamically maintains a basic overlay structure in which each node’s degree is either k or k+1, and roughly 90% of the nodes have degree k. Empirical evaluation shows that Araneola’s basic overlay achieves three important mathematical properties of k-regular random graphs (i.e., random graphs in which each node has exactly k neighbors) with N nodes: (i) its diameter grows logarithmically with N; (ii) it is generally k-connected; and (iii) it remains highly connected following random removal of linear-size subsets of edges or nodes. The overlay is constructed and maintained at a low cost: each join, leave, or failure is handled locally, and entails the sending of only about 3k messages in total, independent of N. Moreover, this cost decreases as the churn rate increases.The low degree of Araneola’s basic overlay structure allows for allocating plenty of additional bandwidth for specific application needs. In this paper, we give an example for such a need — communicating with nearby nodes; we enhance the basic overlay with additional links chosen according to geographic proximity and available bandwidth. We show that this approach, i.e., a combination of random and nearby links, reduces the number of physical hops messages traverse without hurting the overlay’s robustness, as compared with completely random Araneola overlays (in which all the links are random) with the same average node degree.Given Araneola’s overlay, we sketch out several message dissemination techniques that can be implemented on top of this overlay. We present a full implementation and evaluation of a gossip-based multicast scheme, with up to 10,000 nodes. We show that compared with a (non-overlay-based) gossip-based multicast protocol, gossiping over Araneola achieves substantial improvements in load, reliability, and latency.     

Kinetic experiments and modeling of NO oxidation and SCR of NOx with decane over Cu- and Fe-MFI catalysts

The kinetic model of the reduction of NO to N₂ with decane, developed based on the experimental data over Fe-MFI catalyst, has been applied for the oxidation of NO to NO₂ and reduction of NO₂ to N₂ with decane over Cu-MFI catalyst. The model fits well the experimental data of oxidation of NO as well as reduction of NO to N₂. Remarkable differences have been found in performance of Cu-MFI and Fe-MFI catalysts. While Fe-MFI is more active in oxidation of NO to NO₂, Cu-MFI exhibits much higher activity in the reduction of NO with decane. The kinetic model indicates that the significantly lower activity of Fe-MFI in comparison with Cu-MFI in transformation of NO_x to nitrogen is due to higher rate of transformation of NO₂, formed in the first step by the oxidation of NO, back to NO instead to molecular nitrogen.