Gateways for Mobile Routing in Tactical Network Deployments (2009)
R. G. Cole, L. Benmohamed, B. Doshi, Baruch Awerbuch, Derya Cansever
a Network Centric Warfighting (NCW) capability. Key to the deployment of NCW capabilities is the development of scalable networks supporting end user mobility. Initial network deployments operate...
A Time-Optimal Self-Stabilizing Synchronizer Using a Phase Clock (2009)
Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-shamir, George Varghese
Abstract—A synchronizer with a phase counter (sometimes called asynchronous phase clock) is an asynchronous distributed algorithm, where each node maintains a local “pulse counter ” that...
A Jamming-Resistant MAC Protocol for Single-Hop Wireless Networks ABSTRACT (2009)
In this paper we consider the problem of designing a medium access control (MAC) protocol for single-hop wireless networks that is provably robust against adaptive adversarial jamming. The wireless...
Distributed control for PARIS Extended Abstract (2009)
Baruch Awerbuch, Israel Cidont, Inder Gopalt, Marc Kaplan, Shay Kuttent
We describe the control protocols of the PARIS experi-mental network. This high bandwidth network for inte-grated communication (data, voice, video) ia currently operational as a laboratory...
Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-shamir, George Varghese
A synchronizer with a phase counter (sometimes called asynchronous phase clock) is an asynchronous distributed algorithm, where each node maintains a local ‘pulse counter ’ that simulates the...
Baruch Awerbuch, Boaz Patt-shamir, David Peleg
We consider a simple model for reputation systems such as the one used by eBay. In our model there are n players, some of which may exhibit arbitrarily malicious (Byzantine) behavior, and there are m...
Improved Recommendation Systems ∗ Extended Abstract (2009)
Baruch Awerbuch, Boaz Patt-shamir, David Peleg, Mark Tuttle
1
ABSTRACT Online Collaborative Filtering with Nearly Optimal Dynamic Regret (2009)
Baruch Awerbuch, Thomas P. Hayes
We consider a model for sequential online decision-making by many diverse agents. On each day, each agent makes a decision, and pays a penalty if it is a mistake. Obviously, it would be good for...
Baruch Awerbuch, David Holmer, Cristina Nita-rotaru
Ah hoc networks offer increased coverage by using multi-hop communication. This architecture makes services more vulnerable to internal attacks coming from compromised nodes that behave arbitrarily...
Stateless Near Optimal Flow Control with Poly-logarithmic Convergence (2009)
Abstract. We design completely local, stateless, and self-stabilizing flow control mechanism to be executed by “greedy ” agents associated with individual flow paths. Our mechanism is very...
ABSTRACT Stateless Distributed Gradient Descent for Positive Linear Programs (2008)
We develop a framework of distributed and stateless solutions for packing and covering linear programs, which are solved by multiple agents operating in a cooperative but uncoordinated manner. Our...
Baruch Awerbuch, Christian Scheideler
In order to enable communication between a dynamic collection of peers with given ID’s, such as “machine.cs.school.edu”, over the Internet, a distributed name service must be implemented on top...
Beacon-Based Routing for Tactical Networks (2008)
Baruch Awerbuch, David Holmer, Herbert Rubens
is reliant upon the development of a reliable, resilient communications capability under harsh, battlefield environments. Due to high mobilities and the nature of the various terrains, the dynamics...
Abstract Collaboration of Untrusting Peers with Changing Interests Extended Abstract (2008)
Baruch Awerbuch, Boaz Patt-shamir, David Peleg, Mark Tuttle
Electronic commerce engines like eBay depend heavily on reputation systems to improve customer confidence that electronic transactions will be successful, and to limit the economic damage done by...
Abstract Distributed Shortest Paths Algorithms (Extended Abstract) (2008)
This paper is concerned with distributed algorithm for find-ing shortest paths in an asynchronous communication net-work. For the problem of Breadth First Search, the best previously known algorithms...
A Denial-of-Service Resistant DHT (2008)
Baruch Awerbuch, Christian Scheideler
Abstract. We consider the problem of designing scalable and robust information systems based on multiple servers that can survive even massive denial-of-service (DoS) attacks. More precisely, we are...
Baruch Awerbuch, Boaz Patt-shamir, David Peleg
We consider a simple model for reputation systems such as the one used by eBay. In our model there are n players, some of which may exhibit arbitrarily malicious (Byzantine) behavior, and there are m...
Abstract Tell Me Who I Am: An Interactive Recommendation System Extended Abstract (2008)
Noga Alon, Baruch Awerbuch, Johns Hopkins U
We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...
ABSTRACT The Price of Routing Unsplittable Flow (2008)
The essence of the routing problem in real networks is that the traffic demand from a source to destination must be satisfied by choosing a single path between source and destination. The splittable...
Abstract Improved Recommendation Systems ∗ Extended Abstract (2008)
Baruch Awerbuch, Boaz Patt-shamir, David Peleg, Mark Tuttle
We consider a model of competitive recommendation systems proposed by Drineas et al. [4]. In recommendation systems (e.g., for books or movies), the system tracks which product each user chose in the...
Scalable Decentralized Control for Sensor Networks via Distributed Lattices (2008)
Baruch Awerbuch, Jonathan Stanton
Abstract. A network of embedded devices needs to be able to execute queries for dynamically changing content. Even in a completely reliable network, this is a formidable task because of the enormous...
Abstract Collaboration of Untrusting Peers with Changing Interests Extended Abstract (2008)
Baruch Awerbuch, Boaz Patt-shamir, David Peleg, Mark Tuttle
Electronic commerce engines like eBay depend heavily on reputation systems to improve customer confidence that electronic transactions will be successful, and to limit the economic damage done by...
The Online Set Cover Problem (Extended Abstract) (2008)
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph (seffi Naor
Let X = {1, 2,..., n} be a ground set of n elements, and let S be a family of subsets of X, |S | = m, with a positive cost cS associated with each S ∈ S. Consider the following online version of...
The problem of scalable and robust distributed data storage has recently attracted a lot of attention. A common approach in the area of peer-to-peer systems has been to use a distributed hash table...
Baruch Awerbuch, Christian Scheideler
Every peer-to-peer system is based on some overlay network connecting its peers. Many of the overlay network concepts proposed in the scientific community are based on the concept of virtual space....
Categories and Subject Descriptors (2008)
Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-shamir, Mark R. Tuttle, The Israel
We consider a model with n players and m objects. Each player has a “preference vector ” of length m that models his grade for each object. The grades are unknown to the players. A player can...
A Time-Optimal Self-Stabilizing Synchronizer Using a Phase Clock (2008)
Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-shamir, George Varghese
Abstract—A synchronizer with a phase counter (sometimes called asynchronous phase clock) is an asynchronous distributed algorithm, where each node maintains a local “pulse counter ” that...
Baruch Awerbuch, Yossi Azar, Serge Plotkin
We develop a framework that allows us to address the issues of admission control and routing in high-speed networks under the restriction that once a call is admitted and routed, it has to proceed to...
Yair Amir, Baruch Awerbuch, Amnon Barak, Yair Amir, Baruch Awerbuch, ...
A new method is presented for job assignment to and reassignment between machines in a computing cluster. Our method is based on a theoretical framework that has been experimentally tested and shown...
Abstract Tell Me Who I Am: An Interactive Recommendation System Extended Abstract (2008)
Noga Alon, Baruch Awerbuch, Yossi Azar, Boaz Patt-shamir, Neumann Fund
We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...
Abstract Cost-Sensitive Analysis of Communication Protocols (Extended Abstract) (2008)
This paper introduces the notion of cost-sensitive com-munication complexity and exemplifies it on the fol-lowing basic communication problems: computing a global function, network synchronization,...
Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-shamir, Mark R. Tuttle, Springer Science+business Media, ...
Abstract We consider a model with n players and m objects. Each player has a “preference vector ” of length m, that models his grades for all objects. The grades are initially unknown to the...
THE WORLD BECAME A SMALLER PLACE IN THE 20TH CENTURY. TRANS- (2008)
Nabil Adam, Baruch Awerbuch, Jacob Slonim, Peter Wegner, Yelena Yesha, Globalizing Business, ...
portation technology caused physical distances to shrink by several orders of magnitude, and telecommunications technology made terrestrial distances insignificant. The transformation of the world...
A Denial-of-Service Resistant DHT (2008)
Baruch Awerbuch, Christian Scheideler
Abstract. We consider the problem of designing scalable and robust information systems based on multiple servers that can survive even massive denial-of-service (DoS) attacks. More precisely, we are...
Brief Announcement: On Cost Sharing Mechanisms in the Network Design Game ABSTRACT (2008)
A fundamental network design problem is the one of Steiner Network Design. The goal is to design a network which is able to support a unit flow for each commodity, at a time, between its source-sink...
Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph (seffi Naor
Abstract Let X = f1; 2; : : : ; ng be a ground set of n elements, and let S be a family of subsets of X, jSj = m, with a positive cost cS associated with each S 2 S.
Baruch Awerbuch, Rohit Khandekar
We consider the Active Min-Cost Measurement problem to minimize the cost incurred by measuring network link delays. Although the problem has a polynomial representation, its covering LP formulation,...
Abstract Efficient Deadlock-Free Routing (2008)
Baruch Awerbuch, Shay Kutten, David Peleg
This paper deals with store-and-forward deadlocks in communication networks. The goal is to design deadlock-free routing schemes with small overhead in communica-tion and space. Our main contribution...
1. ABSTRACT A Cost-Benefit Framework for Online Management of a Metacomputing System (2008)
Yair Amir, Baruch Awerbuch, R. Sean Borgstrom
Managing a large collection of networked machines, with a series of incoming jobs, requires that the jobs be assigned to machines wisely. A new approach to this problem is presented, inspired by...
Baruch Awerbuch, David Holmer, Cristina Nita-rotaru, Herbert Rubens
An ad hoc wireless network is an autonomous self-organizing system of mobile nodes connected by wireless links where nodes not in direct range can communicate via intermediate nodes. A common...
Anycasting in Adversarial Systems: Routing and Admission Control (2008)
Baruch Awerbuch, Andre Brinkmann, Christian Scheideler
In this paper we consider the problem of routing packets in dynamically changing networks, using the anycast mode. In anycasting, a packet may have a set of destinations but only has to reach any one...
Fast load balancing via bounded best response (2008)
Baruch Awerbuch, Yossi Azar, Rohit Kh
It is known that the dynamics of best response in an environment of non-cooperative users may converge to a good solution when users play sequentially, but may cycle far away from the global optimum...
Noga Alon, Baruch Awerbuch, Johns Hopkins U, Yossi Azar, Boaz Patt-shamir
We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...
This paper deals with the file allocation problem [BFR92] concerning the dynamic optimization of communication costs to access data in a distributed environment. We develop a dynamic file...
Baruch Awerbuch, Boaz Patt-shamir, George Varghese
Many important protocols in distributed computing have simple and elegant solutions if we allow the assumption of unbounded size registers. This assumption can be simulated in practice using...
Baruch Awerbuch, Yossi Azar, Serge Plotkin
We develop a framework that allows us to address the issues of admission control and routing in high-speed networks under the restriction that once a call is admitted and routed, it has to proceed to...
We deal with randomized competitive algorithms for non-preemptive call control on tree-like switching networks. We give an O(log n) competitive algorithm for nonpreemptive call scheduling on trees....
Baruch Awerbuch, Yossi Azar, Yair Bartal
The Generalized Steiner Problem (GSP) is defined as follows. We are given a graph with non-negative weights and a set of pairs of vertices. The algorithm has to construct minimum weight subgraph such...
Baruch Awerbuch, Yossi Azar, Stefano Leonardi
In the present work we study the on-line call admission problem in optical networks. We present a general technique to deal with the problem of call admission and wavelength selection by reducing...
Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev
We consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the flow time (total time in the system). The performance of the algorithm, both in offline and...
Distributed control for PARIS (2007)
Exte Nd Ed, Baruch Awerbuch, Israel Cidon, Inder Gopal, Marc Kaplan, Shay Kutten
Baruch Awerbuch Israel Cidon y Inder Gopal yz Marc Kaplan yx Shay Kutten y Abstract We describe the control protocols of the PARIS experimental network. This high bandwidth network for integrated...
Piecemeal Graph Exploration byaMobile Robot (2007)
Baruchawerbuch Margrit Betke, Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, Mona Singh
We study how a mobile robot can piecemeal learn an unknown environment. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must return every...
Adapting to Asynchronous Dynamic Networks (2007)
Extend Ed, Baruch Awerbuch, Boaz Patt-shamir, David Peleg, Michael Saks
Baruch Awerbuch Boaz Patt-Shamir y David Peleg z Michael Saks x Abstract The computational power of different communication models is a fundamental question in the theory of distributed computation....
Piecemeal Graph Exploration by a Mobile Robot (Extended Abstract) (2007)
Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, Mona Singh
) Baruch Awerbuch y Margrit Betke Ronald L. Rivest Mona Singh Laboratory for Computer Science Massachusetts Institute of Technology Cambridge, MA 02139 Abstract We study the problem of learning a...
Competitive Algorithms for On-line Set Cover or How to Beat Murphy's Law (2007)
Baruch Awerbuch, Yossi Azar, Amos Fiat
This paper considers an on-line optimization version of the set cover problem. We present a optimally competitive on-line randomized algorithm which is O(logn log m) competitive where n is the...
Blindly-Competitive Algorithms: Pricing Bidding as a Case Study (2007)
Extend Ed, Baruch Awerbuch, Yossi Azar
) Baruch Awerbuch Yossi Azar y April 26, 1995 Abstract The standard setting for competitive analysis of online algorithms assumes that online algorithm knows the past (but not future) inputs, and can...
Improved Approximation Guarantees for Minimum-Weight (2007)
Trees And, Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala
We consider a formalization of the following problem. A salesperson must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city...
On-line Algorithms for Generalized Steiner Tree and Network Connectivity Leasing (2007)
Baruch Awerbuch, Yossi Azar, Yair Bartal
The Generalized Steiner Tree (GST) problem is defined as follows. We are given a graph with non-negative weights and a set of pairs of vertices. The algorithm has to construct minimum weight subgraph...
Maximal Dense Trees and Competitive On-line Selective Multicast (Extended Abstract) (2007)
Baruch Awerbuch, Yossi Azar, Rainer Gawlick
) Baruch Awerbuch 1;2 Yossi Azar 3 Rainer Gawlick 2 1 Johns Hopkins University 2 Laboratory for Computer Science, MIT 3 Tel-Aviv University Abstract In this paper we introduce the problem of...
Competitive Distributed File Allocation (Extended Abstract) (2007)
Baruch Awerbuch, Yair Bartal, Amos Fiat
) Baruch Awerbuch Yair Bartal y Amos Fiat y Abstract This paper deals with the file allocation problem [BFR92] concerning the dynamic optimization of communication costs to access data in a...
Consistent Distributed Commit: A Constant Overhead Solution (2007)
Baruch Awerbuch, Xiaoqi Lu, Ciprian Tutu
We present an algorithm for persistent consistent distributed commit (distributed database commit) in a dynamic, asynchronous, peer to peer network. The algorithm has constant overhead in time and...
Baruch Awerbuch, Shay Kutten, David Peleg
This note deals with store-and-forward deadlock prevention in communication networks. The approach we adopt is that of establishing buffer classes in order to prevent cyclic waiting chains. This type...
Maintaining Database Consistency in Peer to Peer Networks (2007)
We present an algorithm for persistent consistent distributed commit (distributed database commit) in a dynamic, asynchronous, peer to peer network. The algorithm has constant overhead in time and...
Piecemeal Graph Exploration by aMobile Robot (2007)
Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, Mona Singh
We study how a mobile robot can piecemeal learn an unknown environment. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must return every...
B. A. Physics, Nancy A. Lynch, David D. Clark, Baruch Awerbuch, Frederic R. Morgenthaler, Rainer Gawlick, ...
2
Maximizing Job Benets On-line (2007)
Baruch Awerbuch, Yossi Azar, Oded Regev
We consider a benet model for on-line preemptive scheduling. In this model jobs arrive at the on-line scheduler at their release time. Each job arrives with its own execution time and benet function....
Baruch Awerbuch, David Holmer, Cristina Nita-rotaru, Herbert Rubens
An ad hoc wireless network is an autonomous self-organizing system of mobile nodes connected by wireless links where nodes not in direct range can communicate via intermediate nodes. A common...
Spanish Ministry of Education. (2007)
Matthew Andrews, Baruch Awerbuch, Antonio Fern, Jon Kleinberg, Tom Leighton, Zhiyong Liu, ...
Foundation, Hong Kong.
Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev
We consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the ow time (total time in the system). The performance of the algorithm, both in oine and online...
Distributed paging [BFR92, ABF93b, AK95] deals with the dynamic allocation of copies of files in a distributed network as to minimize the total communication cost over a sequence of read and write...
Baruch Awerbuch, Petra Berenbrink, Andre Brinkmann, Christian Scheideler
In this paper we consider the problem of delivering dynamically changing input streams in dynamically changing networks where both the topology and the input streams can change in an unpredictable...
Distributed paging [BFR92, ABF93b, AK95] deals with the dynamic allocation of copies of files in a distributed network as to minimize the total communication cost over a sequence of read and write...
Baruch Awerbuch, Boaz Patt-shamir, George Varghese
Self-stabilizing protocols must begin operating correctly even when started from an arbitrary state. The end-to-end problem is to ensure reliable message delivery across an unreliable network under...
Baruch Awerbuch, Boaz Patt-shamir, George Varghese
A network protocol consists of a program for each network node. Each program consists of code and inputs as well as local state. The global state of the network consists of the local state of each...
Baruch Awerbuch, Yossi Azar, Serge Plotkin
We develop a framework that allows us to address the issues of admission control and routing in high-speed networks under the restriction that once a call is admitted and routed, it has to proceed to...
This paper gives a randomized competitive distributed paging algorithm called Heat & Dump. The competitive ratio is logarithmic in the total storage capacity of the network, this is optimal to...
A General Approach to Online Network Optimization Problems (2007)
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph (Seffi) Naor
We study a wide range of online graph and network optimization problems, focusing on problems that arise in the study of connectivity and cuts in graphs. In a general online network design problem,...
Abstract Swarm Intelligence Routing Resilient to Byzantine Adversaries (2007)
Baruch Awerbuch, David Holmer, Herbert Rubens
An ad hoc wireless network is an autonomous selforganizing system of mobile nodes connected by wireless links where nodes not in direct range communicate via intermediary nodes. Routing in ad hoc...
Tradeos in worst-case equilibria (2007)
Baruch Awerbuch, Yossi Azar, Yossi Richter, Dekel Tsur
We investigate the problem of routing trac through a congested network in an environment of non-cooperative users. We use the worst-case coordination ratio suggested by Koutsoupias and Papadimitriou...
Tradeoffs in Worst-Case Equilibria (2007)
Baruch Awerbuch, Yossii Azar, Yossi Richter, Dekel Tsur
We investigate the problem of routing traffic through a congested network in an environment of non-cooperative users. We use the worst-case coordination ratio suggested by Koutsoupias and...
Effects of Multi-rate in Ad Hoc Wireless Networks (2007)
Baruch Awerbuch, David Holmer, Herbert Rubens
An ad hoc wireless network is an autonomous selforganizing system of mobile nodes connected by wireless links where nodes not in direct range communicate via intermediate nodes. Modern wireless...
Yehuda Afek, Baruch Awerbuch, Eli Gafni, Yishay Mansour, Nir Shavit
We consider the basic task of of end-to-end communication in dynamic networks, that is, delivery in finite time, of data items generated on-line by a sender, to a receiver, in order and without...
Baruch Awerbuch, Yossi Azar, Stefano Leonardi
We study the on-line call admission problem in optical networks. We present a general technique that allows us to reduce the problem of call admission and wavelength selection to the call admission...
We deal with randomized competitive algorithms for non-preemptive call control on tree-like switching networks. We give an optimal O(log n) competitive algorithm for non-preemptive call scheduling on...
Fast convergence to nearly optimal solutions in potential games (2007)
Baruch Awerbuch, Yossi Azar, Amir Epstein, Vahab S. Mirrokni, Alexander Skopalik
We study the speed of convergence of decentralized dynamics to approximately optimal solutions in potential games. We consider α-Nash dynamics in which a player makes a move if the improvement in...
Asynchronous Recommendation Systems EXTENDED ABSTRACT (2007)
Baruch Awerbuch, Aviv Nisgav, Boaz Patt-shamir
We consider the following abstraction of recommendation systems. There are n players and m objects, and each player has an arbitrary binary preference grade (“likes ” or “dislikes”) for each...
Analysis of Multiple Trees on Path Discovery for Beacon-Based Routing (2007)
Baruch Awerbuch, David Holmer, Herbert Rubens
proved to be an extremely challenging research problem due to the high frequency of link changes in wireless mobile environments. Most known routing protocols struggle to maintain complex routing...
Baruch Awerbuch, Rohit Kh, Ekar Satish Rao
We consider solutions for distributed multicommodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. We show first distributed solutions that...
Distributed network monitoring and multicommodity flows: a primal-dual approach (2007)
Baruch Awerbuch, Rohit Khandekar
A canonical distributed optimization problem is solving a Covering/Packing Linear Program in a distributed environment with fast convergence and low communication and space overheads. In this paper,...
Greedy distributed optimization of multi-commodity flows (2007)
Baruch Awerbuch, Rohit Khandekar
The multi-commodity flow problem is a classical combinatorial optimization problem that addresses a number of practically important issues of congestion and bandwidth management in...
Baruch Awerbuch, Rohit Kh, Ekar Satish Rao
We consider solutions for distributed multicommodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. We show first distributed solutions that...
Greedy distributed optimization of multi-commodity flows (2007)
While multi-commodity flow is a classical combinatorial optimization problem, it also directly addresses a number of practically important issues of congestion and bandwidth management in...
Baruch Awerbuch, Christian Scheideler
We consider the problem of designing an efficient and robust distributed random number generator for peer-to-peer systems that is easy to implement and works even if all communication channels are...
Robust random number generation for peer-to-peer systems (2007)
Baruch Awerbuch, Christian Scheideler
Abstract. We consider the problem of designing an efficient and robust distributed random number generator for peer-to-peer systems that is easy to implement and works even if all communication...
Improved Approximation Guarantees for Minimum-Weight k-Trees and Prize- Collecting Salesmen (2006)
Awerbuch, Baruch, Azar, Yossi, Blum, Avrim
Consider a salesperson that must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached demand specifying the...
Tell me who I am: An interactive recommendation system (2006)
Noga Alon, Baruch Awerbuch, Yossi Azar, Boaz Patt-shamir
We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...
A Time Optimal Self-Stabilizing Synchronizer Using A Phase Clock ∗ (2006)
Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-shamir, George Varghese
A synchronizer with a phase counter (sometimes called asynchronous phase clock) is an asynchronous distributed algorithm, where each node maintains a local ‘pulse counter ’ that simulates the...
Noga Alon, Baruch Awerbuch, Johns Hopkins U, Yossi Azar, Boaz Patt-shamir
We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...
Online client-server load balancing without global information (2005)
Baruch Awerbuch, Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton
We consider distributed online algorithms tbr maximizing through-put in a network of clients and servers, modeled as a bipartite graph. Unlike most prior work on online load balancing, we do not...
Collaborate With Strangers To Find Own Preferences (2005)
Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-shamir, Mark R. Tuttle
We consider a model with n players and m objects. Each player has a “preference vector ” of length m, that models his grades for all objects. The grades are initially unknown to the players. A...
Provably competitive adaptive routing (2005)
Baruch Awerbuch, David Holmer, Herbert Rubens
∗ Supported by NSF grants ANIR-0240551
Competitive collaborative learning (2005)
Baruch Awerbuch, Robert D. Kleinberg
Abstract. We develop algorithms for a community of users to make decisions about selecting products or resources, in a model characterized by two key features: – The quality of the products or...
Dynamics of Learning Algorithms for the On-Demand Secure Byzantine Routing Protocol (2005)
Baruch Awerbuch, Reza Curtmola, David Holmer, Cristina Nita-rotaru, Herb Rubens, Robert G. Cole
this paper, we extend the analysis in [4] by a) investigating the dynamics of the learning algorithm proposed in the original ODSBR protocol, b) analyzing new learning algorithms and c) investigating...
Provably Competitive Adaptive Routing (2005)
Baruch Awerbuch, David Holmer, Herb Rubens
An ad hoc wireless network is an autonomous self-organizing system of mobile nodes connected by wireless links where nodes not in direct range communicate via intermediary nodes. Routing in ad hoc...
Mobile Ad Hoc, Baruch Awerbuch, David Holmer, Herbert Rubens
We present a performance evaluation of the Pulse protocol operating in a peer-to-peer mobile ad hoc network environment. The Pulse protocol utilizes a periodic flood (the pulse) initiated by the...
The pulse protocol: Mobile ad hoc network performance evaluation (2005)
Baruch Awerbuch, David Holmer, Herbert Rubens
Abstract — We present a performance evaluation of the Pulse protocol operating in a peer-to-peer mobile ad hoc network environment. The Pulse protocol utilizes a periodic flood (the pulse)...
A Cost-Benefit Flow Control for Reliable Multicast and Unicast in Overlay Networks (2005)
Yair Amir, Baruch Awerbuch, Claudiu Danilov, Jonathan Stanton
Abstract — When many parties share network resources on an overlay network, mechanisms must exist to allocate the resources and protect the network from overload. Compared to large physical...
Online client-server load balancing without global information (2005)
Baruch Awerbuch, Mohammad T. Hajiaghayi, Robert Kleinberg, Tom Leighton
We consider distributed online algorithms for maximizing throughput in a network of clients and servers, modeled as a bipartite graph. Unlike most prior work on online load balancing, we do not...
Collaborate With Strangers To Find Own Preferences (2005)
Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-shamir, Mark R. Tuttle
We consider a model with n players and m objects. Each player has a “preference vector ” of length m, that models his grades for all objects. The grades are initially unknown to the players. A...
Dynamics of learning Algorithms for the On-Demand Secure Byzantine Routing (2005)
Baruch Awerbuch, Reza Curtmola, David Holmer, Herb Rubens, Robert G. Cole
Abstract. We investigate the performance of of several protocol enhancements to the On-Demand Secure Byzantine Routing (ODSBR) [3] protocol in the presence of various Byzantine Attack models. These...
Collaborate With Strangers To Find Own Preferences (2005)
Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-shamir, Mark R. Tuttle
We consider a model with n players and m objects. Each player has an unknown grade for each object, modeled by a “preference vector ” of length m. A player can learn his grade for an object by...
Online client-server load balancing without global information (2005)
Baruch Awerbuch, Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton
We consider distributed online algorithms for maximizing throughput in a network of clients and servers, modeled as a bipartite graph. Unlike most prior work on online load balancing, we do not...
Competitive collaborative learning (2005)
Baruch Awerbuch, Robert D. Kleinberg
Abstract. We develop algorithms for a community of users to make decisions about selecting products or resources, in a model characterized by two key features: – The quality of the products or...
Mitigating byzantine attacks in ad hoc wireless networks (2004)
Baruch Awerbuch, Reza Curtmola, David Holmer, Cristina Nita-rotaru, Herbert Rubens
Attacks where adversaries have full control of a number of authenticated devices and behave arbitrarily to disrupt the network are referred to as Byzantine attacks. Traditional secure routing...
The Pulse Protocol: Energy Efficient Infrastructure Access (2004)
Baruch Awerbuch, David Holmer, Herbert Rubens
We present the Pulse protocol which is designed for multi-hop wireless infrastructure access. While similar to the more traditional access point model, it is extended to operate across multiple hops....
The Pulse Protocol: Energy Efficient Infrastructure Access (2004)
Baruch Awerbuch, David Holmer, Herbert Rubens
We present the Pulse protocol which is designed for multi-hop wireless infrastructure access. While similar to the more traditional access point model, it is extended to operate across multiple hops....
High Throughput Route Selection in Multi-Rate Ad Hoc Wireless Networks (2004)
Baruch Awerbuch, David Holmer, Herbert Rubens
Modern wireless devices, such as those that implement the 802.11b standard, utilize multiple transmission rates in order to accommodate a wide range of channel conditions. Traditional ad hoc routing...
The Pulse Protocol: Sensor Network Routing and Power Saving (2004)
Baruch Awerbuch, David Holmer, Herbert Rubens
We present a performance evaluation of the Pulse protocol operating in a sensor network. In this work, a number of modifications are made to the original Pulse protocol to provide efficient operation...
Baruch Awerbuch, David Holmer, Herbert Rubens
Modern wireless devices, such as those that implement the 802.11abg standards, utilize multiple transmission rates in order to accommodate a wide range of channel conditions. The use of multiple...
A general approach to online network optimization problems (2004)
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph (seffi Naor
Abstract We study a wide range of online graph and network optimization problems, focusing on problems that arise in the study of connectivity and cuts in graphs. In a general online network design...
Baruch Awerbuch, Christian Scheideler
In this paper we consider the problem of maintaining a mapping of data objects to memory modules so that the mapping is order preserving, i.e. objects closely together in the sorted set of current...
Improved Recommendation Systems Extended Abstract (2004)
Baruch Awerbuch, Boaz Patt-shamir, David Peleg, Mark Tuttle
We consider a model of competitive recommendation systems proposed by Drineas et al. [DKR02]. In recommendation systems (such as book or movie recommendations), the system tracks which product each...
The hyperring: A low-congestion deterministic data structure for distributed environments (2004)
Baruch Awerbuch, Christian Scheideler
Abstract In this paper we study the problem of designing searchableconcurrent data structures with performance guarantees that can be used in a distributed environment where dataelements are stored...
Yozo Hida, Paul Huang, Rajesh Nishtala, Baruch Awerbuch, David Holmer, Cristina Nita-rotaru, ...
Proposes a secure routing protocol tolerant of faulty or malicious nodes. They consider malicious nodes that tries to create routing loops, misdirects packets, or selectively drops packets. Their...
Yozo Hida, Paul Huang, Rajesh Nishtala, Baruch Awerbuch, David Holmer, Cristina Nita-rotaru, ...
routing protocol resilient to byzantine failures. In ACM Workshop on Wireless Security (WiSe), Atlanta,
Baruch Awerbuch, David Holmer, Herbert Rubens
An ad hoc wireless network is an autonomous selforganizing system of mobile nodes connected by wireless links where nodes not in direct range communicate via intermediary nodes. Routing in ad hoc...
Baruch Awerbuch, David Holmer, Herbert Rubens
The Swarm Intelligence paradigm has recently been demonstrated as an e#ective approach for routing in small static network configurations with no adversarial intervention. These algorithms have also...
ODSBR: An On-Demand Secure Byzantine Routing Protocol (2003)
Baruch Awerbuch, Reza Curtmola, David Holmer, Cristina Nita-rotaru, Herbert Rubens
A common technique used by routing protocols for ad hoc wireless networks is to establish the routing paths on-demand, as opposed to continually maintaining a complete routing table. Since in an ad...
A Generic Scheme for Building Overlay Networks in Adversarial Scenarios (2003)
Ittai Abraham, Baruch Awerbuch, Yossi Azar, Yair Bartal, Dahlia Malkhi, Elan Pavlov
This paper presents a generic scheme for a central, yet untackled issue in overlay dynamic networks: maintaining stability over long life and against malicious adversaries. The generic scheme...
The Online Set Cover Problem (2003)
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph (Seffi) Naor
Let X = f1; 2; : : : ; ng be a ground set of n elements, and let S be a family of subsets of X , jSj = m, with a positive cost c S associated with each S 2 S.
Peer-to-Peer Systems for Prefix Search (2003)
Baruch Awerbuch, Christian Scheideler
This paper presents a general methodology for building messagepassing peer-to-peer systems capable of performing prefix search for arbitrary user-defined names. Our methodology allows to achieve even...
Reducing truth-telling online mechanisms to online optimization (2003)
We describe a general technique for converting an online algorithm B to a truthtelling mechanism. We require that the original online competitive algorithm has certain “niceness” properties in...
Anycasting in adversarial systems: Routing and admission control (2003)
Baruch Awerbuch, André Brinkmann, Christian Scheideler
Abstract. In this paper we consider the problem of routing packets in dynamically changing networks, using the anycast mode. In anycasting, a packet may have a set of destinations but only has to...
A Generic Scheme for Building Overlay Networks in Adversarial Scenarios (2003)
Ittai Abraham, Yossi Azar, Baruch Awerbuch, Yair Bartal, Dahlia Malkhi, Elan Pavlov
This paper presents a generic scheme for a central, yet untackled issue in overlay dynamic networks: maintaining stability over long life and against malicious adversaries. The generic scheme...
A Robust Routing Algorithm for Overlay Networks (2003)
Baruch Awerbuch, Andreas Terzis
A number of different Overlay network designs have been proposed to provide a large range of services ranging from content delivery and application-level multicast to robust data delivery in the...
A Reliable Broadcast Protocol, (2002)
Segall,Adrian, Awerbuch,Baruch
Broadcast multipoint communication is the delivery of copies of messages to all nodes in a communication network. In a network with mobile subscribers, for example, the location and connectivity to...
A Reliable Broadcast Algorithm, (2002)
Segall, Adrian, Awerbuch, Baruch
Broadcast in a communication network is the delivery of copies of messages to all nodes. A broadcast algorithm is reliable if all messages reach all nodes in finite time, in the correct order and...
Atomic Shared Register Access by Asynchronous Hardware. (2002)
Vitanyi,Paul M., Awerbuch,Baruch
The contributions of this paper is two-fold. First, it describes two ways to construct multivalued atomic n-writer n-reader registers. The first solution uses atomic 1-writer 1-reader registers and...
An on-demand secure routing protocol resilient to byzantine failures (2002)
Baruch Awerbuch, David Holmer, Cristina Nita-rotaru, Herbert Rubens
An ad hoc wireless network is an autonomous self-organizing system of mobile nodes connected by wireless links where nodes not in direct range can communicate via intermediate nodes. A common...
Global flow control for wide area overlay networks: A cost-benefit approach (2002)
Yair Amir, Baruch Awerbuch, Claudiu Danilov, Jonathan Stanton
Abstract---This paper presents a flow control protocol for multi-sender multi-group multicast and unicast in wide area overlay networks. The protocol is analytically grounded and achieves real world...
An on-demand secure routing protocol resilient to byzantine failures (2002)
Baruch Awerbuch, David Holmer, Cristina Nita-rotaru, Herbert Rubens
An ad hoc wireless network is an autonomous self-organizing system of mobile nodes connected by wireless links where nodes not in direct range can communicate via intermediate nodes. A common...
Global flow control for wide area overlay networks: A cost-benefit approach (2002)
Yair Amir, Baruch Awerbuch, Claudiu Danilov, Jonathan Stanton
Abstract---This paper presents a flow control protocol for multi-sender multi-group multicast and unicast in wide area overlay networks. The protocol is analytically grounded and achieves real world...
Anycasting and Multicasting in Adversarial Systems: Routing and Admission Control (2002)
Baruch Awerbuch, André Brinkmann, Christian Scheideler
In this paper we consider the problem of routing packets in dynamically changing networks, concentrating on two different modes: anycasting and multicasting. In anycasting, a packet has a set of...
Global flow control for wide area overlay networks: A cost-benefit approach (2002)
Yair Amir, Baruch Awerbuch, Claudiu Danilov, Jonathan Stanton
Abstract—This paper presents a flow control protocol for multi-sender multi-group multicast and unicast in wide area overlay networks. The protocol is analytically grounded and achieves real world...
Global flow control for wide area overlay networks: A cost-benefit approach (2002)
Yair Amir, Baruch Awerbuch, Claudiu Danilov, Jonathan Stanton
Abstract—This paper presents a flow control protocol for multi-sender multi-group multicast and unicast in wide area overlay networks. The protocol is analytically grounded and achieves real world...
Maintaining Database Consistency in Peer to Peer Networks (2002)
We present an algorithm for persistent consistent distributed commit (distributed database commit) in a dynamic, asynchronous, peer to peer network. The algorithm has constant overhead in time and...
Flow control for many-to-many multicast: A cost-benefit approach (2001)
Yair Amir, Baruch Awerbuch, Claudiu Danilov, Jonathan Stanton
Flow control, especially in multicast networks, is a problem of significant theoretical and practical interest. We present a protocol that is analytically grounded, yet also achieves real world...
Universal-Stability Results and Performance Bounds for Greedy Contention-Resolution Protocols (2001)
Matthew Andrews, Baruch Awerbuch, Antonio Fernandez, Tom Leighton, Ziyong Liu, Jon Kleinberg, ...
In this paper, we analyze the behavior of packet-switched communication networks in which packets arrive dynamically at the nodes and are routed in discrete time steps across the edges. We This work...
Flow control for many-to-many multicast: A cost-benefit approach (2001)
Yair Amir, Baruch Awerbuch, Claudiu Danilov, Jonathan Stanton
Flow control, especially in multicast networks, is a problem of significant theoretical and practical interest. We present a protocol that is analytically grounded, yet also achieves real world...
Author Affiliations Yair, Yair Amir, Yair Amir, Baruch Awerbuch, Baruch Awerbuch, ...
. A new method is presented for job assignment to and reassignment between machines in a computing cluster. Our method is based on a theoretical framework that has been experimentally tested and...
Multicast Routing Through a Network With Hierarchical Topology Aggregation (2000)
Baruch Awerbuch, Tripurari Singh
The PNNI is an umbrella protocol that allows considerable routing exibility. While it species the network signalling, it leaves route generation undened. Any non-trivial route generation requires the...
Baruch Awerbuch, Yossi Azar, Oded Regev
We consider a bene t model for on-line preemptive scheduling. In this model jobs arrive at the on-line scheduler at their release time. Each job arrives with its own execution time and bene t...
An opportunity cost approach for job assignment in a scalable computing cluster (2000)
Yair Amir, Baruch Awerbuch, Amnon Barak, R. Sean Borgstrom, Arie Keren
A new method is presented for job assignment to and reassignment between machines in a computing cluster. Our method is based on a theoretical framework that has been experimentally tested and shown...
Minimizing the flow time without migration (1999)
Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev
We consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the flow time (total time in the system). The performance of the algorithm, both in offline and...
New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen (1999)
Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala
We consider a formalization of the following problem. A salesperson must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city...
Approximating the Size of a Dynamically Growing Asynchronous Distributed Network. (1998)
Awerbuch, Baruch, Plotkin, Serge A.
We show how to approximate up to a constant factor the size of a dynamically growing asynchronous distributed network. The technique presented in this paper has an amortized message complexity of...
Polynomial End-to-End Communication. (1998)
Awerbuch, Baruch, Mansour, Yishay, Shavit, Nir
A dynamic communication network is one in which links may repeatedly fail and recover. In such a network, though it is impossible to establish a path of unfailed links, reliable communication is...
Cost-Sensitive Analysis of Communication Protocols, (1998)
Awerbuch, Baruch, Baratz, Alan, Peleg, David
This paper introduces the notion of cost-sensitive communication complexity and exemplifies it on the following basic communication problems: computing a global function, network synchronization,...
A Cost-Benefit Approach to Resource Allocation in Scalable Metacomputers (1998)
Borgstrom, R. S., Awerbuch, Baruch, Amir, Yair
The work described in this report develops, tests, and implements several advanced strategies for resource management in a network of machines. The Cost-Benefit Framework, developed in this work,...
Large Algorithmic Methods for Dynamic System Management (1998)
Awerbuch, Baruch, Leighton, F. T.
The issue of uncertainty-tolerant computing has been largely ignored by algorithm designers, who focused on developing elegant mathematical structures for solving traditional combinatorial problems....
Near-linear time construction of sparse neighborhood covers (1998)
Baruch Awerbuch, Bonnie Berger, Lenore Cowen, David Peleg
Abstract. This paper introduces a near-linear time sequential algorithm for constructing a sparse neighborhood cover. This implies analogous improvements (from quadratic to near-linear time) for any...
Yair Amir, Baruch Awerbuch, Amnon Barak, R. Sean Borgstrom, Arie Keren
. A new method is presented for job assignment to and reassignment between machines in a computing cluster. Our method is based on a theoretical framework that has been experimentally tested and...
The Java Market: Transforming the Internet into a Metacomputer (1998)
Yair Amir, Baruch Awerbuch, Ryan S. Borgstrom
. Most of the machines that are connected to the Internet are idle a significant fraction of the time. This paper presents the Java Market, a system that allows organizations and Internet users to...
Yair Amir, Baruch Awerbuch, Amnon Barak, R. Sean Borgstrom, Arie Keren
. A new method is presented for job assignment to and reassignment between machines in a computing cluster. Our method is based on a theoretical framework that has been experimentally tested and...
Routing Through Networks with Hierarchical Topology Aggregation (1998)
Baruch Awerbuch, Yi Du, Bilal Khan, Yuval Shavitt
In the future, global networks will consist of a hierarchy of subnetworks called domains. For reasons of both scalability and security, domains will not reveal details of their internal structure to...
Routing Through Networks with Hierarchical Topology Aggregation (1998)
Baruch Awerbuch, Yi Du, Bilal Khan, Yuval Shavitt
In the future, global networks will consist of a hierarchy of subnetworks called domains. For reasons of both scalability and security, domains will not reveal details of their internal structure to...
Polylogarithmic-Overhead Piecemeal Graph Exploration (1998)
Baruch Awerbuch, Stephen Kobourov
We introduce a new traversal technique in the context of piecemeal exploration of unknown graphs. The problem of learning a graph via piecemeal exploration requires a robot to create a complete map...
The Java Market: Transforming the Internet into a Metacomputer (1998)
Yair Amir, Baruch Awerbuch, Ryan S. Borgstrom
Most of the machines that are connected to the Internet are idle a significant fraction of the time. This paper presents the Java Market, a system that allows organizations and Internet users to make...
A Cost-Benefit Framework for Online Management of a Metacomputing System (1998)
Yair Amir, Baruch Awerbuch, R. Sean Borgstrom
Managing a large collection of networked machines, with a series of incoming jobs, requires that the jobs be assigned to machines wisely. A new approach to this problem is presented, inspired by...
Online algorithms for selective multicast and maximal dense trees (1997)
Baruch Awerbuch, Tripurari Singh
Multicast routing and admission control can be defined as follows. Various network users issue online requests for a connection to certain multicast sources. The network either connects this request...
Slide - The Key to Polynomial End-to-End Communication (1997)
Yehuda Afek, Baruch Awerbuch, Eli Gagni, Yishay Mansour, Adi Rosen, Nir Shavit
We consider the basic task of of end-to-end communication in dynamic networks, that is, delivery in finite time, of data items generated on-line by a sender, to a receiver, in order and without...
Buy-at-Bulk Network Design (1997)
The essence of the simplest buy-at-bulk network design problem is buying network capacity "wholesale " to guarantee connectivity from all network nodes to a certain central network switch....
Topology Aggregation for Directed Graph (1997)
Baruch Awerbuch, Yuval Shavitt
This paper addresses the problem of aggregating the topology of a sub-network in a compact way with minimum distortion. The problem arises from networks that have a hierarchical structure, where each...
The Maintenance of Common Data in a Distributed System (1997)
Baruch Awerbuch, Leonard J. Schulman
A basic task in distributed computation is the maintenance at each processor of the network, of a current and accurate copy of a common database. A primary example is the maintenance, for routing and...
The Maintenance of Common Data in a Distributed System (1997)
Baruch Awerbuch, Leonard J. Schulman
A basic task in distributed computation is the maintenance at each processor of the network, of a current and accurate copy of a common database. A primary example is the maintenance, for routing and...
Universal Stability Results for Greedy Contention-Resolution Protocols (1996)
Matthew Andrews, Baruch Awerbuch, Antonio Fernandez, Jon Kleinberg, Tom Leighton, Zhiyong Liu
In this paper, we analyze the behavior of communication networks in which packets are generated dynamically at the nodes and routed in discrete time steps across the edges. We focus on a basic...
Baruch Awerbuch, Yossi Azar, Tom Leighton
In this paper, we formulate and provide optimal solutions for a broad class of problems in which a decision-maker is required to select from among numerous competing options. The goal of the...
On-line Competitive Algorithms for Call Admission in Optical Networks (1996)
Baruch Awerbuch, Yossi Azar, Amos Fiat, Stefano Leonardi, Adi Rosén
In the present work we study the on-line call admission problem in optical networks. We present a general technique to deal with the problem of call admission and wavelength selection by reducing...
Packet Routing via Min-Cost Circuit Routing (1996)
Baruch Awerbuch, Yossi Azar, Amos Fiat
In this paper we initiate the study of competitive on-line packet routing algorithms. At any time, any network node may initiate sending a packet to another node. Our goal is to route these packets...
Fast Distributed Network Decompositions and Covers (1996)
Baruch Awerbuch, Bonnie Berger, Lenore Cowen, David Peleg
This paper presents deterministic sublinear-time distributed algorithms for network decomposition and for constructing a sparse neighborhood cover of a network. The latter construction leads to...
Baruch Awerbuch, Yossi Azar, Tom Leighton
In this paper, we formulate and provide optimal solutions for a broad class of problems in which a decision-maker is required to select from among numerous competing options. The goal of the...
Distributed Paging for General Networks (1996)
Baruch Awerbuch, Yair Bartal, Amos Fiat
Distributed paging [BFR92, ABF93b, AK95] deals with the dynamic allocation of copies of files in a distributed network as to minimize the total communication cost over a sequence of read and write...
Universal Stability Results for Greedy Contention-Resolution Protocols (1996)
Matthew Andrews, Baruch Awerbuch, Antonio Fernández, Jon Kleinberg, Tom Leighton, Zhiyong Liu
In this paper, we analyze the behavior of communication networks in which packets are generated dynamically at the nodes and routed in discrete time steps across the edges. We focus on a basic...
On-line Generalized Steiner Problem (1996)
Baruch Awerbuch, Yossi Azar, Yair Bartal
The Generalized Steiner Problem (GSP) is defined as follows. We are given a graph with non-negative weights and a set of pairs of vertices. The algorithm has to construct minimum weight subgraph such...
Universal Stability Results for Greedy Contention-Resolution Protocols (1996)
Matthew Andrews, Baruch Awerbuch, Antonio Fernández, Jon Kleinberg, Tom Leighton, Zhiyong Liu
In this paper, we analyze the behavior of communication networks in which packets are generated dynamically at the nodes and routed in discrete time steps across the edges. We focus on a basic...
Load balancing in the L_p norm (1995)
Baruch Awerbuch, Yossi Azar, Edward F. Grove, Ming-Yang Kao, P. Krishnan, Jeffrey Scott Vitter
In the load balancing problem, there is a set of servers, and jobs arrive sequentially. Each job can be run on some subset of the servers, and must be assigned to one of them in an online fashion....
Piecemeal graph exploration by a mobile robot (1995)
Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, Mona Singh
We study how a mobile robot can piecemeal learn an unknown environment. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must return every...
Piecemeal graph exploration by a mobile robot (1995)
Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, Mona Singh
We study how a mobile robot can learn an unknown environment in a piecemeal manner. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must...
Competitive multicast routing (1995)
In this paper, we introduce and solve the multicast routing problem for virtual circuit environment without making any assumptions about the communication patterns, or about the network topology. By...
Load balancing in the L_p norm (1995)
Baruch Awerbuch, Yossi Azar, Edward F. Grove, Ming-Yang Kao, P. Krishnan, Jeffrey Scott Vitter
In the load balancing problem, there is a set of servers, and jobs arrive sequentially. Each job can be run on some subset of the servers, and must be assigned to one of them in an online fashion....
Improved Approximation Guarantees for Minimum-Weight (1995)
Trees And, Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala
Consider a salesperson that must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached demand specifying the...
Competitive Routing of Virtual Circuits with Unknown Duration (1995)
Baruch Awerbuch, Yossi Azar, Serge Plotkin, Orli Waarts
In this paper we present a strategy to route unknown duration virtual circuits in a highspeed communication network. Previous work on virtual circuit routing concentrated on the case where the call...
Improved Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen (1995)
Baruch Awerbuch, Yossi Azar, Avrim Blum, And Santosh Vempala, Santosh Vempala
Consider a salesperson that must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached demand specifying the...
Baruch Awerbuch, Yossi Azar, Edward F. Grove, Ming-yang Kao, P. Krishnan, Jeffrey Scott Vitter
In the load balancing problem, there is a set of servers, and jobs arrive sequentially. Each job can be run on some subset of the servers, and must be assigned to one of them in an online fashion....
Local Management of a Global Resource in a Communication Network (1995)
Yehuda Afek, Baruch Awerbuch, Serge Plotkin, Michael Saks
This paper introduces a new distributed data object called Resource Controller which provides an abstraction for managing the consumption of a global resource in a distributed system. Examples of...
Online Tracking of Mobile Users (1995)
This paper deals with the problem of maintaining a distributed directory server, that enables us to keep track of mobile users in a distributed network. The paper introduces the graph-theoretic...
Improved Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen (1995)
Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala
We consider a formalization of the following problem. A salesperson must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city...
Piecemeal graph exploration by a mobile robot (1995)
Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, Mona Singh
We study how a mobile robot can learn an unknown environment in a piecemeal manner. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must...
Load balancing in the lp norm (1995)
Baruch Awerbuch, Yossi Azar, P. Krishnan
Abstract. In the load balancing problem, there is a set of servers, and jobs arrive sequentially. Each job can be run on some subset of the servers, and must be assigned to one of them in an online...
Baruch Awerbuch, Rainer Gawlick, Tom Leighton, Yuval Rabani
This paper considers the problems of admission control and virtual circuit routing in high performance computing and communication systems. Admission control and virtual circuit routing problems...
Competitive Routing of Virtual Circuits with Unknown Duration (1994)
Baruch Awerbuch, Yossi Azar, Serge Plotkin, Orli Waarts
In this paper we present a strategy to route unknown duration virtual circuits in a highspeed communication network. Previous work on virtual circuit routing concentrated on the case where the call...
Memory-Efficient and Self-Stabilizing Network RESET (1994)
Baruch Awerbuch, Rafail Ostrovsky
In this paper we consider the question of fault-tolerant distributed network protocols with extremely small memory requirements per processor. In particular, we show that even in the case of...
Competitive Routing of Virtual Circuits with Unknown Duration (1994)
Baruch Awerbuch, Yossi Azar, Serge Plotkin, Orli Waarts
In this paper we present a strategy to route unknown duration virtual circuits in a highspeed communication network. Previous work on virtual circuit routing concentrated on the case where the call...
Bounding the Unbounded (Extended Abstract) (1994)
B. Awerbuch, Baruch Awerbuch, Boaz Patt-shamir, George Varghese
Baruch Awerbuch Lab. for Computer Science MIT Boaz Patt-Shamir y Lab. for Computer Science MIT George Varghese z Dept. of Computer Science Washington University Abstract Many important protocols in...
Self-Stabilization by Local Checking and Global Reset (Extended Abstract) (1994)
Baruch Awerbuch, Boaz Patt-shamir, George Varghese, Shlomi Dolev
Baruch Awerbuch 12 , Boaz Patt-Shamir 2 , George Varghese 3 and Shlomi Dolev 45 1 Dept. of Computer Science, Johns Hopkins University 2 Lab. for Computer Science, MIT 3 Dept. of Computer Science,...
Improved Approximation Guarantees for Minimum-Weight (1994)
Trees And Prize-Collecting, Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala
Consider a salesperson that must sell some quota of brushes in order to win a trip to Hawaii. This salesperson has a map (a weighted graph) in which each city has an attached demand specifying the...
In this paper, we describe a very simple boundedqueuesize local-control algorithm for routing multicommodity flows in a dynamically-changing distributed network. The algorithm is based on the...
Compact Distributed Data Structures for Adaptive Routing (1994)
Baruch Awerbuch, Amotz Bar-noy, Nathan Linial, David Peleg
In designing a routing scheme for a communication network it is desirable to use as short as possible paths for routing messages, while keeping the routing information stored in the processors'...
Competitive On-line Selective Multicast via Dense Trees Construction (Extended Abstract) (1994)
Baruch Awerbuch, Yossi Azar, Rainer Gawlick
) Baruch Awerbuch 1;2 Yossi Azar 3 Rainer Gawlick 2 1 Johns Hopkins University 2 Laboratory for Computer Science, MIT 3 Tel-Aviv University May 3, 1994 Abstract This paper introduces the problem of...
Competitive Concurrent Distributed Data Structures (1994)
Baruch Awerbuch, Yair Bartal, Amos Fiat, Rainer Gawlick
this paper are ffl definition of semantics and complexity measures for distributed data structure for concurrent asynchrnous distributed directory access.
The work is motivated by deadlock resolution and resource allocation problems, occurring in distributed server-client architectures. We consider a very general setting which includes, as special...
Distributively-Competitive Online Paging for Arbitrary-Topology Networks (Extended Abstract) (1994)
Baruch Awerbuch, Yair Bartal, Amos Fiat
) Baruch Awerbuch Yair Bartal y Amos Fiat y May 3, 1994 Abstract This paper gives first competitive distributed paging algorithm for the general network topology. The competitive ratios in storage...
Efficient Asynchronous Distributed Symmetry Breaking (1994)
Baruch Awerbuch, Lenore Cowen, Mark Smith
This paper considers symmetry-breaking in an asynchronous distributed network. We present and analyze a randomized protocol that constructs a maximal independent set in O(logn) expected time, and...
Baruch Awerbuch, Rainer Gawlick, Tom Leighton, Yuval Rabani
This paper considers the problems of admission control and virtual circuit routing in high performance computing and communication systems. Admission control and virtual circuit routing problems...
Blindly-Competitive Algorithms for Pricing & Bidding (Extended Abstract) (1994)
) Baruch Awerbuch Yossi Azar y November 30, 1994 Abstract The standard setting for competitive analysis of online algorithms assumes that online algorithm knows the past (but not future) inputs, and...
Baruch Awerbuch, Rainer Gawlick, Tom Leighton, Yuval Rabani
In this paper, we consider the problems of admission control and virtual circuit routing in high performance computing and communication systems. The admission control and virtual circuit routing...
Competitive Routing of Virtual Circuits with Unknown Duration (1994)
Baruch Awerbuch, Yossi Azar, Serge Plotkin, Orli Waarts
In this paper we present a strategy to route unknown duration virtual circuits in a highspeed communication network. Previous work on virtual circuit routing concentrated on the case where the call...
Baruch Awerbuch, Rainer Gawlick, Tom Leighton, Yuval Rabani
This paper considers the problems of admission control and virtual circuit routing in high performance computing and communication systems. Admission control and virtual circuit routing problems...
Memory-Efficient and Self-Stabilizing Network RESET (Extended Abstract) (1994)
Baruch Awerbuch, Rafail Ostrovsky
In this paper we consider the question of fault-tolerant distributed network protocols with extremely small memory requirements per processor. In particular, we show that even in the case of...
Time optimal self-stabilizing synchronization (extended abstract (1993)
Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-shamir, George Varghese
In this paper we present a time optimal self-stabilizing scheme for network synchronization. Our construction has two parts. First, we give a simple rule by which each node can compute its pulse...
Competitive Distributed File Allocation (1993)
Baruch Awerbuch, Yair Bartal, Amos Fiat
This paper deals with the file allocation problem [BFR92] concerning the dynamic optimization of communication costs to access data in a distributed environment. We develop a dynamic file...
A Simple Local-Control Approximation Algorithm for Multicommodity Flow (1993)
In this paper, we describe a very simple (1 + ")- approximation algorithm for the multicommodity flow problem. The algorithm runs in time that is polynomial in N (the number of nodes in the...
Near-Linear Cost Sequential and Distributed Constructions of Sparse Neighborhood Covers (1993)
Baruch Awerbuch, Bonnie Berger, Lenore Cowen, David Peleg
This paper introduces the first near-linear (specifically, O(E log n + n log 2 n)) time algorithm for constructing a sparse neighborhood cover in sequential and distributed environments. This...
Approximate Load Balancing on Dynamic and Asynchronous Networks (1993)
William Aiello, Baruch Awerbuch, Bruce Maggs, Satish Rao
This paper presents a simple local algorithm for load balancing in a distributed network. The algorithm makes no assumption about the structure of the network. It can be executed on a synchronous...
Throughput-Competitive On-Line Routing (1993)
Baruch Awerbuch, Yossi Azar, Serge Plotkin
We develop a framework that allows us to address the issues of admission control and routing in high-speed networks under the restriction that once a call is admitted and routed, it has to proceed to...
Heat & Dump: Competitive Distributed Paging (1993)
Baruch Awerbuch, Yair Bartal, Amos Fiat
This paper gives a randomized competitive distributed paging algorithm called Heat & Dump. The competitive ratio is logarithmic in the total storage capacity of the network, this is optimal to...
Competitive Distributed File Allocation (1993)
Baruch Awerbuch, Yair Bartal, Amos Fiat
This paper deals with the file allocation problem [BFR92] concerning the dynamic optimization of communication costs to access data in a distributed environment. We develop a dynamic file...
Routing with Polynomial Communication-Space Tradeoff (1993)
This paper presents a family of memory-balanced routing schemes that use relatively short paths while storing relatively little routing information. The hierarchical schemes H k (for every integer k...
Throughput-Competitive On-Line Routing (1993)
Baruch Awerbuch, Yossi Azar, Serge Plotkin
We develop a framework that allows us to address the issues of admission control and routing in high-speed networks under the restriction that once a call is admitted and routed, it has to proceed to...
Near-Linear Cost Sequential and Distributed Constructions of Sparse Neighborhood Covers (1993)
Baruch Awerbuch, Bonnie Berger, Lenore Cowen, David Peleg
This paper introduces the first near-linear (specifically, O(E log n + n log 2 n)) time algorithm for constructing a sparse neighborhood cover in sequential and distributed environments. This...
Throughput-Competitive On-Line Routing (1993)
Baruch Awerbuch, Yossi Azar, Serge Plotkin
We develop a framework that allows us to address the issues of admission control and routing in high-speed networks under the restriction that once a call is admitted and routed, it has to proceed to...
Adapting to Asynchronous Dynamic Networks (Extended Abstract) (1992)
Baruch Awerbuch, Boaz Patt-shamir, David Peleg, Michael Saks
Baruch Awerbuch Boaz Patt-Shamir y David Peleg z Michael Saks x Abstract The computational power of different communication models is a fundamental question in the theory of distributed computation....
Low-Diameter Graph Decomposition is in NC (1992)
Baruch Awerbuch, Bonnie Berger, Lenore Cowen, David Peleg
We obtain the first NC algorithm for the low-diameter graph decomposition problem on arbitrary graphs. Our algorithm runs in O(log 5 (n)) time, and uses O(n 2 ) processors. 1 Introduction For an...
The maintenance of common data in a distributed system (1991)
Awerbuch, Baruch, Schulman, Leonard J.
A basic task in distributed computation is the maintenance at each processor of the network, of a current and accurate copy of a common database. A primary example is the maintenance, for routing and...
Self-Stabilization By Local Checking and Correction (Extended Abstract) (1991)
Baruch Awerbuch, Boaz Patt-shamir, George Varghese
Baruch Awerbuch Boaz Patt-Shamir y George Varghese z Laboratory for Computer Science Massachusetts Institute of Technology Cambridge, MA 02139 Abstract In this work we introduce the first...
Concurrent Online Tracking of Mobile Users (1991)
This paper deals with the problem of maintaining a distributed directory server, that enables us to keep track of mobile users in a distributed network in the presence of concurrent requests. The...
Concurrent Online Tracking of Mobile Users (1991)
This paper deals with the problem of maintaining a distributed directory server, that enables us to keep track of mobile users in a distributed network in the presence of concurrent requests. The...
Optimal maintenance of replicated information (1990)
Baruch Awerbuch, Israel Cidon, Shay Kutten
"Those who cannot remember the past, are condemned to repeat it. " (Philosopher George Santayana) In this paper we show that keeping track of history enables significant...
A Tradeoff Between Information and Communication in Broadcast Protocols (1990)
Baruch Awerbuch, Oded Goldreich, David Peleg, Ronen Vainish
This paper concerns the message complexity of broadcast in arbitrary point-topoint communication networks. Broadcast is a task initiated by a single processor that wishes to convey a message to all...
Sparse Partitions (Extended Abstract) (1990)
1 ) Baruch Awerbuch David Peleg y Abstract: This abstract presents a collection of clustering and decomposition techniques enabling the construction of sparse and locality preserving representations...
Distributed Control for PARIS (Extended Abstract) (1990)
Baruch Awerbuch, Israel Cidon, Inder Gopal, Marc Kaplan, Shay Kutten
Baruch Awerbuch Israel Cidon y Inder Gopal yz Marc Kaplan yx Shay Kutten y Abstract We describe the control protocols of the PARIS experimental network. This high bandwidth network for integrated...
Locality-Sensitive Resource Allocation (1990)
This paper presents a locality-sensitive controller, governing the supply of demands for a given resource in a way that takes into account the distances between the requesting vertex and the location...
Network Synchronization With Polylogarithmic Overhead (1990)
The synchronizer is a simulation methodology for simulating a synchronous network by an asynchronous one, thus enabling the execution of a synchronous algorithm on an asynchronous network. Previously...
Optimal maintenance of replicated information (1990)
Baruch Awerbuch, Israel Cidon, Shay Kutten
\Those who cannot remember the past, are condemned to repeat it. " (Philosopher George Santayana) In this paper weshowthat keeping track of history enables signi cant improvements in the...
Network Decomposition and Locality in Distributed Computation (Extended Abstract) (1989)
Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, Serge A. Plotkin
) Baruch Awerbuch Department of Mathematics and Laboratory for Computer Science M.I.T. Cambridge, MA 02139 Andrew V. Goldberg y Department of Computer Science Stanford University Stanford, CA 94305...
Compact Distributed Data Structures for Adaptive Routing (1989)
Baruch Awerbuch, Amotz Bar-noy, Nathan Linial, David Peleg
In designing a routing scheme for a communication network it is desirable to use as short as possible paths for routing messages, while keeping the routing information stored in the processors'...
Dynamic Networks are as fast as static networks (Preliminary Version) (1988)
Baruch Awerbuch, Michael Sipser
This paper gives an efficient simulation to show that dynamic networks are as fast as static ones up to a constant multiplicative factor. That is, any task can be performed in a dynamic asynchronous...
Dynamic Networks are as fast as static networks (1988)
Baruch Awerbuch, Michael Sipser
This paper gives an efficient simulation to show that dynamic networks are as fast as static ones up to a constant multiplicative factor. That is, any task can be performed in a dynamic asynchronous...
Local Management of a Global Resource in a Communication Network (1987)
Yehuda Afek Baruch, Baruch Awerbuch, Serge Plotkin, Michael Saks
This paper introduces a new distributed data object called Resource Controller which provides an abstraction for managing the consumption of a global resource in a distributed system. Examples of...
November, 1982 A RELIABLE BROADCAST PROTOCOL (1982)
Adrian Segall, Baruch Awerbuch
Broadcast in a communication network is the delivery of copies of messages to all nodes. A broadcast protocol is reliable if all messages reach all nodes in finite time, in the correct order and with...
A Cost-Benefit Framework for Online Management of a Metacomputing System
Yair Amir, Baruch Awerbuch, R. Sean, R. Sean Borgstrom
Managing a large collection of networked machines, with a series of incoming jobs, requires that the jobs be assigned to machines wisely. A new approach to this problem is presented, inspired by...
A Cost-Benefit Framework For Online Management Of A Metacomputing System
Yair Amir, Baruch Awerbuch, R. Sean Borgstrom
Managing a large collection of networked machines, with a series of incoming jobs, requires that the jobs be assigned to machines wisely. A new approach to this problem is presented, inspired by...
An Opportunity Cost Approach For Job Assignment In A Scalable Computing Cluster
Yair Amir Baruch, Yair Amir, Baruch Awerbuch, Amnon Barak, R. Sean Borgstrom, Arie Keren
. A new method is presented for job assignment to and reassignment between machines in a computing cluster. Our method is based on a theoretical framework that has been experimentally tested and...
Routing Through Teranode Networks with Topology Aggregation
Baruch Awerbuch, Yi Du, Bilal Khan, Yuval Shavitt
The future global teranode networks will consist of many subnetworks called domains. For reasons of both scalability and security, domains will not release details of their internal structure to...
An Opportunity Cost Approach for Job Assignment in a Scalable Computing Cluster
Yair Amir, Baruch Awerbuch, Amnon Barak, R. Sean Borgstrom, Arie Keren
A new method is presented for job assignment to and reassignment between machines in a computing cluster. Our method is based on a theoretical framework that has been experimentally tested and shown...