ceClub

Self-Adjusting Networks and Distributed Data Structures

Dr. Chen Avin

Department of Communication Systems Engineering, Ben Gurion University

We study self-optimizing networks and data structures. The goal of this research line is the design of fully distributed algorithms which flexibly adapt the network to a dynamic environment such as changing demands or traffic patterns. The idea of self-adjusting networks is motivated by trends in today's Internet like large data centers and peer-to-peer networks.

In this talk I will preset the general model of the problem and some initial theoretical results on data centers placement and splay networks and the connection to well known concepts such as minimum linear arrangement, splay trees and Entropy.

Joint work with: Michael Borokhovich (BGU), Bernhard Haeupler (MIT), Zvi Lotker (BGU), Christian Scheideler (U. Paderborn) and Stefan Schmid (T-Labs).

Bio: Dr. Chen Avin received the B.Sc. degree in Communication Systems Engineering from Ben Gurion University, Israel, in 2000. He received the M.S. and Ph.D. degrees in computer science from the University of California, Los Angeles (UCLA) in 2003 and 2006 respectively. He is a senior lecturer in the Department of Communication Systems Engineering at the Ben Gurion University for which he joined on October 2006. His current research interests are: graphs and networks algorithms, modeling and analysis with emphasis on wireless networks, complex systems and randomize algorithms for networking.

Green Cellular Networks: A Survey, Some Research Issues and Challenges

Vijay K. Bhargava

University of British Columbia and President, IEEE Communications Society

In this talk, we present techniques to enable green communications in future generation of wireless systems that will rely on cooperation and cognition to meet increasing demand of high data rate. So far, achieving high data rate has been the primary focus of research in cooperative and CR systems, without much consideration of energy efficiency. However, many of these techniques significantly increase system complexity and energy consumption. Escalating energy costs and environmental concerns have already created an urgent need for more energy-efficient "green" wireless communications. Therefore, we need to design energy-efficient solutions for cooperative and cognitive networks, which will potentially drive the future generation of wireless communication. We focus on several important topics that are crucial towards reducing the energy consumption of the cognitive and cooperative networks. These topics include efficient base station redesign, heterogeneous network deployment, green communications via cognitive radio, cooperative relays to deliver green communications, and energy efficient cognitive cooperative networks.

Bio: Vijay Bhargava, an IEEE Volunteer for three decades, is Professor in the Department of Electrical and Computer Engineering at the University of British Columbia in Vancouver, where he served as Department Head during 2003-2008. Previously he was with the University of Victoria (1984-2003) and Concordia University (1976-84). He received his Ph.D. from Queen's University in 1974. He is a fellow of the IEEE, the Royal Society of Canada, the Canadian Academy of Engineering and the Engineering Institute of Canada

Vijay has served on the Board of Governors of the IEEE Information Theory Society and the IEEE Communications Society. He has held important positions in these societies and has organized conferences such as ISIT'83, ISIT'95, ICC'99 and VTC 2002 Fall. He played a major role in the creation of the IEEE Transactions on Wireless Communications, and served as its editor-in-chief during 2007, 2008 and 2009. He is a past President of the IEEE Information Theory Society and is currently serving as the President of the IEEE Communications Society.

Improving Virtualization Performance Through Physical Transparency

Nadav Amit

Technion CS

Machine virtualization, where many virtual machines run on a single physical machine, has become an increasingly popular area of research and development in the last decade. Despite the introduction of hardware support for machine virtualization in commodity servers, many workloads still suffer from degraded performance when run in virtual machines. This degradation can be particularly acute when an unmodified virtual machine -- a VM that is not aware it is running in a virtual environment -- is used to run the workload. The degradation is is caused primarily by the lack of physical hardware transparency: instead of exposing the underlying physical hardware transparently to virtual machines, the hypervisor -- the software layer that controls the virtual machines -- usually exposes hardware "abstractions" instead. This talk will present results from two recent projects that improved VM performance by increasing physical transparency: the first increased device emulation throughput threefold using sidecore emulation, and the second improved I/O throughput by 30%-60% using direct interrupt delivery to VMs.

Joint work with Muli Ben-Yehuda, Abel Gordon, Nadav Har'El, Alex Landau, Assaf Schuster, and Dan Tsafrir.

Bio: Nadav Amit is currently a PhD student in the Technion's computer science faculty, conducting research in the area of machine virtualization under the supervision of Prof. Assaf Schuster. Before coming to the Technion, he spent five years in industry working in Intel on development of random instruction tests generator for the validation of virtualization and power management features. He is the recipient of the prestigious IBM Fellowship for PhD students.

PCI Express: Technology, Road Map and Design Challenges

Rick Eads

Agilent Technologies; Member of PCI-SIG board of directors

PCI Express is an industry standard, and the most prominent interconnection architecture for I/O devices and other boards inside a computer. It is defined and updated by the PCI-SIG(R) industry standards body, originally formed in 1992 as the Peripheral Component Interconnect (PCI) special interest group (SIG). Agilent Technologies, a prominent developer and provider of test equipment at all levels yet not a competitor in the computer market, has played a key role in the advancement of PCI Express as a high performance yet extremely reliable interconnection scheme with very good interoperability among different-vendor equipment.

This talk will provide the following: an overview of PCI Express; PCI Express design and debugging challenges; Agilent tools for PCI Express development (physical layer, signal integrity and protocol validation); PCI Express electrical and protocol testing; and a live demo of testing solutions.

Bio: Rick Eads, a senior program manager for PCI Express tools at Agilent Technologies, serves as Agilent's PCI Express Technology lead. Since 2007, he has served on the board of directors of PCI-SIG.

Synthesizing Concurrent Relational Data Structures

Dr. Roman Manevich

UT Austin

Efficient concurrent data structures are extremely important for obtaining good performance for most parallel programs. However, ensuring the correctness of concurrent data structure implementations can be very tricky because of concurrency bugs such as race conditions and deadlocks. In systems that use optimistic parallel execution such as boosted transactional memory systems and the Galois system, the implementation of concurrent data structures is even more complex because data structure implementations must also detect conflicts between concurrent activities and support the rollback of conflicting activities.

At present, these types of concurrent data structures are implemented manually by expert programmers who write explicitly parallel code packaged into libraries for use by application programmers. This solution has its limitations; for example, it does not permit the customization or tuning of a data structure implementation for a particular application.

In this talk, we present Autograph, which is the first concurrent data structure compiler that can synthesize concurrent relational data structure implementations for use by application programmers. The input to Autograph is a high-level declarative specification of an abstract data type (ADT); the output is a concurrent implementation of that ADT with conflict detection and rollback baked in. Our synthesizer is parameterized by a set of data structures called "tiles", which are building blocks that the compiler composes to create the overall data structure. Application programmers can use a simple expression language to tune the composition of these tiles, thereby exercising high level, fine-grain control of data structure implementations. We have used Autograph to synthesize concurrent sparse graph data structures for a number of complex parallel graph benchmarks. Our results show that the synthesized concurrent data structures usually perform better than the handwritten ones; for some applications and thread counts, they improve performance by a factor of 2.

bio: Roman Manevich is a postdoctoral fellow at the university of Texas, Austin. Roman's research interests are software verification of sequential and concurrent programs manipulating dynamically allocated (heap) memory by static analysis, and synthesis of sequential and concurrent programs.

Distributed Average Consensus and Coherence in Dynamic Networks

Dr. Stacy Patterson

Technion EE

In the distributed average consensus problem, each node in a network has an initial value, and the objective is for all nodes to reach consensus at the average of these values using only communication with nearby nodes. Distributed average consensus algorithms have a wide variety of applications, including distributed optimization, sensor fusion, load balancing, and autonomous vehicle formation control.

This talk centers on the analysis of distributed averaging algorithms for consensus and vehicle formation control in networks with dynamic characteristics such as stochastic packet loss, node failures, network partitions, and additive disturbances. I will present an overview of distribued averaging algorithms and some recent results on the stability and robustness of these algorithms in dynamic networks. We analyze the relationship between algorithm performance and the size, dimension, and dynamic characteristics of the network, and we show that network dimension imposes fundamental limitations on algorithm performance in large networks.

bio: Dr. Stacy Patterson received her B.A in Mathematics and B.S. in Computer Science from Rutgers University in 1998 and her M.S. and Ph.D. in Computer Science from the University of California, Santa Barbara in 2003 and 2009 respectively. From July 2009 to August 2011, she was a postdoctoral scholar at the Center for Control, Dynamical Systems, and Computation at the University of California, Santa Barbara. She is currently a postdoctoral fellow in the Department of Electrical Engineering at the Technion, working with Professor Idit Keidar. Her research interests include distributed systems, vehicle networks, and cloud computing.

Persistent OSPF attacks

Gabi Nakibly

National EW Research and Simulation Center

Open Shortest Path First (OSPF) is the most popular interior gateway routing protocol on the Internet. Most known OSPF attacks that have been published in the past are based on falsifying the link state advertisement (LSA) of an attacker-controlled router. These attacks can only falsify a small portion of the routing domain's topology, hence their effect is usually limited. More powerful attacks are the ones that affect LSAs of other routers not controlled by the attacker. However, these attacks usually trigger the OSPF "fight-back" mechanism by the victim router which advertises a correcting LSA, making the attacks' effect non-persistent. In this work we present new OSPF attacks that exploit design vulnerabilities in the protocol specification. These new attacks can affect the LSAs of routers not controlled by the attacker while evading "fight-back". As a result, an attacker can persistently falsify large portions of the routing domain's topology viewed by other routers thereby giving the attacker control over their routing tables. We discuss a number of mitigation strategies and propose an update to the OSPF specification that defeats these attacks and improves OSPF security. The talk is based on results presented at Black Hat '11 and NDSS '12. This is a joint work with Alex Kirshon, Dima Gonikman and Dan Boneh.

bio: Gabi Nakibly is a professional fellow in the National EW Research and Simulation Center at Rafael -- Advanced Defense Systems. He also serves as an adjunct researcher and lecturer in the Computer Science department at the Technion. Gabi received his Ph.D. in computer Science in 2008 from the Technion, and he is a recipient of the Katzir Fellowship. His main research interests include network security and traffic engineering.

Graph matching and clustering on the GPU

Rob Bisseling

Utrecht University

Graph matching is the problem of matching nodes of a graph in pairs such that the largest number of pairs is created or the largest sum of edge weights is obtained. Greedy graph matching provides us with a fast way to coarsen a given graph during graph partitioning. Direct algorithms on the CPU which perform such greedy matchings are simple and fast, but offer few handholds for parallelisation. To remedy this, we introduce a fine-grained shared-memory parallel algorithm for greedy matching, together with an implementation on the GPU, which is faster than the CPU algorithms and produces matchings of similar or better quality.

Another graph problem with much practical interest is that of graph clustering, where highly connected clusters with many internal edges and few external edges are determined. Agglomerative clustering is an effective greedy way to quickly generate graph clusterings of high quality. We introduce a fine-grained shared memory algorithm for agglomerative clustering on both the CPU and GPU. This heuristic algorithm is able to generate clusterings in very little time: an optimal clustering is obtained from a street network graph with 14 million vertices and 17 million edges in six seconds on the GPU. The clustering work was done as part of the 10th DIMACS challenge on graph partitioning and clustering.

Joint work with Bas Fagginger Auer.

bio: Rob Bisseling is a professor in scientific computing at the Mathematics Institute of Utrecht University, the Netherlands. He is author of the book, "Parallel Scientific Computation: A Structured Approach using BSP and MPI", Oxford University Press, March 2004. He is co-author of the BSPlib communications library and the Mondriaan sparse matrix partitioning package. His reserach interests are: graph algorithms, sparse matrix computations, parallel computing, polymer simulations.

http://www.staff.science.uu.nl/~bisse101/

Load Balancing for SIP Server Clusters

Erich Nahum

IBM T.J. Watson Research Center

The Session Initiation Protocol (SIP) is widely used for controlling communication sessions such as voice and video calls over IP, video conferencing, streaming multimedia distribution, instant messaging, presence information, file transfer and online games. This work introduces several novel load balancing algorithms for distributing SIP requests to a cluster of SIP servers. Our load balancer improves both throughput and response time versus a single node, while exposing a single interface to external clients. We present the design, implementation and evaluation of our system using a cluster of Intel x86 machines running Linux. We compare our algorithms with several well-known approaches and present scalability results for up to 10 nodes. Our best algorithm, Transaction Least-Work-Left (TLWL), achieves its performance by integrating several features: knowledge of the SIP protocol; dynamic estimates of back-end server load; distinguishing transactions from calls; recognizing variability in call length; and exploiting differences in processing costs for different SIP transactions. By combining these features, our algorithm provides finer-grained load balancing than standard approaches, resulting in throughput improvements of up to 24 percent and response time improvements of up to two orders of magnitude. We present a detailed analysis of occupancy to show how our algorithms significantly reduce response time.

Reference: This work appeared in IEEE INFOCOM in 2009 and is accepted to appear in IEEE/ACM Transactions on Networking. This research is joint with Hongbo Jiang of Huazong University of Science and Technology, and Arun Iyengar, Wolfgang Segmuller, Asser Tantawi, and Charles P. Wright of the IBM T.J. Watson Research Center.

bio: Erich Nahum is a research staff member in the IBM T.J. Watson Research Center. He received his Ph.D. in Computer Science from the University of Massachusetts, Amherst in 1996, advised by Jim Kurose and Don Towsley. His research has included work on SIP, HTTP, Instant Messaging, TCP/IP, workload characterization, workload generation, overload control, dynamic content, clusters, multiprocessors, operating systems, and security. He is interested in all aspects of performance in experimental networked systems. More detail can be found at http://researcher.ibm.com/researcher/view.php?person=us-nahum

Distributed computing: bridging the gap between theory and practice.

Yuval Emek

ETH

The theory of distributed computing, which lies at the heart of understanding the power and limitations of distributed systems, underwent tremendous progress over the last few decades. Despite this progress, there seems to be a widening gap between the traditional models on top of which the theory of distributed computing is built and the real-world problems we wish to investigate through these models. In this talk we will discuss the different aspects of this widening gap and present some of the efforts made in attempt to adjust the field of theoretical distributed computing to the rapidly changing needs of its practical applications. In particular, we will focus on recent advances in the study of wireless networks and on a new model for decentralized networks of "unorthodox" devices. The talk will be self-contained.

bio: Yuval Emek graduated summa cum laude from the Technion - Israel Institute of Technology with a bachelor degree in computer science and completed his master studies and Ph.D. in computer science at the Weizmann Institute. Following that, he spent one year as a post-doc at Tel Aviv University and another year in Microsoft. He currently holds a post-doc position at ETH Zurich, Switzerland. In his scientific work, Yuval studies various aspects of complex decentralized systems with an emphasis on theoretical distributed computing.

MARS: Adaptive Remote Execution Scheduler for Multithreaded Mobile Devices

Tomer London

Stanford University, Dept. of Electrical Engineering

Mobile devices face a growing demand to support computationally intensive applications like 3D graphics and computer vision. However, these devices are inherently limited by processor power density and device battery life. Dynamic remote execution addresses this problem, by enabling mobile devices to opportunistically offload computations to a remote server. We envision remote execution as a new type of cloud-based heterogeneous computing resource, or a "Cloudon-Chip", which would be managed as a system resource as if it were a local CPU, with a highly variable wireless interconnect. To realize this vision, we introduce MARS, the first adaptive, online and lightweight RPC-based remote execution scheduler supporting multi-threaded and multi-core systems. MARS uses a novel efficient offloading decision algorithm that takes into account the inherent trade-offs between communication and computation delays and power consumption. Due to its lightweight design, MARS runs on the device itself, instantly adapts its decisions to changing wireless resources, and supports any number of threads and cores. We evaluated MARS using a trace-based simulator driven by real world measurements on augmented reality, face recognition and video game applications. MARS achieves an average speedup of 57% and 33% higher energy savings over the best static client-server partitions.

bio: Tomer London is a Stanford Graduate Fellow in the Electrical Engineering PhD program at Stanford University, working on mobile computing with Professors Christos Kozyrakis and Sachin Katti. Previously, he was the co-founder and CEO of Vizmo Mobile Inc., an enterprise software startup. Tomer also served as a researcher at Intel Microarchitecture Technology Labs, and as a product lead in Bump Technologies. Tomer received his BSc from Technion Electrical Engineering dept. in '10 with Summa Cum Laude honors and is the recipient of the Robert Bosche Stanford Graduate Fellowship, Sohnis Promising Scientist Award, and the Freescale Award '10.

Flashback: A New Control Channel for Wireless Networks

Asaf Cidon

Stanford University, Dept. of Electrical Engineering

Unlike wired network protocols, Wi-Fi does not separate the data channel from the control channel, since only a single sender and receiver can communicate at a given time slot. Flashback is a system that allows multiple transmitters to send 'flashes' of high power OFDM sub-carriers without affecting the normal data transmissions on the Wi-Fi channel. By taking advantage of SNR margins of Wi-Fi channel codes, the flashes do not impose any overhead on the regular data transmission. Using this simple PHY mechanism, Flashback provides higher networking layers with a multi-user control channel, which can be used to significantly improve existing Wi-Fi protocols. During the talk we will share the results from our implementation of Flashback, and discuss their implications on the higher layers of the Wi-Fi stack.

bio: Asaf Cidon is an Electrical Engineering PhD and MBA student at Stanford University, where he conducts research on data-center and mobile systems under Professors Mendel Rosenblum and Sachin Katti. He worked at Google Israel and helped develop Google Related and previously served as a Product Manager for two start-ups. Prior to his studies, Asaf served as a team leader in an elite unit in the Israeli Intelligence Forces. He received his BSc in Computer and Software Engineering Cum Laude from the Technion, and is a recipient of the Stanford Graduate Fellowship and Sohnis Promising Scientist Award.

Multi-party Computation Forever, for Cloud Computing and Beyond

Shlomi Dolev

Math and CS, Ben-Gurion University

Three works will be described. In the first we present reactive secret sharing, that changes the secret according to unbounded sequence of common inputs, where no communication among the (dynamic set of) participants is allowed, we present a fully secure solution for simple functions but somewhat non secure solution for any function.. In the second work dynamic on-going multiparty computation, in which we consider the case of dynamic group of participants that should not know the sequence of inputs of the others, as well as should not know the function performed on the inputs. In the last work we consider the case of infinite execution with no communication among the participants where we prove that any automaton can be executed in a fully secure fashion, the construction is based on Krohn-Rhodes decomposition technique.

Joint works with Limor Lahiani, Moti Yung, Juan Garay, Niv Gilboa and Vladimir Kolesnikov

bio:Shlomi Dolev received his B.Sc. in Engineering and B.A. in Computer Science in 1984 and 1985, and his M.Sc. and D.Sc. in computer Science in 1990 and 1992 from the Technion Israel Institute of Technology. From 1992 to 1995 he was at Texas A and M University postdoc of Jennifer Welch. In 1995 he joined the Department of Mathematics and Computer Science at Ben-Gurion University where he is now a full professor and the dean of natural sciences.

He was a visiting researcher/professor at MIT, DIMACS, and LRI, for several periods during summers. Shlomi is the author of the book "self-stabilization" published by the MIT Press. He published two hundreds journal and conference scientific articles, and patents. Shlomi served in the program committee of more than 60 conferences including: the ACM Symposium on Principles of Distributed Computing, and the International Symposium on DIStributed Computing. He is an associate editor of the IEEE Transactions on Computers, the AIAA Journal of Aerospace Computing, Information and Communication and a guest editor of the Distributed Computing Journal and the Theoretical Computer Science Journal. His research grants include IBM faculty awards, Intel academic grants, Verisign, ISF, US Airforce, EU and NSF grants.

Shlomi is the founding chair of the computer science department at Ben-Gurion University, where he now holds the Rita Altura trust chair in computer science. His current research interests include distributed computing, distributed systems, security and cryptography and communication networks; in particular the self-stabilization property of such systems. Recently, he is involved in optical computing research.

Title: Crafting Fast Wait-Free Algorithms

Alex Kogan

Technion, CS

Lock-freedom is a progress guarantee that ensures overall program progress. Wait-freedom is a stronger progress guarantee that ensures the progress of each thread in the program. The latter property is valuable for systems that need to be responsive, such as real-time systems, operating systems, etc. While many practical lock-free algorithms are known in the literature, constructing wait-free algorithms is considered a complicated task that results in inefficient implementations. In this talk, we present first construction of a wait-free queue and a methodology called fast-path-slow-path, which allows the wait-free algorithms (and our queue in particular) to practically match the performance of the lock-free ones. Subsequent work has used this methodology to create other efficient wait-free algorithms.

bio: Alex Kogan is a Ph.D. student in the Department of Computer Science at the Technion. He holds M.Sc. (2008) and B.A (Summa Cum Laude, 2002) degrees from the same department. His research interests lie at the intersection of distributed and mobile computing, and in parallel computing. Specifically, he is interested in constructing efficient and reliable distributed algorithms for mobile networks, utilizing emergent technologies for wireless communication and the availability of cloud services. Recently, he became interested in exploring and boosting the performance of modern multi-core systems by devising efficient concurrent algorithms.

Replicate and Bundle (RnB) - A Relief for Certain Data Center Bottlenecks

Shachar Raindel

Technion, EE

In this talk, we present the Replicate and Bundle (RnB) scheme for relieving back-end processor and network bottlenecks in read-mostly key-value storage systems wherein each user request spawns a large number of back-end small-item requests. This is common in Web 2.0 and online social network systems. Adding processors is of little help because this increases the number of back-end requests per user request, thereby also increasing the overall processor and network load. Instead, RnB adds memory and replicates the stored data, thereby permitting each user request to be serviced through fewer back-end requests, reducing the total amount of work required from the network-processing and storage components of the system. The scheme is very easy to deploy, completely distributed, and while oblivious to the workload, beneficially exploits its spatial locality.

We have studied RnB through simulation, and augmented this with a micro-benchmark in order to estimate the expected actual system performance.

Our results show that by using RnB, two major scaling bottlenecks are considerably relieved: 1) the TCP InCast issue and 2) the memcached multi-get hole. When utilizing the requests' locality, we achieve a considerable improvement in these bottlenecks with relatively little additional memory. In fact, RnB can use existing replicas (included for fault tolerance), in which case the extra cost is minimal if any. Finally, we note that this is yet another example of judicious exploitation of redundancy for performance enhancement.

bio: Shachar Raindel holds a BSc in Computer Engineering from the Technion. He served in the IDF in a technical R&D position. He is now completing his MSc thesis at the Technion's Electrical Engineering department under the guidance of Prof. Yitzhak Birk.

Self-stabilizing Autonomic Recoverers

Dr. Olga Brukman

Technion, CS

This talk introduces theoretical foundations for system architectures and algorithms for creating truly robust autonomic systems -- systems that are able to recover automatically from unexpected failures. We consider various settings of system transparency. We consider black box and transparent box software packages. The general assumption is that a software package fails when it encounters an unexpected environment state -- a state the package was not programmed to cope with. Creating a system that anticipates every possible environment state is not feasible due to the size of the environment. Thus, an autonomic system design should imply that a system is able to overcome an unexpected environment state either by executing a recovery action that restores a legal state or by finding a new program that respects the specifications and achieves the software package goals in the current environment.

In the first part of this talk, we consider software packages to be black boxes. We propose modeling software package flaws (bugs) by assuming eventual Byzantine behavior of the package. A general, yet practical, framework and paradigm for the monitoring and recovery of systems called autonomic recoverer is proposed. In the second part we consider a software package to be a transparent box and introduce the recovery oriented programming paradigm. Programs designed according to the recovery oriented programming paradigm include important safety and liveness properties and recovery actions as an integral part of the program. We design a pre-compiler that produces augmented code for monitoring the properties and executing the recovery actions upon a property violation. Finally, in the third part, we consider a highly dynamic environment, which typically implies that there are no realizable specifications for the environment, i.e., there does not exist a program that respects the specifications for every given environment. We suggest searching for a program in run time by trying all possible programs on environment replicas in parallel. We design control search algorithms that exploit various environment properties.

bio: Olga had graduated with PhD in Computer Science under supervision of Prof. Shlomi Dolev from Ben-Gurion University, Beer-Sheva, Israel in 2008. The main focus of her work was exploring formal definitions of the system architectures for autonomic systems and using techniques from self-stabilization to create true self-recovery systems. Since then she worked in Microsoft Israel in PC Health group on creating monitoring and recovery scenarios for PC Advisor. Next, she spent a year in Deutsche Telekom Labs in Ben-Gurion University working on spam mitigation techniques and security concerns in IPv6. Then, she was with Inifinidat.com, a storage systems startup.

Observations on Linux Development

Prof. Dror Feitelson

Computer Science, Hebrew University

Linux is used extensively in systems research as a platform for the implementation of new ideas, exploiting its open-source nature. But Linux is also interesting as an object of study about software engineering. In particular, Linux defies common management theories, as it lacks any coherent plan or management structure, but still grows at an ever-increasing rate, while also gaining market share. We will review some previous studies of Linux development and add new observations regarding the lifecycle model and code complexity.

The presentation includes results of my students Ayelet Israeli, Ahmad Jbara, and Adam Matan.

bio: Dror Feitelson has been on the faculty of the School of Computer Science and Engineering at the Hebrew University of Jerusalem since 1995. His major contributions have been in parallel job scheduling (where he co-founded the JSSPP series of workshops) and workload modeling (where he maintains the parallel workloads archive). Recently he has also started to work on software engineering, and in particular the development of open-source systems like Linux.

On Distributed Coordination Strategies in Cooperative Wireless Networks

Dr. Lavy Libman

School of Information Technologies, University of Sydney

Cooperative and opportunistic communication techniques in wireless networks promise significant performance benefits over traditional methods that do not exploit the broadcast nature of wireless transmissions. However, such techniques generally require coordination among the participating nodes, e.g. to discover available neighbors or negotiate the best course of action after every packet broadcast. The associated coordination overheads negate much of the cooperation benefits for applications with strict latency requirements, or in networks with highly dynamic topologies. This talk will highlight distributed cooperation strategies, where each node overhearing a packet decides independently whether to retransmit it, without explicit coordination with the source, intended receiver, or other neighbours in the vicinity. We formulate two non-traditional optimization problems that arise in this context, present their solution methodology and demonstrate the superior performance attained by the respective strategies.

Bio: Lavy Libman is a Visiting Scientist (during the winter semester of 2011-2012) at the Department of Electrical Engineering, Technion - Israel Institute of Technology, where he also received his PhD in 2003. Since 2009, he is a senior lecturer at the School of Information Technologies, University of Sydney. He also continues to be associated with the Networks research group in NICTA (the national ICT research institute in Australia), where he was a researcher between 2003-2009. His research revolves around the design and optimization of wireless networks, with a particular interest in cooperative and opportunistic techniques, protocols for resource-limited devices, and game-theoretic modeling. Dr. Libman is a senior member of the IEEE Communications Society and is serving as an associate editor of IEEE Transactions on Wireless Communications. He is a publicity co-chair of IEEE Infocom 2012, served as a program co-chair of ICCCN 2010 and WiOpt 2010, and continues to be involved as a program committee member of several international conferences, including IEEE Infocom, IEEE LCN, ACM MSWiM, and WiOpt.

Highly Efficient Synchronization Techniques

Prof. Panagiota Fatourou

Foundation for Research and Technology-Hellas, Institute of Computer Science

We present highly-efficient synchronization techniques and experimentally show that these techniques outperform most state of the art lock-based and lock-free synchronization mechanisms. One of the techniques ensures, in addition, wait-freedom.

We have used these techniques to implement common concurrent data structures, like stacks and queues. Our experiments show that these data structure implementations have much better performance than state of the art shared stack and queue implementations which ensure only weaker progress properties than one of our techniques.

Talk slides.

Bio: Panagiota Fatourou is an Assistant Professor at the Department of Computer Science, University of Crete and an affiliated faculty member of the Institute of Computer Science (ICS) of the Foundation for Research and Technology-Hellas (FORTH). Prior to joining the University of Crete and FORTH ICS, she was a full-time faculty member at the Department of Computer Science of the University of Ioannina. The academic years 2000 and 2001, she was a postdoc at Max-Planck Institut fur Informatik, Saarbrucken, Germany, and at the Computer Science Department of the University of Toronto, Canada. She got a degree in Computer Science from the University of Crete, and a PhD degree in Computer Engineering from the University of Patras. Her research interests focus on the theory of parallel and distributed computing.

Network Science - A Network of Sciences

Prof. Ariel Orda

Technion, Department of Electrical Engineering

Network Science is a newly emerging discipline with applications in a variety of domains, such as Communication Networks, Power Grid Networks, Transportation Networks, Social Networks and Biological Networks. Focusing on communication networks, we shall discuss what network science should be and what it should consist of. The talk will also feature some historical anecdotes, tracing back to ancient times. Further details would be a spoiler.

Bio: Ariel Orda is a professor at the Department of Electrical Engineering in the Technion. His research interests include network routing, survivability, QoS provisioning, wireless networks, the application of game theory to computer networking and network pricing. For more information, see http://webee.technion.ac.il/Sites/People/ArielOrda/.

Estimating Sizes of Social Networks via Biased Sampling

Dr. Liran Katzir

Yahoo! Research Haifa

Online social networks have become very popular in recent years and their number of users is already measured in many hundreds of millions. For various commercial and sociological purposes, an independent estimate of their sizes is important. In this work, algorithms for estimating the number of users in such networks are considered. The proposed schemes are also applicable for estimating the sizes of networks' sub-populations.

The suggested algorithms interact with the social networks via their public APIs only, and rely on no other external information. Due to obvious traffic and privacy concerns, the number of such interactions is severely limited. We therefore focus on minimizing the number of API interactions needed for producing good size estimates. We adopt the abstraction of social networks as undirected graphs and use random node sampling. By counting the number of collisions or non-unique nodes in the sample, we produce a size estimate. Then, we show analytically that the estimate error vanishes with high probability for smaller number of samples than those required by prior-art algorithms. Moreover, although our algorithms are provably correct for any graph, they excel when applied to social network-like graphs. The proposed algorithms were evaluated on synthetic as well real social networks such as Facebook, IMDB, and DBLP. Our experiments corroborated the theoretical results, and demonstrated the effectiveness of the algorithms.

Bio: Liran is a Research Engineer in Yahoo! Israel Labs. He received his B.A., M.A., and Ph.D. degrees in computer science from the Technion--Israel Institute of Technology, Haifa, Israel, in 2001, 2005, and 2008 respectively. His Ph.D. thesis deals with scheduling algorithms in advanced wireless networks. His current main research interests are algorithmic aspects of Web technologies. Liran is the co-author of several refereed journal and conference papers.

Orleans: A Programming Model for the Cloud

Dr. Gabriel Kliot

eXtreme Computing Group, Microsoft Research

What if you could build the next Facebook or Twitter with just a few hundred lines of code ? and scale it to hundreds of millions of users across thousands of servers, right out of the box? Orleans is a cloud programming model and runtime from Microsoft Research, which can make this the new "norm".

Orleans is a software framework for building 'client + cloud' applications. It encourages the use of simple concurrency patterns that are easy to understand and implement correctly, with an actor-like programming model for distributed applications. It uses declarative specification of persistence, replication, and consistency properties, as well as lightweight transactions to support the development of reliable and scalable 'client + cloud' applications.

Bio: Gabriel Kliot a Research Software Development Engineer in the eXtreme Computing Group, Microsoft Research. He's been working on Orleans since its early days. Gabriel also leads project Horton: a distributed database for managing and querying large distributed graphs. Gabriel obtained his PhD in Computer Science from the Technion in 2009, where his thesis focused on Probabilistic Middleware Services for Wireless Mobile Ad-Hoc Networks, as well as other various aspects of Distributed Systems. In his spare time Gabriel is a competitive long-distance runner.

How Secure are Secure Internet Routing Protocols?

Prof. Sharon Goldberg

Computer Science Department at Boston University

A decade of research has been devoted to addressing vulnerabilities in global Internet routing system. The result is a plethora of security proposals, each providing a different set of security guarantees. To inform decisions about which proposal should be deployed in the Internet, we present the first side-by-side quantitative comparison of the major security variants. We evaluate security variants on the basis of their ability to prevent one of the most fundamental forms of attack, where attacker manipulates routing messages in order to attract traffic to a node it controls (so that it can tamper, drop, or eavesdrop on traffic). We combine a graph-algorithmic analysis with simulations on real network data to show that prior analysis has underestimated the severity of attacks, even when the strongest known secure routing protocol is fully deployed in the network. We find that simple access control mechanisms can be as effective as strong cryptographic approaches, and it is really the combination of these two competing approaches that leads to a significant improvement in security. Time permitting, we will also discuss some of the economic and engineering issues that must be addressed before any of these proposals can realistically be deployed in the Internet.

Based on joint work with Michael Schapira, Pete Hummon, Jennifer Rexford and Phillipa Gill.

Bio: Sharon Goldberg is an assistant professor of computer science at Boston University. She received her PhD from Princeton in 2009, and her BASc from the University of Toronto in 2003. She has worked as a network engineer at Bell Canada and Hydro One Networks, and as a researcher at Microsoft, Cisco, and IBM. Her research focuses on finding practical solutions to problems in network security, by leveraging formal techniques from cryptography and game theory.

A Shape Analysis for Optimizing Parallel Graph Programs

Dr. Roman Manevich

University of Texas at Austin

In the first part of the talk I will give a high-level introduction to Galois, a framework for designing and implementing parallel graph algorithms and related concepts. I will explain what are ordered/unordered graph algorithms and how optimistic parallelism is achieved using transactional boosting.

In the second part of the talk I will describe a new shape analysis, which is used for analyzing graph algorithms written with Galois. The shape analysis infers properties that can be used to optimize the graph algorithm by reducing two of the main overheads of the system --- synchronization overheads and rollback logging overheads, We implemented the analysis on top of TVLA and applied it to several graph algorithms. The optimized (parallel) graph algorithms run 2x to 12x faster than the unoptimized algorithms.

This talk is based on joint work with Dimitrios Prountzos, Keshav Pingali, and Kathryn McKinley, presented at POPL 2011.

Bio: Roman Manevich is a post-graduate student at the University of Texas at Austin working with Prof. Keshav Pingali on programming languages aspects of parallelizing graph algorithms. Previously he spent a year as a post-doc at the University of California Los Angeles, working with Prof. Rupak Majumdar on verifying correctness of transactional memories.. His Research interests are primarily in the area of formal verification and synthesis of concurrent programs. He obtained his PhD in Computer Science from Tel-Aviv University in 2009. His thesis focused on verification of sequential and concurrent programs with dynamic memory allocation.

How to win Friends and Influence People, Truthfully

Yaron Singer

Computer Science Division, University of California at Berkeley

Throughout the past decade there has been extensive research on algorithmic and data mining techniques for solving the problem of influence maximization in social networks: if one can convince a subset of individuals to influence their friends to adopt a new product or technology, which subset should be selected so that the spread of influence in the social network is maximized?

Despite the progress in modeling and techniques, the incomplete information aspect of problem has been largely overlooked. While the network structure is often available, the inherent cost individuals have for influencing friends is difficult to extract.

In this talk we will discuss mechanisms that extract individuals' costs in well studied models of social network influence. We follow the mechanism design framework which advocates for truthful mechanisms that use allocation and payment schemes that incentivize individuals to report their true information. Beyond their provable theoretical guarantees, the mechanisms work well in practice. To show this we will use results from experiments performed on the mechanical turk platform and social network data that provide experimental evidence of the mechanisms' effectiveness.

Dr. Philip M. Merlin Memorial Lecture and Prize Award
Search Flavors - Trends and Opportunities

Prof. Yossi Matias

Senior Director and Head of Israel R&D Center, Google

This talk will discuss some recent developments in search, emerging in various shapes and forms. We will highlight some challenges, and point to some search trends that play an increasing role in multiple domains. We will also discuss the power of data and the significant role of cloud technologies in facilitation of new opportunities. Some of the core technologies and global innovations developed in Google's R&D center in Israel will be highlighted.

Bio: Yossi Matias is the director of the Google Tel Aviv R&D Center. He joined Google in August 2006 to build and lead the center, and is responsible for the strategy and operation of the center.

Prof. Matias is a faculty member of the School of Computer Science at Tel Aviv University (on leave), having joined the faculty in 1997 as a recipient of the prestigious Alon Fellowship. He was recently a visitor at Stanford Univ (2004-2006). Prior to his position at Tel Aviv University, he was a Research Scientist at Bell Laboratories (1992-1997). He received his Ph.D. with distinction from Tel Aviv University (1992), M.Sc. from the Weizmann Institute (1987) (thesis with excellence), and B.Sc. (cum laude) from Tel Aviv University (1985). Previously he served in the Israeli IDF as an Israeli Air Force pilot.

Matias authored over 100 scientific and technological research papers and is the inventor of over 20 patents. His research and expertise span many diverse areas, and range from highly theoretical works to works involving applied technology and extensive system implementation. His research and technology developments and innovations include: data analysis, algorithms for massive data sets, data streams, data synopses, parallel computation, data compression, data and information management systems, data security and privacy, video scrambling, and Internet technologies. He is a frequent speaker and was on the program committees of numerous international scientific and technology conferences. He is on the founding steering committee of the Israeli Academic Grid and was a member of a national committee evaluating strategies for Grid technologies.

In addition to his academic and scientific work, for over a decade Matias has been heavily involved in the high tech industry and in technology and product development. He founded in Bell Labs the Lucent Personalized Web Assistant project (1996), developing one of the early Internet privacy and anti-spam technologies (sold by Lucent to a CMGI company); he co-founded and led Zapper Technologies (1999), developing advanced contextual and personalized search technologies; he was the CTO and Chief Scientist of Hyperroll, leading the technology strategy of its high performance data aggregation software that is at the core of data warehouses and Business Intelligence applications of multiple Fortune 100 enterprises. Matias has served as a consultant and adviser to many technology companies, including public and startup companies, and to venture capital firms.

Yossi Matias is a recipient of the 2005 ACM-EATCS Godel prize in Theoretical Computer Science "for the profound impact on the theory and practice of the analysis of data streams". His work was instrumental in setting up a scientific field of algorithmics for massive data sets, and technologies now extensively used in industries involving massive data sets.

Side Channels in Cloud Services: The Case of Deduplication in Cloud Storage

Prof. Benny Pinkas

Bar-Ilan University

The talk will discuss deduplication, a form of compression in which duplicate copies of files are replaced by links to a single copy. Deduplication is known to reduce the space and bandwidth requirements of Cloud storage services by more than 90%, and is most effective when applied across multiple users.

We study the privacy implications of cross-user deduplication. We demonstrate how deduplication can be used as a side channel which reveals information about the contents of files of other users, as a covert channel by which malicious software can communicate with its control center, or as a method to retrieve files about which you have only partial information.

Due to the high savings offered by cross-user deduplication, cloud storage providers are unlikely to stop using this technology. We therefore propose mechanisms that enable cross-user deduplication while ensuring meaningful privacy guarantees.

Bio: Benny Pinkas is an associate professor in the department of Computer Science at Bar Ilan University, Israel. He received his PhD from the Weizmann Institute of Science in 2000. Following that worked in the research labs of Intertrust technologies and Hewlett-Packard, and was a member of the faculty in the department of Computer Science of the University of Haifa. His research interests include cryptography, privacy, and computer and communications security.

Abstraction-Guided Synthesis of Synchronization

Dr. Eran Yahav

Faculty Member, Computer Science Dept., Technion

In this talk I will present a framework for synthesizing efficient synchronization in concurrent programs, a task known to be difficult and error-prone when done manually. The framework is based on abstract interpretation and can infer synchronization for infinite state programs. Given a program, a specification, and an abstraction, we infer synchronization that avoids all (abstract) interleavings that may violate the specification, but permits as many valid interleavings as possible. I will show application of this general idea for automatic inference of atomic sections and memory fences in programs running over relaxed memory models.

Joint work with Michael Kuperstein, Martin Vechev, and Greta Yorsh.

Bio: Eran Yahav is a faculty member of the Computer Science department at the Technion, Israel. Prior to his position at Technion, he was a Research Staff Member at the IBM T.J. Watson Research Center in Hawthorne, New York (2004-2010). He received his Ph.D. from Tel Aviv University (2004) and his B.Sc. (cum laude) from the Technion-Israel Institute of Technology (1996). His research interests include static and dynamic program analysis, program synthesis, and program verification.

Eran is a recipient of the prestigious Alon Fellowship for Outstanding Young Researchers, and the Andre Deloro Career Advancement Chair in Engineering.

Fat-Trees Routing and Node Ordering Providing Contention Free Traffic for MPI Global Collectives

Eitan Zahavi

Senior Director of Engineering, Mellanox Technologies LTD, Israel.

As the size of High Performance Computing clusters grows, the increasing probability of interconnect hot spots degrades the latency and effective bandwidth the network provides. This paper presents a solution to this scalability problem for real life constant bisectional-bandwidth fat-tree topologies. It is shown that maximal bandwidth and cut-through latency can be achieved for MPI global collective traffic. To form such congestion-free configuration, MPI programs should utilize collective communication, MPI-node-order should be topology aware, and the packets routing should match the MPI communication patterns. First, we show that MPI collectives can be classified into unidirectional and bidirectional shifts. Using this property, we propose a scheme for congestion-free routing of the global collectives in fully and partially populated fat trees running a single job. Simulation results of the proposed routing, MPI-node-order and communication patterns show a 40% throughput improvement over previously published results for all-to-all collectives.

Bio: Senior Director of Engineering, Mellanox Technologies LTD, Israel.

A cofounder of Mellanox, served as Mellanox's Software Architect since October 2005, and as Director of Design Technologies since May 1999. Today Eitan leads the Design Automation group and researches network architectures. As part of his netwrok architecture role he is a co-chair of the IBTA Management working group, and focuses on cluster topologies, congestion control, deterministic routing and adaptive routing technologies.

Eitan is also an M.Sc. student of Avinoam Kolodny and Israel Cidon at the Technion EE department studying loss-less networks in and out of the chip.

Prior to joining Mellanox, from March 1992 to April 1999, Mr. Zahavi served in various Chip Design and Design Automation and EDA positions at Intel in both the Micro Processors group and Intel's Strategic CAD Lab.

Mr. Zahavi holds a Bachelor of Science in Electrical Engineering at the Technion (Israel's Institute for Technology) since 1987.

IBM Watson and the Jeopardy! Challenge

Dr. David Carmel and Dr. Dafna Sheinwald

IBM Research -- Haifa

Over the last days, millions of viewers witnessed computing history being made as IBM's Watson question answering system defeated Jeopardy! quiz show champions Brad Rutter and Ken Jennings. Watson is an application of advanced natural language processing, information retrieval, knowledge representation and reasoning, and machine learning technologies to the field of open domain question answering. Watson runs on a cluster of 90 IBM Power 750 servers in 10 racks with a total of 2880 POWER7 processor cores and 16 Terabytes of RAM, enabling it to respond within less than 3 seconds. The deep analytic capabilities and systems technologies that enabled Watson to win at Jeopardy! now can be customized for specific industry lexicons and applications to help humans make smarter, faster and more effective decisions.

In this talk we will tell more about the challenge, Watson's architecture and technologies, our contributions to the system, and some insights from the man vs. machine match.

David Carmel is a Research Staff Member at the Information Retrieval group at IBM Haifa Research Lab. David's research is focused on search in the enterprise, query performance prediction, social search, and text mining. David has published more than 80 papers in Information retrieval and Web journals and conferences, and serves in the Program Committee of many conferences and workshops.
https://researcher.ibm.com/researcher/view.php?person=il-CARMEL

Dafna Sheinwald is a researcher at the Information Retrieval group of IBM Haifa Research Lab, focusing mainly on different aspects of search in the enterprise: various sources of data, similar data repeating in different sites, combination of internal and external data, and system configurations addressing load problems. Dafna has expertise also in Data Compression and in algorithms and data structures. She often serves in the committee of the Data Compression Conference.

Causality, Knowledge and Coordination in Distributed Systems

Ido Ben-Zvi

Technion, Electrical Engineering Department

Coordinating the proper ordering of events across remote sites is a central task of distributed applications. In asynchronous systems, such coordination depends in an essential way upon message chains, as captured by Lamport's happened-before relation. The relation provides a useful approximation of causality, in the sense that in asynchronous systems two event can only be causally related if they are Lamport related.

The talk will consider coordination and causality in synchronous systems, where upper bounds are available on message transmission times over each channel, and processes share a global clock. Here, active coordination is required whenever a spontaneous external input is meant to trigger an ordered sequence of responses across various sites. We capture the essence of such a coordination task in a proposed class of coordination problems called Ordered Response. Within this framework we embark on a search for a similar notion of causality. We will not touch upon knowledge in any great depth, but consider that in a synchronous setting both message chains and the passage of time can be used to spread information across the system, and hence to enable coordination.

Indeed, it turns out that the synchronous analog for Lamport's causality is a structure that carefully combines message chains and the existing upper bounds on transmission times. This causal structure, called the centipede, is shown to be necessary in every solution of the Ordered Response problem.

Portability and Performance of Applications in the Manycore Era

Dr. Erven Rohou

INRIA Rennes, ALF Research Group

For many years, the frequency of microprocessors has grown at an exponential pace (from 20 MHz in 1990 to 2 GHz in 2000). Since 2002 however, despite considerable effort, the frequency has been plateauing. Advances in technology and micro-architecture now translate into more parallelism. The consequences on the software industry are dramatic: most existing software has been designed with a sequential model in mind, and even parallel applications contain residual sequential sections. The performance of these applications will ultimately be driven by the performance of the sequential part, as stated by Amdahl's law.

For this reason we envision that future architectures will consist of many simple cores, but also a few very complex cores. The performance of applications is unlikely to automatically increase with new generations of future processors, as it used to happen in the past. Even plain portability is at risk for applications developed with a specific model of parallelism in mind. This talk proposes directions to address the problem of portability and performance of applications on future manycore processors, taking into account both parallel and residual sequential code sections.

IBM's PowerEN Developer Cloud: Fertile Ground for Academic Research

Dr. Amit Golander

IBM Haifa Research Lab

IBM's newest technology, the Power Edge of Network (PowerEN) processor, merges network and server attributes to create a new class of wire-speed processor. PowerEN is a hybrid computer that employs: massive multithreading capabilities, integrated I/O and unique special-purpose accelerators for compression, cryptography, pattern matching, XML and Network processing.

As a novel architecture, the PowerEN processor offers fertile ground for research. It can facilitate the development of faster applications in many fields of computer science such as Networking, Cryptography, Virtualization, Bioinformatics, SOA, and Systems. IBM encourages academic research and has set up the "PowerEN Developer Cloud" infrastructure to allow it. Israeli universities are of the first to perform research on this global infrastructure.

Distributed peta-scale data transfer

Jesse Alpert

Google

Many internal Google systems need to copy huge volumes of data between Google's data centers. Solving this problem requires managing very high traffic volumes, dealing effectively with packet loss, scheduling and prioritizing the use of constrained resources and avoiding a single point of failure.

Effingo, Google's internal large scale copy service, is designed to scale and sustain very high traffic throughput. Effingo features the following characteristics:
o A custom network protocol over UDP.
o Distributed scheduling decisions when managing the use of constrained resources.
o Multi-point topological efficiency.
o High availability even when clusters are down, or slow.
o Scalability to many files, many users and to very high throughput globally.

In this talk I'll describe the challenges of peta-scale data transfer, and how they are addressed using Effingo. This is a joint work with many other Google engineers and researchers.

Efficient Cloud Operations via Job-Migration and Pricing

Dr. Ishai Menache

Microsoft Research New England

Cloud computing technology offers on-demand network access to shared pools of configurable computing resources, such as virtual servers, applications and software services. This paradigm delivers the economy of scale to users via large datacenters, fast and flexible provisioning of resources, and the freedom from long-term investments in equipment. Despite the potential advantages, a new set of challenges must be overcome before cloud providers can see a return on their investments; namely, dealing with the uncertainty involved in operating cloud systems, both in terms of supply (time-varying energy prices and availability) and demand for computing resources.

One way to reduce operation costs is by exploiting the spatiotemporal variation of electricity prices. I start by showing how techniques from online algorithms can be employed to develop algorithms that move computation to datacenters in which energy is available at a cheaper price. The algorithm we design performs remarkably well on empirical electricity-prices and job-demand data. In the second part of the talk, I develop a general queuing-based model for the study of cloud computing economics, incorporating stochastic demands and diversity in the application types and user preferences. Despite the high level of heterogeneity, I show that a simple per-unit price (currently employed by most cloud platforms) suffices to induce social efficiency. I will conclude with a discussion of ongoing work on combining energy-aware scheduling and pricing for optimizing profits.

Large scale iterative computing using GraphLab

Dr. Danny Bickson

Machine Learning Department, Carnegie Mellon

As the available computing power around us keeps growing (clouds, clusters, GPUs etc.) and the amount of collected data is increasing, new challenges arise when designing algorithms for handling the data. In this talk, I will cover my work concerning both the theoretical and the practical aspects of parallel and distributed large scale computing on massive datasets. I will discuss the design of efficient iterative algorithms to be used in large scale settings, as well as actual algorithm implementation on different distributed platforms such as multicore, computer clusters and GPUs.

As a case study I will relate to the problem of modeling network flows, which tend to exhibit heavy tailed behavior. I will describe the theory developed for computing efficient inference in linear heavy tailed probabilistic graphical models: for the first time a method for computing exact inference in this model, where state-of-the-art approaches are using only approximations. We further design efficient iterative algorithms for inference and analyze their properties.

From the practical side, I will present the design and implementation of the GraphLab framework, a parallel computing abstraction for iterative sparse graph algorithms. The GraphLab framework is used to rapidly prototype a distributed implementation of the developed iterative inference algorithms, hiding implementation details like caching, load balancing, data partitioning and scheduling. I will demonstrate the applicability of GraphLab to the developed inference techniques using real network data obtained from the PlanetLab network. Experimental results demonstrate high scalability without compromising the solution accuracy. I will cover briefly other interesting applications as parallel Lasso on GPUs and distributed matrix factorization.

Stealing Reality - the New Menace, Already Here

Dr. Yaniv Altshuler

Ben Gurion University, Deutsche Telekom Laboratories

In this talk we will discuss the threat of malware targeted at extracting information about the relationships in a real-world social network as well as characteristic information about the individuals in the network, which we dub "Stealing Reality". We present Stealing Reality (SR), explain why it differs from traditional types of network attacks, and discuss why its impact is significantly more dangerous than that of other attacks. We also present our initial analysis of this attack, based on real-world mobile network data, and show how in many scenarios such attacks will be very difficult (if not impossible) to detect using currently available network monitoring systems.

Caching for Realtime Search

Dr. Eddie Bortnikov

Yahoo! Research

Modern search engines feature real-time indices, which incorporate changes to content within seconds. As search engines also cache search results for reducing user latency and back-end load, without careful real-time management of search results caches, the engine might return stale search results to users despite the efforts invested in keeping the underlying index up to date. We propose an architectural component called CIP - the cache invalidation predictor. CIPs invalidate supposedly stale cache entries upon index modifications. We propose CIP heuristics, and evaluate them in an authentic environment (a real evolving corpus and query stream of a large commercial news search engine. We show that a classical cache replacement policy, LRU, completely fails to guarantee freshness over time, whereas our CIPs serve 97% of the queries with fresh results. Our policies incur a negligible impact on the baseline's cache hit rate, in contrast with traditional age-based invalidation, which must severely reduce the cache performance in order to achieve the same freshness. We demonstrate that the computational overhead of our algorithms is minor, and that they even allow reducing the cache's memory footprint.

Transactional Memory Today

Prof. Maurice Herlihy

Brown University, Computer Science Department

"Transactional Memory" replaces conventional multiprocessor locks, monitors, and conditions with a transactional model of synchronization. The original proposal dates back to 1993, but even today, there is a vigorous debate about what it means and what it should do. This debate sometimes generates more heat than light: terms are not always well-defined and criteria for making judgments are not always clear.

This talk will try to impose some order on the conversation. TM itself can encompass hardware, software, speculative lock elision, and other mechanisms. The benefits sought encompass simpler implementations of highly-concurrent data structures, better software engineering for concurrent platforms and enhanced performance. These goals are distinct, and sometimes in conflict.

The Cost of Privatization

Prof. Hagit Attiya

Technion, Computer Science Department

Software transactional memory (STM) guarantees that a transaction, consisting of a sequence of operations on the memory, appears to be executed atomically. In practice, it is important to be able to run transactions together with non-transactional legacy code accessing the same memory locations, by supporting privatization. This should be provided without sacrificing the parallelism offered by today's multicore systems and multiprocessors.

This paper proves an inherent cost for supporting privatization, which is linear in the number of privatized items. Specifically, we show that a transaction privatizing k items must have a data set of size at least k, in an STM with invisible reads, which is oblivious to different non-conflicting executions and guarantees progress in such executions. When reads are visible, it is shown that Omega(k) memory locations must be accessed by a privatizing transaction, where k is the minimum between the number of privatized items and the number of concurrent transactions guaranteed to make progress, thus capturing the trade off between the cost of privatization and the parallelism offered by the STM.

This is joint work with Eshcar Hillel (CS, Technion)

Sparse Reliable Graph Backbones

Dr. Yuval Emek

Microsoft Israel R&D and the School of Electrical Engineering, Tel Aviv University

In this talk we discuss the notion of network reliability: Given a connected graph G and a failure probability p(e) for each edge e in G, the reliability of G is the probability that G remains connected when each edge e is removed independently with probability p(e).

I will show that every n-vertex graph contains a spanning subgraph with O(n \log n) edges whose reliability is very close to that of G. Our proof is based on a polynomial time randomized algorithm for constructing this sparse subgraph.

The talk will be self contained.

Based on a joint work with Shiri Chechik, Boaz Patt-Shamir, and David Peleg.

The Turtles Project: Design and Implementation of Nested Virtualization

Muli Ben-Yehuda

IBM Haifa Research Lab

In classical machine virtualization, a hypervisor runs multiple operating systems simultaneously, each on its own virtual machine. In nested virtualization, a hypervisor can run multiple other hypervisors with their associated virtual machines. As operating systems gain hypervisor functionality---Microsoft Windows 7 already runs Windows XP in a virtual machine---nested virtualization will become necessary in hypervisors that wish to host them.

We present the design, implementation, analysis, and evaluation of high-performance nested virtualization on Intel x86-based systems. The Turtles project, which is part of the Linux/KVM hypervisor, runs multiple unmodified hypervisors (e.g., KVM and VMware) and operating systems (e.g., Linux and Windows). Despite the lack of architectural support for nested virtualization in the x86 architecture, it can achieve performance that is within 6-8% of single-level (non-nested) virtualization for common workloads, through multi-dimensional paging for MMU virtualization and multi-level device assignment for I/O virtualization.

Joint work with M. D. Day, Z. Dubitzky, M. Factor, N. Har'El, A. Gordon, A. Liguori, O. Wasserman, and B.-A. Yassour.

Utility Dependence in Correct and Fair Rational Secret Sharing

Prof. Yehuda Lindell

Department of Computer Science, Bar Ilan University

The problem of carrying out cryptographic computations when the participating parties are rational in a game-theoretic sense has recently gained much attention. One problem that has been studied considerably is that of rational secret sharing. In this setting, the aim is to construct a mechanism (protocol) so that parties behaving rationally have incentive to cooperate and provide their shares in the reconstruction phase, even if each party prefers to be the only one to learn the secret.

Although this question was only recently asked by Halpern and Teague (STOC 2004), a number of works with beautiful ideas have been presented to solve this problem. However, they all have the property that the protocols constructed need to know the actual utility values of the parties (or at least a bound on them). This assumption is very problematic because the utilities of parties are not public knowledge. We ask whether this dependence on the actual utility values is really necessary and prove that in the basic setting, rational secret sharing cannot be achieved without it. On the positive side, we show that by somewhat relaxing the standard assumptions on the utility functions, it is possible to achieve utility independence. In addition to the above, we observe that the known protocols for rational secret sharing that do not assume simultaneous channels all suffer from the problem that one of the parties can cause the others to output an incorrect value. (This problem arises when a party gains higher utility by having another output an incorrect value than by learning the secret itself; we argue that such a scenario is not at all unlikely.) We show that this problem is inherent in the non-simultaneous channels model, unless the actual values of the parties' utilities for this attack is known, in which case it is possible to prevent this from happening.

Joint work with Gilad Asharov (presented at CRYPTO 2009).

Introduction to NoSQL and Cassandra

Ran Tavory

Outbrain

NoSQL (Not Only SQL) is a movement promoting a loosely defined class of non-relational data stores that break with a long history of relational databases. These data stores may not require fixed table schemas, usually avoid join operations and typically scale horizontally. Academics and papers typically refer to these databases as structured storage.

Notable production implementations include Google's BigTable and Amazon's Dynamo. However, there are also many publicly available open source variants including HBase and Cassandra.

In the talk I'll be giving an introduction to nosql (Not Only SQL) and Cassandra, an open-source implementation of a column oriented data store originally developed at facbook which relies upon Google's BitTable model as well as Amazon's Dynamno system.

Talk slides.

Reliable data sharing using unreliable storage

Alex Shraer

Tehcnion, Electrical Engineering Department

Distributed storage architectures provide a cheap and scalable alternative to expensive monolithic disk array systems currently used in enterprise environments. Such distributed architectures make use of many unreliable servers (or storage devices) and provide reliability through replication. The large number of fault-prone servers requires supporting dynamic changes when faulty servers are removed from the system and new ones are introduced. In order to maintain reliability when such changes occur and to avoid "split-brain'' behavior, it is essential to ensure proper coordination, e.g., when multiple such changes occur simultaneously. Existing solutions are either centralized, or use strong synchronization algorithms (such as consensus) among the servers to agree on every change in the system. In fact, it was widely believed that reconfigurations require consensus and just like consensus cannot be achieved in asynchronous systems. In this presentation I will refute this belief and present DynaStore, an asynchronous and completely decentralized reconfiguration algorithm for read/write storage.

Cloud storage is another setting where reliability is a challenge. While storing data online becomes increasingly popular, repeated incidents show that clouds fail in a variety of ways. Yet, clients must currently trust cloud providers to handle their information correctly, and do not have tools to verify this. I will present Venus, a system that guarantees data consistency and integrity to clients that collaborate using commodity cloud storage, and alerts clients when the storage is faulty or malicious (e.g., as a result of a software bug, misconfiguration, or a hacker attack). Venus does not require trusted components or changes to the storage provider.

This work is a collaboration with researchers from IBM Research - Zurich and Microsoft Research Silicon Valley.

Dr. Philip M. Merlin Memorial Lecture and Prize Award
Entrepreneurship, innovation, achievements and preserving them

Dr. Orna Berry

Venture Partner, Gemini Israel Funds

Israel GDP has doubled during the 90s and its ICT (Information and Communications Technologies) based industries have six-tupled during the same period. Now the world has adopted innovations and knowledge and means of growth and equality and the state of Israel needs to sharpen its policies in order to retain competitiveness and growth as well as broaden the economic benefit of its might.

Fast CDN (Content Delivery Network)

Eyal Zohar

Tehcnion, Electrical Engineering Department

In this talk we will go through several facts and challenges related to high speed content delivery in client-server model.

The presentation is based on the experience that was gained during the development and implementation of a cache system for large video files over P2P file sharing and HTTP (like YouTube).

Agenda: which protocols are used in the Internet today, disk reading speed, networking with multi-core CPU, scalable CDN, inline processing of heavy traffic, and more.

Continuous Consensus

Prof. Yoram Moses

Tehcnion, Electrical Engineering Department

This talk presents the continuous consensus primitive in synchronous distributed systems. Continuous consensus is a general tool for simultaneous coordination. Continuous consensus is described and its applications are illustrated. We then survey the problem of implementing continuous in a number of different settings. We show cases in which the problem can efficiently be solved, ones in which it becomes intractable, and discuss self-stabilizing solutions to continuous consensus. Continuous consensus is closely related to the state of common knowledge, and this connection is effectively used in its analysis. The talk will be self-contained and will not assume familiarity with knowledge theory or related terms.

This talk describes joint work with Mark Tuttle, Tal Mizrahi, Ezra Hoch and Danny Dolev.

Building Robust Nomadic Wireless Mesh Networks Using Directional Antennas

Dr. Yigal Bejerano

Bell Laboratories, Alcatel-Lucent

Nomadic wireless mesh networks (NWMNs) are currently used for military applications and fast recovery networks. In such systems, wireless routers, termed nodes, are mounted on top of vessels that may change their locations and the nodes are required to establish a broadband and reliable wireless mesh network. For improving network performance, some vendors use directional antennas and the mesh topology comprises of point-to-point (P2P) connections between adjacent nodes. Consequently, the number of P2P connections of a node is upper-bounded by the number of directional radios (and antennas) that it has, which is typically a small constant. This raises the need to build robust (i.e., two-node/edge-connected) mesh networks with a bounded node degree, regardless of the nodes' locations. In the talk, I will describe simple and efficient schemes for constructing robust wireless mesh networks with small node degree.

(Joint work with Qunfeng Dong)

Noninterference in the Presence of Colluding Adversaries

Dr. Kai Engelhardt

School of Computer Science and Engineering, UNSW

Whether adversaries can glean information from a distributed system in a formal sense hinges on the definition of such a system and what can be observed by those adversaries. In the presence of colluding adversaries, the standard definition of noninterference by Goguen and Meseguer and its many variants proposed in the literature fail in a very intuitive sense to capture a simple collusion attack. The crucial difference between what is modelled in those definitions and what we argue needs to be modelled is that teams can observe pomsets as Plotkin and Pratt stated. In this talk we expose what goes wrong in the known approaches and why we should care.

Innovative companies and cloud computing

Dr. Aake Edlund

PDC Center for High Performance Computing, KTH

To maintain a competitive advantage through innovation, companies of today must handle increasingly dynamic environments and increasingly rapid innovation cycles. Cloud computing is addressing many of these challenges, especially the possibility of rapid and cost-efficient prototyping and scaling. Flexibility is the key feature addressed in this talk illustrated with examples from the presenter's own experiences in startups and larger international enterprises.

An online high performance computing service for genetic linkage analysis

Mark Silberstein

Technion, Computer Science Department

In this talk I will describe the algorithms and mechanisms underlying a distributed system for genetic linkage analysis, called Superlink-online. It is a production online system which serves hundreds of geneticists worldwide allowing for faster analysis of genetic data via automatic parallelization and execution on thousands of non-dedicated computers. I will describe the following innovative technologies forming the core of this system.

1. Practical scheduling and execution of embarrassingly parallel Bags of Tasks in multiple non-dedicated computing environments (SC09). Our approach allows for virtualization of multiple grids, clouds and volunteer gids as a single computing platform by building an overlay of execution clients over the physical resources; another component is a generic mechanism for dynamic scheduling policies to reduce the turnaround time in the presence of resource failures and heterogeneity. Our system has executed hundreds of Bags of Tasks with over 9 million jobs during 3 months alone; these have been invoked on 25,000 hosts from the local clusters, the Open Science Grid, EGEE, UW Madison pool and Superlink@Technion community grid.

2. A general technique for designing memory-bound algorithms on GPUs through software-managed cache (ICS08). This technique was successfully applied to the probabilistic network inference yielding an order of magnitude performance improvement versus the performance without such a cache. Overall we achieved up to three orders of magnitude speedup when executing our GPU-based algorithm versus single CPU performance.

3. Coarse- and fine-grained parallel algorithms for the inference in probabilistic networks on large-scale non-dedicated environments and GPUs. We devised and implemented an algorithm suitable for loosly coupled environments with unreliable resources (American Journal of Human Genetics 2006, HPDC06) and adapted it for heterogeneous GPU-CPU supercomputer TSUBAME in Tokyo Tech.

Computer Science Meets Game Theory: Implementing Mediators Robustly

Prof. Joe Halpern

Cornell University, Computer Science Department

The question of whether a problem in a multiagent system that can be solved with a trusted mediator can be solved by just the agents in the system, without the mediator, has attracted a great deal of attention in both computer science (particularly in the cryptography community) and game theory. In cryptography, the focus on the problem has been on secure multiparty computation, where each agent has some private information and the agents want to compute some function of this information without revealing it. This can be done trivially with a trusted mediator: the agents just send their private information to the mediator, who computes the function value and sends it to all of them. Work on multiparty computation conditions under which this can be done without a mediator, under the assumption that at most a certain fraction of the agents are faulty, and do not follow the recommended protocol. By way of contrast, game theory is interested in implementing mediators using what is called "cheap talk", under the assumption that agents are rational. We are interested in combining both strands: We consider games that have (k,t)-robust equilibria when played with a mediator, where an equilibrium is (k,t)-robust if it tolerates deviations by coalitions of rational players of size up to k and deviations by up to t players who can be viewed as faulty (although they can equally well be viewed as rational players with unanticipated utilities). We prove matching upper and lower bounds on the ability to implement such mediators using cheap talk (that is, just allowing communication among the players). The bounds depend on (a) the relationship between k, t and n, the total number of players in the system; (b) whether players know the exact utilities of other players; (c) whether there are broadcast channels or just point-to-point channels; (d) whether cryptography is available; and (e) whether the game has a (k+t)-punishment strategy; that is, a strategy that, if used by all but at most k+t players, guarantees that every player gets a worse outcome than they do with the equilibrium strategy. This talk covers joint work Ittai Abraham, Danny Dolev, and Rica Gonen. No previous background in game theory is assumed.

Internet Routing: Foundations, Challenges and Future Directions

Dr. Michael Schapira

Yale University and UC Berkeley

Over the past two decades there has been exponential growth in the scale and complexity of the Internet. However, the protocols that handle routing on the Internet (e.g., OSPF, BGP) have not changes significantly in comparison and, consequently, often do not cope well with modern-day challenges (bounded computational resources, economically driven manipulations, security attacks, and more). Understanding, ``fixing'' and re-designing Internet routing necessitates taking a principled approach that goes beyond context-specific solutions, bridges theory and systems research, and breaks traditional disciplinary barriers. I shall present conceptual frameworks for addressing today's challenges and novel implementable routing schemes that improve on the existing ones. I shall also discuss the surprising implications of these results for other areas of research: distributed computing, game theory, mechanism design and complexity theory. Finally, I shall outline interesting directions for future work.

Talk slides.

Deep packet inspection for next generation network devices

Dr. Anat Bremler-Barr

Interdisciplinary Center (IDC), Herzliya, Computer Science Dept.

Deep packet inspection (DPI) lies at the core of contemporary Network Intrusion Detection/Prevention Systems and Web Application Firewall. DPI aims to identify various malware (including spam and viruses). DPI consists on either exact string or regular expression pattern matching, which are well-studied problems in Computer Science; nevertheless, all these solutions are not sufficient for current network demands: First, current solutions do not scale in terms of speed, memory and power requirements. Second, non clear-text traffic, such as compressed traffic, becomes a dominant portion of the Internet and is clearly harder to inspect.

In this talk we discuss the current challenges of performing fast DPI and give some overview on the recent advances in hardware that help us cope with these demanding requirements. We present two of our works. In the first work, we propose a novel technique to compress the Deterministic Finite Automaton (DFA), a commonly used paradigm for pattern matching. We show that this compression technique enables performing fast pattern matching with commodity chips that perform fast IP-lookups, thus achieving rate of 10 Gbps. In the second paper, we present a novel technique that accelerates pattern matching of compressed HTTP traffic. Surprisingly, we show that in many situations, pattern matching on compressed data, with the penalty of decompression, is faster than pattern matching on clear-text traffic.

These works appeared in Infocom 2009 and Infocom 2010. Joint work with Yaron Koral (IDC) and David Hay (Columbia University).

DejaView - a Personal Virtual Computer Recorder

Oren Laadan

Columbia University, Computer Science Department

Continuing advances in hardware technology have enabled the proliferation of faster, cheaper, and more capable personal computers. As users interact with the world and their peers through their computers, it is becoming important to archive and later search the information that they have *viewed*. Exponential improvements in processing and storage are not making this problem any easier. Existing state-of-the-art desktop search tools fail to provide a suitable solution.

DejaView is a personal virtual computer recorder that provides a complete record of a desktop computing experience. DejaView continuously records a user's session to provide a complete WYSIWYS (What You See Is What You've Seen) record and enable a user to playback, browse, search and revive records. DejaView combines transparent operating system, display and file system virtualization, with semantic information recorder and a desktop search system, to provide this functionality without any chances to applications, window systems, or operating system kernels. Experimental results show that DejaView provides continuous recording without any user noticeable performance degradation, and is fast enough for interactive use.

Large-Scale Software Dissemination in Stochastic Wireless Networks

Prof. David Starobinski

Boston University

Commercial providers are increasingly permitting third-parties to develop and implement their own applications on wireless devices, ranging from sensors to 3G cellular phones. Accordingly, software dissemination is quickly emerging as a key enabling technology, providing fundamental services such as over-the-air programming and security patching. The lossy nature of the wireless medium joined with the commonly high density of devices hamper efficient accomplishment of this task, however.

In this work, we address the scalability of reliable software dissemination in two ways: (i) we develop and analyze policies harnessing the multi-channel transceiving capabilities of single radio wireless devices, and (ii) we rigorously address the problem of quantifying forward error correction (FEC) redundancy to eliminate control traffic with high probability.

We first analyze the performance of software dissemination in multi-channel, single radio networks. For arbitrary topology networks, we model this problem as a stochastic shortest path optimization and provide an approach to compute the optimal control policy achieving minimum average delay in a finite number of steps using Dijkstra's algorithm. Due to the prohibitive computational complexity of the optimal solution, we devise simple, asymptotically optimal polices for dense networks. Our analysis and simulations reveal that a single radio in each receiver suffices to achieve performance gain directly proportional to the number of channels available.

Next, pairing rateless coding with extreme value theory, we quantify FEC redundancy by analyzing the cumulative distribution function (CDF) of the completion time. We precisely characterize this CDF and demonstrate the existence of a phase transition associated with it. We demonstrate the benefit of accurately quantifying FEC redundancy through real experiments on sensor motes, which reveal drastic reduction in control traffic, energy consumption and overall delay.

Fabric Consolidation - Concepts and Protocols

Dror Goldenberg

Dir. Architecture, Mellanox

Fabric and Server Consolidation is an important trend of today's growing data centers. Consolidation brings a huge value, saving on the infrastructure: equipment cost, power, management, etc. Network speed is an essential factor for consolidating multiple networks over a single fabric and that is addressed by InfiniBand and 40/100G Ethernet. There are many other challenges to provide efficient I/O consolidation solution. These are addressed by various standardization organizations to include IEEE, PCISIG, IBTA and T11 as well as commercial pre standard solutions.

In this talk we will present the various concepts that are applied for efficient consolidation, such as: QoS, partitioning, protocol encapsulation, RDMA, independent flow control, inter-VM packet switching, and will highlight on the corresponding standards and pre-standards such as ETS, FCoE, FCoIB, PFC, VEPA+, RDMAoE, etc.

Finding what You Needed, didn't Know Existed and Couldn't See

Uri Schonfeld

UCLA

Search engines employ huge clusters in an attempt to find the documents they need to best answer their users' queries. Unfortunately, crawling and evaluating the "entire web" is unfeasible. Search engines can identify queries that can likely be improved but do not know how to efficiently and reliably find the pages that would best improve the results. Web sites, on the other hand, have cheap access to their content but do now know what the search engine's needs are. The solution we present in this paper is a new channel of two-way communication channel between the search engine and the web sites. This new channel makes discovering relevant pages more efficient

The WiMAX MAC Layer, markets and applications

Nadav Lavi

Alvarion

WiMAX is a Broadband Wireless Access technology based on the IEEE 802.16 standard that enables the delivery of high-speed personal broadband services to subscribers anytime, anywhere. Operational in both licensed and license-exempt frequencies, WiMAX technology offers flexible and economically viable solutions for different deployment scenarios in urban, suburban and rural environments.

In this talk we will describe the WiMAX MAC layer and network functionalities, and the various WiMAX markets and applications.

MSC8156 Freescale Multicore DSP

Dr. Freddy Gabbay

Freescale

Freescale has been recognized for its leadership and increasing commitment to the broadband wireless industry. The company has been named the award winner for its MSC8156 Multicore DSP as the Best LTE Chip by a premier publication in China that covers the central government's latest strategies of information technology.

The MSC8156 is the industry's highest-performance programmable DSP with its new SC3850 StarCore DSP cores generating 6 GHz - a 2X performance leap over the main competitor's latest multicore DSP. Another advantage is its innovative MAPLE-B acceleration platform. This platform boosts the performance of Forward Error Correction and Fourier Transforms required in different wireless standards while offloading DSP cores and eliminating the need for external FPGA to perform these tasks.

Freescale is the first to launch a device supporting multiple broadband wireless standards such as TD-SCDMA, TDD-LTE, FDD-LTE, WiMAX and WCDMA. The device enables smooth migration among standards and is designed to dramatically advance the capabilities of wireless broadband base station equipment.

The Mulitcore Streaming Framework

Uzi Shvadron

IBM Research, Haifa

Next generation computing system are going to be significantly different than the current systems. This is due to two main reasons: Power consumption restrictions - higher computing rate requires more parallel processors with scaled power consumption The memory wall problem - shared memory for multiple processors is not a suitable option due to access delays of large NUMA memory systems As a result future computing systems are going to have up to thousands of very small, specialized, heterogenous cores with a distributed memory system that provides small amount of local memory for each core. This imposed design creates significant programmability challenges The Mulitcore Streaming Framework (MSF) is an implementation of a programming model for parallel platforms. The main target of the MSF design is to ease the task of parallel programming. Programming for a multicore environment must have inherent data and code transfers between various processors. In many cases the management of these transfers are left to the programmer, this make parallel programming difficult. MSF provides an abstraction of these transfers that releases the programmers from handling the parallel execution and the data transfers that are associated with the execution.

Programming using the MSF is based on a concept of data streaming between tasks. Nevertheless, MSF can be used for none-streaming type of applications as well. By using the MSF API the programmer provides a set of tasks and the data dependency connections graph between them. Thereafter MSF is capable to execute the tasks as long as data is available for them. Tasks are independent components of code that may process large amount of input data and produce large amount of output data using the provided API. A task can run on any of the available processors in the multicore processor. MSF provides and architecture independent interface. It can be implemented on various systems with shared or distributed memories, and can be scaled to a multiprocessor systems.

The well structured programming model of MSF allows the use of MSF by compilers that rely on the provided runtime code to execute programs that were programmed for sequential programs. Initial results in these area have been achieved.

Talk slides.

Group Scalability in Distributed Systems

Dr. Ymir Vigfusson

IBM Research, Haifa

We address shortcomings of two important group communication paradigms, IP Multicast and gossip based message dissemination, both of which have scalability issues when the number of groups grows.

First, we propose a transparent and backward-compatible layer called Dr. Multicast to allow data center administrators to enable IPMC for large numbers of groups without causing scalability issues. Dr. Multicast optimizes IPMC resources by grouping together similar groups in terms of membership to minimize redundant transmissions as well as the cost of filtering unwanted messages.

Second, we argue that when nodes belong to multiple groups, gossip based communication loses its appealing property of using a fixed amount of bandwidth. We propose a platform called GO (Gossip Objects) that bounds each node's bandwidth use to a customizable limit, prohibiting applications from joining groups that would cause the limit to be exceeded. We make the observation that gossip rumors tend to be small, and propose a utility-based heuristic to stack rumors into packets to optimize delivery speed, with rumors sometimes traveling through indirect paths.

Features joint work with Hussam Abu-Libdeh, Mahesh Balakrishnan, Ken Birman, Robert Burgess, Gregory Chockler, Qi Huang, Jure Leskovec, Haoyuan Li, Deepak Nataraj and Yoav Tock.

Algebraic Gossip via EXCHANGE: Analytical and Simulation Results

Dr. Chen Avin

Communication Systems Engineering Department, Ben Gurion University of the Negev

In this work we study the stopping times of gossip algorithms for network coding. We analyze Algebraic gossip (i.e., random linear coding) and consider three gossip algorithms for information spreading Pull, Push and Exchange. While traditionally Algebraic gossip protocols used Pull or Push, we prove that using the Exchange algorithm can be unboundedly better. The stopping time of Algebraic gossip is known to be linear for the complete graph, but the question of determine a tight upper bound for general graphs is still open. We take a major step in solving this question, and prove a linear tight upper bound for bounded degree graphs and a tight lower bound of n^2 for general graphs.

Our proofs uses a new method that relies on Jackson's queueing theorem to analyze the stopping time of network coding, and the technique is likely to turn useful for future research.

In addition, we compare algebraic gossip to the average computation task via Exchange and show that there are graphs for which algebraic gossip can be unboundedly faster.

Joint work with: Michael Borokhovich and Zvi Lotker.

Self-Stabilizing and Byzantine Fault Tolerance

Ezra Hoch

School of Computer Science and Engineering, The Hebrew University of Jerusaelm

In this talk I will discuss a few results that combine self-stabilizing and Byzantine fault tolerance. I will concentrate on the simpler model of synchronous message passing, and discuss the major tools that are used to achieve the results.

The three main results I will discuss are:
1. Self-stabilizing Byzantine Digital Clock Synchronization (SSS 06)
2. On Self-stabilizing Synchronous Actions Despite Byzantine Attacks (DISC 07)
3. Fast Self-stabilizing Byzantine Tolerant Digital Clock Synchronization (PODC 08)

No Need to Constrain Many-Core Parallel Programming

Prof. Uzi Vishkin

University of Maryland Institute for Advanced Computer Studies

The transition in mainstream computer science from serial to parallel programming for many-core on-chip computing offers parallel computing research the wonderful impact opportunity it had sought all along. However, such transition is a potential trauma for programmers who need to change the basic ways in which they conduct their daily work. The long experience with multi-chip parallel machines only adds to the apprehension of today's programmers. Many people who tried (or deliberated trying) to program these multi-chip machines consider their programming 'as intimidating and time consuming as programming in assembly language' (--2003 NSF Cyberinfrastructure Blue Ribbon Committee), and have literally walked away. Programmers simply did not want to deal with the constraint of programming for locality in order to extract the performance that these machines promise. Consequently, their use fell far short of historical expectations. Now, with the emerging many-core computers, the foremost challenge is ensuring that mainstream computing is not railroaded into another major disappointment. Limiting many-core parallel programming to more or less the same programming approaches that dominated parallel machines could again: (i) repel programmers; (ii) reduce productivity of those programmers who hold on: getting the performance promise requires high development-time and leads to more error-prone code; (iii) raise by too much the minimal professional development stage for introducing programmers to parallel programming, reducing further the pool of potential programmers; and overall (iv) fail to meet expectations regarding the use of parallel computing; only this time for many-cores.

The talk will overview a hardware-based PRAM-On-Chip vision that seeks to rebuild parallel computing from the ground up. Grounded in the richest and easiest known theory of parallel algorithms, known as PRAM, where the programmer only needs to identify at each step operations that can be executed concurrently, an on-chip architecture that scales to thousands of processors on chip called XMT (for explicit multi-threading) was introduced. Significant hardware and software prototyping of XMT will be reported, including a 64-processor FPGA-based machine and two ASIC chips fabricated using 90nm CMOS technology, as well as strong speedups on applications. By having XMT programming taught at various levels from rising 6th graders to graduate students, we developed evidence that the stage at which parallel programming can be taught is earlier than demonstrated by other approaches. For example, students in a freshman class were able to program 3 parallel sorting algorithms. Software release of the XMT environment can be downloaded to any standard PC platform along with extensive teaching materials, such as video-recorded lectures of a one-day tutorial to high school students and a full-semester graduate class, class notes and programming assignments. Preliminary thoughts on encapsulating XMT into a hardware-enhanced programmer's workflow will also be presented and the prospects for incorporating it as an add-on into some other many-core designs be discussed.

Lessons from Winning the Grand Prize at the Netflix Competition

Dr. Yehuda Koren

Sr. Research Scientist, Yahoo! Research

The collaborative filtering approach to recommender systems predicts user preferences for products or services by learning past user-item relationships. Their significant economic implications made collaborative filtering techniques play an important role at known e-tailers such as Amazon and Netflix. This field enjoyed a surge of interest since October 2006, when the Netflix Prize competition was commenced. Netflix released a dataset containing 100 million anonymous movie ratings and challenged the research community to develop algorithms that could beat the accuracy of its recommendation system, Cinematch. In this talk I will survey the competition together with some of the principles and algorithms, which have led us to winning the Grand Prize in the competition.

Med-Hoc-Net 2009 Keynote: Vehicular Urban Sensing: Dissemination and Retrieval

Prof. Mario Gerla

UCLA, Computer Science Department

There has been growing interest in vehicle to vehicle communications for a broad range of applications ranging from safe driving to content distribution, advertising, commerce and games. One emerging application is urban sensing. Vehicles monitor the environment, classify the events, e.g., license plates, pollution readings, etc. and exchange metadata with neighbors in a peer-to-peer fashion, creating a distributed index from which mobile users can extract different views. For instance, the Department of Transportation captures traffic statistics; the Department of Health monitors pollutants; and Law Enforcement Agents investigate crimes. Mobile, vehicular sensing differs significantly from conventional wireless sensing. Vehicles have no strict limits on battery life, processing power and storage capabilities. Moreover they can generate enormous volumes of data, making conventional sensor data collection inadequate. In this talk we first review popular V2V applications and then introduce MobEyes, a middleware solution that diffuses data summaries to create a distributed index of the sensed data. We discuss the challenges of designing and maintain such a system, from information dissemination to harvesting, routing and privacy.

Med-Hoc-Net 2009 Opening Talk: Cognitive Networks - Throughput, Delay Bounds and Routing Issues

Prof. Luigi Fratta

Politecnico di Milano, Dipartimento di Elettronica e Informazione

Cognitive Radio Networks (CRNs) are composed of frequency-agile radio devices that allow licensed (primary) and unlicensed (secondary) users to coexist, where secondary users opportunistically access channels without interfering with the operation of primary ones. From the perspective of secondary users, spectrum availability is a time varying network resource over which multi-hop end-to-end connections must be maintained.

Analytical bounds on throughput and transmission delay of secondary users under different assumptions on secondary and primary users traffic statistics in a single channel scenario will be presented.

Then it will be discussed the problem of routing secondary user flows in a CRN with the aim of characterizing optimal sequences of routes over which a secondary flow is maintained. The optimality is defined according to a novel metric that considers the maintenance cost of a route as channels and/or links must be switched due to the primary user activity. Different from the traditional routing problem, the proposed approach considers subsequent path selections. The problem can be formulated as an integer programming optimization model and shown to be of polynomial time complexity in case of full knowledge of primary user activity. The use of heuristic algorithms, to solve the minimum maintenance cost routing problem when information on primary user activity is not complete, will be discussed. Some numerical results will allow to assess the optimality gap of a proposed heuristic routing algorithm.

External Mining of Search Query logs

Maxim Gurevich

Technion, Electrical Engineering Faculty

Search query logs are valuable data sources that are kept confidential by search engines, in order to protect their users' privacy. Some search engines disclose aggregate statistics about queries via services, like Google Trends and Google Trends for Websites. The information provided by these services, however, is obfuscated, non-repeatable, and partial. For example, statistics for medium to low volume queries and sites are not readily available. In this talk I will describe algorithms for "external" mining of search query logs. Our algorithms can be used to estimate the popularity of queries in the log and the amount of impressions web sites receive from search results. The algorithms use only public search engine services, like the web search service and the query suggestion service, and thus do not require privileged access to confidential search engine data sources. In addition, the algorithms use modest resources, and hence can be used by anyone to gather statistics about any query and/or any web site. Our algorithms rely on tools from information retrieval (keyword extraction), statistics (importance sampling), and databases (tree volume estimation).

The talk will be self-contained.

Based on joint work with Ziv Bar-Yossef.

ETNA architecture for Inter Domain Transport Network

David Berechya

Nokia Siemens

Inter Domain Transport Network is an architecture for automatic inter domain provisioning of transport services. ETNA emphasizes and analyses the case of Inter Carrier, i.e. different domains operated by different carriers. This innovative method developed by ETNA enables efficient and low cost pan-European and even world wide transport services. Today, provisioning of inter carrier transport involves time-consuming manual intervention, a process that lasts days or even weeks. Automatic inter carrier provisioning will shorten the provisioning period dramatically and will decrease the OPEX involved significantly. The ETNA Inter domain transport concept works for any domain technology like IEEE based transport (PBB, PBB-TE), MPLS, MPLS-TP etc., this concept considers the fact that the pan European transport is composed of several transport technologies operated by different carriers.

Lower bounds on the Complexity of Set-Agreement in Partially Synchronous Systems

Dr. Corentin Travers

Technion, Computer Science Department

Set agreement is a fundamental problem in distributed computing in which processes collectively choose a small subset of values from a larger set of proposals. The impossibility of fault-tolerant set agreement in asynchronous networks is one of the seminal results in distributed computing. In synchronous networks, too, the complexity of set agreement has been a signifcant research challenge that has now been resolved. Real systems, however, are neither purely synchronous nor purely asynchronous. Rather, they tend to alternate between periods of synchrony and periods of asynchrony. Nothing specific is known about the complexity of set agreement in such a "partially synchronous" setting.

In this paper, we address this challenge, presenting the first (asymptotically) tight bound on the complexity of set agreement in such systems. While doing so, we highlight close connections between the basic models of distributed computation: synchronous, partially synchronous, and asynchronous. We introduce a technique for simulating, in a fault-prone asynchronous shared memory, executions of an asynchronous and failure-prone message-passing system in which some fragments appear synchronous to some processes. We use this simulation technique to derive a lower bound on the round complexity of set agreement in a partially synchronous system by a reduction from asynchronous wait-free set agreement.

Specifically, we show that every set agreement protocol requires at least floor(t/k) + 2 synchronous rounds to decide. We present an (asymptotically) matching algorithm that relies on a distributed asynchrony detection mechanism to decide as soon as possible during periods of synchrony, that is, in floor(t/k) + 4 synchronous rounds. From these two results, we derive the size of the minimal window of synchrony needed to solve set agreement. By relating synchronous, asynchronous and partially synchronous environments, our simulation technique is of independent interest. In particular, it allows us to re-derive and extend existing lower bounds on the complexity of synchronous early-deciding set agreement.

joint work with Dan Alistarh, Seth Gilbert and Rachid Guerraoui EPFL

TCP Starvation in Routers

Alex Shpiner

Technion, Electrical Engineering Faculty

Starvation can have a dramatic impact on application performance. To avoid it, network-based applications often rely on TCP, a reliable transport-layer protocol that is defined to adjust itself to networks with variable environment, like link capacities, propagation times and buffer sizes. Many researchers have analyzed this protocol and proved its capabilities using ideal router models in global networks. However, we find that both real routers and datacenter networks may lead to starvation and unfairness between the TCP flows.

In this talk, we first analyze the interactions of user-based congestion control algorithms and router-based switch scheduling algorithms. Previous papers neglected or mitigated these interactions, and typically found that flow rates reach a fair equilibrium. On the contrary, we show that these interactions can lead to extreme unfairness with temporary flow starvation, as well as to large rate oscillations. For instance, we prove that this is the case for the MWM switch scheduling algorithm, even with a single router output and basic TCP flows. In addition, we fully characterize the network dynamics for both these switch scheduling algorithms.

In the second part we talk about using TCP in the network architecture of the datacenters. Datacenters are a challenging environment for TCP flows. They are characterized by very short round trip times and a large number of flows. Thus, their short links are not long enough to contain packets from all the flows. As a result, we show that TCP-based datacenter networks can suffer from high unfairness and starvation. We present a novel algorithm called HCF (Hashed Credits Fair) which is simple to implement. We show by simulations, that this algorithm improves the fairness and reduces the starvation, yet keeps a maximal possible throughput.

M.Sc. research under the supervision of Dr. Isaac Keslassy.

Can IP Networks be merged with Optical Networks?

Dr. Ori Gerstel

CISCO

Core IP networks have been using optical wavelength multiplexing (DWDM) technology in most networks across the globe. As bandwidth needs continue to increase, the limits of electrical processing in routers in reached and the simple usage of optics by routers no longer suffices. As a result, more dynamic optical networking must be deployed to exploit the vast scale that optics provides. However, such a technology comes with many challenges that must be first overcome. This talk will cover the current evolution from static point-to-point DWDM networks to a fully switched network that better serves the IP layer. We will then propose a possible next phase in this evolution - from fixed usage of optical spectrum to dynamic usage of spectrum.

O(log N / log log N) RMRs Randomized Mutual Exclusion

Dr. Danny Hendler

Ben-Gurion University, Department of Computer Science

Mutual exclusion is a fundamental distributed coordination problem. Shared-memory mutual exclusion research focuses on local-spin algorithms and uses the remote memory references (RMRs) metric. An RMR is a shared memory access that cannot be served from a process' local cache.

A recent proof by Attiya, Hendler and Woelfel established an \Omega(log N) lower bound on the number of RMRs incurred by processes as they enter and exit the critical section, matching an upper bound by Yang and Anderson. Both these bounds apply for N-process algorithms that only use read and write operations.

The lower bound of Attiya et al. only holds for deterministic algorithms, however; the question of whether randomized mutual exclusion algorithms, using reads and writes only, can achieve sub-logarithmic expected RMR complexity remained open. In this talk, I will present recent work that answers this question in the affirmative.

We present two strong-adversary randomized local-spin mutual exclusion algorithms. In both algorithms, processes incur O(log N / log log N) expected RMRs per critical section passage. Our first algorithm has sub-optimal worst-case RMR complexity of O( (log N / log log N)^2 ). Our second algorithm is a variant of the first that can be combined with a deterministic algorithm, such as that of Anderson and Yang, to obtain O(log N) worst-case RMR complexity. The combined algorithm thus achieves sub-logarithmic expected RMR complexity while maintaining optimal worst-case RMR complexity.

The talk will be self-contained and no familiarity with distributed computing theory will be assumed.

This is joint work with Philipp Woelfel.

Cryptography and security, from theory to practice

Dr. Benny Pinkas

Haifa University, Department of Computer Science

Research in cryptography and security has an incredible potential for fruitful interaction between theory and practice, as was demonstrated by the very successful deployment of public key technology. On the other hand, there has been much less interaction between theory and practice in other areas of cryptographic research. For instance, cryptographers have devised procedures for performing many seemingly impossible tasks, using zero-knowledge proofs and protocols for secure multi-party computation, but none of these procedures is in daily use.

This talk will describe two research efforts which aim to close the gap between the theory and practice of cryptography. The first is in secure multi-party computation, a technology which enables a set of untrusting parties to compute any function of their private inputs while revealing nothing but the result of the function. We will describe recent advances in implementing secure computation, involving both theoretical research and implementation experiments.

The second area of research is an investigation of the security of the pseudo-random generators of operating systems, which is crucial for the security of almost any security application. We examined the pseudo-random number generators of the Linux and Windows operating systems, whose details were never revealed before our work. In both cases we presented weaknesses and attacks, with the goal of motivating manufacturers to improve the security of these elements.

Dynamics of Peer-to-Peer Networks, or Who is Going to be The Next Pop Star?

Prof. Yuval Shavitt

Tel Aviv University, School of Electrical Engineering

P2P file-sharing applications are quickly being adopted by a wider and more mainstream audience. There is much to be learned from keyword searches users perform in order to retrieve content from these networks.

This talk presents an unprecedented large-scale (both in time and volume) measurement study of search terms in the modern Gnutella network. We analyzed both static snapshots of the Gnutella networks, as well as the dynamics of the network over time. In particular, we show how analysis of the query string over time and space (geography) can help us detect with high success rate (over 20% on average and about 50% at peak) emerging artists in the US.

The talk is based on two papers co-authored with Tomer Tankel, Noam Koenigstein, and Adam Shaked-Gish.

The second paper was recently receiving large media exposure both in Israel (Yediot Aharonot, glz, Channel 2) and abroad (Popular Science, The New Scientist, Daily Telegraph, Seed Magazine, MSNBC and more).

Approximate Shared-Memory Counting Despite a Strong Adversary

Keren Censor

Technion, Computer Science Department

Most randomized consensus algorithms embed a shared-coin algorithm that allows the processes to flip a coin, with constant probability for all processes agreeing on each of the outcomes. To get good guarantees of the shared coin, these implementations require the processes to count.

A new randomized asynchronous shared-memory data structure is given for implementing an approximate counter that can be incremented up to n times. For any fixed epsilon, the counter achieves a relative error of delta with high probability, at the cost of O(((1/delta) log n)^{O(1/epsilon)}) register operations per increment and O(n^{4/5+epsilon}((1/delta) log n)^{O(1/epsilon)}) register operations per read. The counter combines randomized sampling for estimating large values with an expander for estimating small values. This is the first sublinear solution to this problem that works despite a strong adversary scheduler that can observe internal states of processes.

An application of the improved counter is an improved protocol for solving randomized shared-memory consensus, which reduces the best previously known individual work complexity from O(n log n) to an optimal O(n), resolving one of the last remaining open problems concerning consensus in this model.

The talk is based on joint work with Hagit Attiya and James Aspnes [PODC 2008, SODA 2009].

To Peer or not to Peer? That's the question!

Prof. Fernando Kuipers

Delft University of Technology, Network Architectures and Services group

P2P technology has been a popular means of sharing files over the Internet. With the increase in popularity of video-based services, the question emerges whether P2P technology will also become a key technology for delivering real-time video services. These services can be delivered (1) via a dedicated network that is under full control by a service provider, or (2) via a Peer-to-Peer protocol over the Internet, which means less control but better scalability. Many operators are currently struggling with the question whether to adopt P2P technology or not. An important criterion in this decision process is the quality of the services as experienced by their end-users. In this talk we will provide more insight into this matter by studying the Quality of Experience of a P2PTV application called SopCast.

Mitigating Congestion in High-Speed Interconnects for Computer Clusters

Vladimir Zdornov

The Technion, EE faculty

In large computer clusters such as nearly all current super computers, congestion is an inherent problem, which arises due to oversubscription of communication resources. Moreover, the limited number of buffers results in rapid "congestion spreading", whereby communication along paths that do not traverse congested links is also severely degraded.

Cluster interconnection networks constitute a managed environment, in which the behavior of all elements can be defined to implement new protocols without jeopardizing the interoperability. This property, combined with very low delays and reliable communication, creates an opportunity for application of sophisticated control mechanisms aimed to avoid damage caused by congestion-related phenomena.

In this work, we propose novel mechanisms for adaptive routing and rate control, and study them under performance goals specific to cluster networks.

Our adaptive routing uses virtual circuits to guarantee in-order packet delivery. The path setup process is performed by switches locally. Importantly, we avoid blocking and backtracking. The scheme is shown to reduce the maximum contention by up to 50% in slightly enriched fat tree topology, for random permutation traffic.

Unlike most current rate control schemes such as those used in TCP and in InfiniBand, our proposed rate control schemes rely on explicit rate calculation. We formulate three different performance goals and present distributed algorithms that achieve them. Simulation results of synthetic benchmarks demonstrate the algorithms to have significant impact on the relevant measures. In addition, we prove tight theoretical bounds that reflect the behavior of the algorithms under unsuitable performance goals (among the three defined).

M.Sc. research under the supervision of Prof. Yitzhak Birk

Toward Task Completion Assistance in Web Information Retrieval

Dr. Ronny Lempel

Director of Yahoo! Research, Haifa

This talk will describe some of the challenges currently addressed by Web Information Retrieval systems, namely search engines. The first generation of search engines closely resembled classic IR systems in their goal to return relevant documents to a user's query. Those systems relied mostly on on-page contents. The second generation of search engines added the links between Web pages to the mix, and differentiated between several types of information needs. Today's engines tap huge amounts of user generated content, and focus on helping users to complete tasks. This involves both assisting users to break down their tasks into sub-tasks, as well as interpretation, aggregation and integration of diverse content that allows users to more readily digest complex information. The talk will explore some of the search assistance tools available today and will highlight some of the technical challenges in their development.

Audio Video Services in Home Network: Overview of the MoCA protocol and 802.1 AVB

Dr. Philippe Klein

Associate Technical Director, Broadcom

MoCA is the standard for home entertainment networks over coax and allows for the distribution of multiple HD video streams, multi-room gaming and whole-home DVR services in the home. Broadcom is a board member of the MoCA alliance and an active contributor to the MoCa specifications.

The IEEE 802.1 Audio/Video Bridging Task Group charter is to provide the specifications that will allow end to end QoS and time-synchronized low latency streaming services through 802 (802.3, 802.11) and "Coordinated Shared" networks. Broadcom chairs the IEEE 802.1 AVB TG and is an active contributor to its specifications.

http://www.mocalliance.org
http://www.ieee802.org/1/pages/avbridges.html

Startup - Israel's National Sport

Ofir Zohar

VP XIV, IBM

"In the talk 'Startup - Israel's National Sport' I will talk about the principles of building a startup and making a successful exit while telling the story of XIV and using analogies from the world of sports".

Ofir Zohar is the ex-CEO of XIV - a startup which was acquired by IBM in December 2007 for $300 million. XIV develops high-end enterprise storage services.

http://it.themarker.com/tmit/article/4498

FPGA Technology

Udi Landen

VP of Software and IP Engineering, Altera

• Silicon Technology Evolution
• Why Use an FPGA?
• Altera Overview
• Architecting FPGA Architectures and CAD Tools
• Leveraging FPGA Technology for Teaching
• Future Directions

Rate and Delay Controlled Core Networks: A Theory and a WAN Testbed Demonstration

Dr. Zvi Rosberg

CSIRO ICT Centre, Australia

Growing demand for streaming, voice and interactive gaming applications emphasize the importance of quality of service (QoS) provisioning in the Internet; particularly the need for maximum end-to-end delay and jitter guarantee as well as for packet policing at the network edge. Current methods of QoS provisioning have either scalability concern (IntServ) or cannot guarantee end-to-end delay and jitter with acceptable packet loss, unless bandwidth is over-provisioned (DiffServ). Furthermore, they cannot adapt the influx traffic rate at the network edge so as to protect the QoS of running applications.

I will present three combined rate and end-to-end delay controls and discuss their stability properties in a fluid network model. I will also present the implementation in network routers of one of the controls and demonstrate its stability and convergence in our WAN testbed.

To further demonstrate that a combined rate and end-to-end delay control can address the current DiffServ issues, we use the control as a building block for several shell protocols around the DiffServ services. The advantage over the native DiffServ in our WAN testbed will also be presented using real video/voice/data applications demonstrating the vitality of our solution.

RFIDs and Swarms security schemes

Prof. Shlomi Dolev

The Computer Science Department, Ben Gurion University

Two recent works on security in the RFID and swarm young domains will be described.

For RFIDs: We consider repeated communication sessions between a RFID Tag (e.g., Radio Frequency Identification, RFID Tag) and a RFID Verifier. A proactive information theoretic security scheme is proposed. The scheme is based on the assumption that the information exchanged during at least one of every n successive communication sessions is not exposed to an adversary. The Tag and the Verifier maintain a vector of n entries that is repeatedly refreshed by pairwise xoring entries, with a new vector of n entries that is randomly chosen by the Tag and sent to the Verifier as a part of each communication session. A computational secure scheme which is based on the information theoretic secure scheme is used to ensure that even in the case that the adversary listens to all the information exchanges, the communication between the Tag and the Verifier is secure.

For Swarms: Secret sharing is a fundamental cryptographic task. Motivated by the virtual automata abstraction and swarm computing, we investigate an extension of the k-secret sharing scheme, in which the secret shares are changed on the fly, independently and without (internal) communication, as a reaction to a global external trigger. The changes are made while maintaining the requirement that k or more secret shares may reconstruct the secret and no k - 1 or fewer can do so. The application considered is a swarm of mobile processes, each maintaining a share of the secret which may change according to common outside inputs, e.g., inputs received by sensors attached to the process. The proposed schemes support addition and removal of processes from the swarm, as well as corruption of a small portion of the processes in the swarm.

The talk is based on joint works with Marina Kopeetsky, Adi Shamir, Limor Lahiani and Moti Yung

A Secure Cryptographic Token Interface

Dr. Christian Cachin

IBM Zurich Research Laboratory

Cryptographic keys must be protected from exposure. In real-world applications, they are often guarded by cryptographic tokens that employ sophisticated hardware-security measures. Several logical attacks on the key management operations of cryptographic tokens have been reported in the past, which allowed to expose keys merely by exploiting the token API in unexpected ways.

This talk presents a novel, provably secure, cryptographic token interface that supports multiple users, implements symmetric cryptosystems and public-key schemes, and provides operations for key generation, encryption, authentication, and key wrapping. The token interface allows only the most important operations found in real-world token APIs; while flexible to be of practical use, it is restricted enough so that it does not expose any key to a user without sufficient privileges. An emulation of the security policy in the industry-standard PKCS \#11 interface is demonstrated.

Based on joint work with Nishanth Chandran.

Portably Preventing File Race Attacks with User-Mode Path Resolution

Dr. Dan Tsafrir

IBM T. J. Watson Research Center

The filesystem API of contemporary systems exposes programs to TOCTTOU (time of check to time of use) race-condition vulnerabilities, which occur between pairs of check/use system calls that involve a name of a file. Existing solutions either help programmers to detect such races (by pinpointing their location) or prevent them altogether (by altering the operating system). But the latter alternative is not prevalent, and the former is just the first step: programmers must still address TOCTTOU flaws within the limits of the existing API with which several important tasks cannot be safely accomplished in a portable straightforward manner. The recent "filesystem maze" attack further worsens the problem by allowing adversaries to deterministically win races and thus refuting the common perception that the risk is small. In the face of this threat, we develop a new algorithm that allows programmers to effectively aggregate a vulnerable pair of distinct system calls into a single operation that is executed "atomically". This is achieved by emulating one kernel functionality in user mode: the filepath resolution. The surprisingly simple resulting algorithm constitutes a portable solution to a large class of TOCTTOU vulnerabilities, without requiring modifications to the underlying operating system.

Joint work with Tomer Hertz (Microsoft Research), David Wagner (Berkeley), and Dilma Da Silva (IBM T.J. Watson Research Center).Based on http://www.usenix.org/events/fast08/tech/tsafrir.html

USENIX File & Storage Technologies (FAST'08). Awarded best paper.

Robust and efficient TCAM-based classification

Dr. David Hay

The Electronic Department, Politecnico di Torino

Ternary content-addressable memory (TCAM) devices are increasingly used for performing high-speed packet classification. A TCAM consists of an associative memory that compares a search key in parallel against all entries and thus provides high throughput.

In this talk we tackle two challenges related to these devices.

In the first part, we will consider the representation of rules that contains range fields (e.g. source or destination ports). Prior art algorithms typically represent each such rule by multiple TCAM entries, which results in a range expansion that dramatically reduce TCAM utilization. We present a novel scheme for constructing efficient representations of range rules, making use of extra bits, available in each TCAM entry.By extensive comparative analysis on real-life classification databases, we establish that our scheme reduces the number of redundant TCAM entries caused by range rules by more than 60% as compared with best range-encoding prior art.

In the second part, we present PEDS, a novel parallel error detection scheme that locates the erroneous entries in a TCAM device. PEDS is based on applying an error-detection code to each TCAM entry, and utilizing the parallel capabilities of the TCAM, by simultaneously checking the correctness of multiple TCAM entries. A key feature of PEDS is that the number of TCAM lookup operations required to locate all errors depends on the number of symbols per entry rather than the (orders-of-magnitude larger) number of TCAM entries. PEDS allows flexible and dynamic selection of trade-off points between robustness, space complexity, and number of lookups.

These are joint works with Anat Bremler-Bar (IDC, Israel), Danny Hendler (BGU, Israel) and Ronny Roth (Technion, Israel), and are supported by a Cisco grant.

Improved Distributed Approximate Matching

Prof. Boaz Patt-Shamir

Department of Electrical Engineering, Tel Aviv University

We present improved algorithms for finding approximately optimal matchings in both weighted and unweighted graphs. For unweighted graphs, we give an algorithm providing (1-epsilon)-approximation in O(log n) time for any constant epsilon>0. This result improves on the classical 1/2-approximation due to Israeli and Itai. As a by-product, we also provide an improved algorithm for unweighted matchings in bipartite graphs. In the context of weighted graphs, we give an algorithm which provides (1/2-epsilon)-approximation in general graphs in O(log n) time. The latter result improves on the known (1/4-epsilon)-approximation in O(log n) time, or (1/2-epsilon)-approximation in O(log^2 n) time.

joint work with Zvi Lotker (Ben Gorion U.) and Seth Pettie (U. Michigan)

Establishing Multiple Survivable Connections

Michael Keslassy

The Technion, EE faculty

With the increasing use of telecommunication networks, the ability of a network to recover from failures becomes a crucial requirement. In particular, link failures can be catastrophic in networks that are capable of transmitting very large amounts of data on each link. Accordingly, various routing schemes have been proposed for supporting network survivability. Such schemes handle link failures by rerouting connections through alternative paths. Survivable networks have been studied extensively in the context of optical wavelength division multiplexing networks (WDM) and multiprotocol label switching (MPLS) protection.

We consider in this talk the establishment of multiple connections in survivable networks, where each connection is allocated with a working (primary) path and a protection (backup) path. While many optimal solutions have been found for the establishment of a single connection, only heuristics have been proposed for the multi-connection case.

Our talk will start with the basic, but yet already complex case where two connections are to be established. A differentiation will be made between online and offline frameworks, and between full and partial reliability. We will then extend our analysis to a K connection problem, where K>2 is a fixed number and each connection needs to be fully reliable. For online and offline variants, optimal solutions of polynomial complexity will be presented. Finally, the intractability of some extensions of the problem will be shown.

MSc. research under the supervision of Prof. Ariel Orda.

Parallel Job Scheduling and Workloads

Prof. Dror Feitelson

School of Computer Science and Engineering, The Hebrew University of Jerusalem

Parallel job scheduling is concerned with the scheduling of parallel jobs -- jobs composed of multiple interacting processes -- on large-scale parallel machines or clusters. New scheduling schemes are typically evaluated using simulations. This has to be done using representative workloads, that have similar characteristics to the workloads on real production parallel systems. Many studies therefore use actual workload traces from production systems to drive the simulations. However, using such traces may lead to unforeseen problems. This talk will start with a very simple approach to parallel job scheduling, called backfilling, which is in wide use today. Backfilling requires users to provide runtime estimates for submitted jobs, so that the scheduler will be able to plan its actions. Surprisingly, the results of performance evaluations are very sensitive to models of how such estimates are generated. We'll then review the importance of feedback in workloads, where the submittal of additional jobs depends on the performance of the system when servicing previous jobs. Regrettably, feedback data is not included explicitly in workload traces, so we need models of user behavior to extract it. Modeling user behavior such as feedback and daily cycles of activity is important not only for evaluations, but also as an enabler of novel approaches. Finally, we'll demonstrate the need to clean workload data before it is used in evaluations.