Reuven Cohen, David Ilcinkas, David Peleg
A finite automaton, simply referred to as a robot, has to explore a graph, i.e., visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph or of its size. It...
Reuven Cohen, Pierre Fraigniaud, David Ilcinkas, Amos Korman, David Peleg, David Ilcinkas
This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling...
Theory of Computing Systems (2009)
Shay Kutten, David Peleg, Uzi Vishkin
Abstract. The resource discovery problem was introduced by Harchol-Balter, Leighton, and Lewin. They developed a number of algorithms for the problem in the weakly connected directed graph model....
Abstract The resource discovery problem was introduced by Harchol-Balter, Leighton and Lewin. They developed a number of algorithms for the problem in the weakly connected directed graph model. This...
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
Labeling Schemes for Tree Representation (2009)
Cohen, Reuven, Fraigniaud, Pierre, Ilcinkas, David, Korman, Amos, Peleg, David
This paper deals with compact label-based representations for trees. Consider an $n$-node undirected connected graph $G$ with a predefined numbering on the ports of each node. The {\em all-ports}...
Labeling Schemes for Tree Representation (2009)
Cohen, Reuven, Fraigniaud, Pierre, Ilcinkas, David, Korman, Amos, Peleg, David
This paper deals with compact label-based representations for trees. Consider an $n$-node undirected connected graph $G$ with a predefined numbering on the ports of each node. The {\em all-ports}...
Abstract On the Complexity of Radio Communication (Extended Abstract) (2008)
Noga Alon, Amotz Bar-noy, Nathan Linial, David Peleg
A radio network is a synchronous network of processors that communicate by transmitting messages to their neighbors. A processor receives a message in a given step if and only if it is silent then...
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...
COMPUTINGWITHNOISYINFORMATION* (2008)
Uriel Feiget, Prabhakar Raghavant, David Peleg, Eli Upfal
Abstract. This paper studies the depth of noisy decision trees in which each node gives the wrong answer with some constant probability. In the noisy Boolean decision tree model, tightbounds are...
DOI 10.1007/s00446-005-0127-6 ORIGINAL ARTICLE (2008)
Zvi Lotker, Boaz Patt-shamir, David Peleg
Abstract This paper considers the problem of distributively constructing a minimum-weight spanning tree (MST) for graphs of constant diameter in the bounded-messages model, where each message can...
Labeling Schemes for Tree Representation (2008)
Cohen, Reuven, Fraigniaud, Pierre, Ilcinkas, David, Korman, Amos, Peleg, David
This paper deals with compact label-based representations for trees. Consider an $n$-node undirected connected graph $G$ with a predefined numbering on the ports of each node. The {\em all-ports}...
Label-Guided Graph Exploration by a Finite Automaton (2008)
Cohen, Reuven, Fraigniaud, Pierre, Ilcinkas, David, Korman, Amos, Peleg, David
A finite automaton, simply referred to as a {\em robot}, has to explore a graph, i.e., visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph or of its...
SINR Diagrams: Towards Algorithmically Usable SINR Models of Wireless Networks (2008)
Avin, Chen, Emek, Yuval, Kantor, Erez, Lotker, Zvi, Peleg, David, Roditty, Liam
The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model. For a collection...
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...
Lower Bounds on Broadcasting Time in UDG Radio Networks with Unknown Topology (2008)
Yuval Emek, Erez Kantor, Andrzej Pelc, David Peleg, Chang Su
The paper considers broadcasting in radio networks, modeled as unit disk graphs (UDG). Network stations are modeled as points in the plane, where a station is connected to all stations at Euclidean...
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...
Energy and Time Efficient Broadcasting in Known Topology Radio Networks (2008)
Leszek Gasieniec, Erez Kantor, Dariusz R. Kowalski, David Peleg, Chang Su
Abstract. The paper considers broadcasting protocols in radio networks with known topology that are efficient in both time and energy. The radio network is modelled as an undirected graph G = (V, E)...
Reuven Cohen, David Ilcinkas, David Peleg
A finite automaton, simply referred to as a robot, has to explore a graph, i.e., visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph or of its size. It...
Local Aspects in Distributed Algorithms (2008)
Présentée À, Spécialité Informatique, Pierre Fraigniaud, Directeur Recherche Cnrs, Pierre Fraigniaud, ...
Après avis des rapporteurs:
Labeling Schemes for Weighted Dynamic Trees (Extended Abstract) (2008)
Abstract. This paper studies β-approximate distance labeling schemes, which are composed of a marker algorithm for labeling the vertices of a graph with short labels, coupled with a decoder...
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...
Online Tracking of Mobile Users BARUCH AWERBUCH (2008)
John Shopkinsunilvrsity, David Peleg
Abstract. 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...
THE WAKEUP PROBLEM IN SYNCHRONOUS BROADCAST SYSTEMS ∗ (2008)
Leszek Ga Sieniec, Andrzej Pelc, David Peleg
Abstract. This paper studies the differences between two levels of synchronization in a distributed broadcast system (or a multiple-access channel). In the globally synchronous model, all processors...
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...
Degree-Constrained Subgraph Problems: Hardness and Approximation Results (2008)
Amini, Omid, Peleg, David, Perennes, Stephane, Sau Valls, Ignasi, Saurabh, Saket
A general instance of a Degree-Constrained Subgraph problem consists of an edge-weighted or vertex-weighted graph G and the objective is to find an optimal weighted subgraph, subject to certain...
Degree-Constrained Subgraph Problems: Hardness and Approximation Results (2008)
Amini, Omid, Peleg, David, Perennes, Stephane, Sau Valls, Ignasi, Saurabh, Saket
A general instance of a Degree-Constrained Subgraph problem consists of an edge-weighted or vertex-weighted graph G and the objective is to find an optimal weighted subgraph, subject to certain...
Label-Guided Graph Exploration by a Finite Automaton (2008)
Cohen, Reuven, Fraigniaud, Pierre, Ilcinkas, David, Korman, Amos, Peleg, David
A finite automaton, simply referred to as a {\em robot}, has to explore a graph, i.e., visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph or of its...
Label-Guided Graph Exploration by a Finite Automaton (2008)
Cohen, Reuven, Fraigniaud, Pierre, Ilcinkas, David, Korman, Amos, Peleg, David
A finite automaton, simply referred to as a {\em robot}, has to explore a graph, i.e., visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph or of its...
A near-linear time algorithm for computing replacement paths in planar directed graphs (2008)
Yuval Emek, David Peleg, Liam Roditty
Let G = (V (G), E(G)) be a weighted directed graph and let P be a shortest path from s to t in G. In the replacement paths problem we are required to compute for every edge e in P, the length of a...
SIAM J. DISCRETE MATH c (2007)
Ron Holzman, Yosi Marcus, David Peleg
Abstract. This paper introduces and studies the question of balancing the load on processors participating in a given quorum system. Our proposed measure for the degree of balancing is the ratio...
On the Weak mod m Representation of Boolean Functions (2007)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
one article at a time in L ATEX source form on the Internet. Pagination
Grigni: [3] Tight Bounds on Minimum Broadcast Networks Michelangelo Grigni (2007)
A broadcast graph is an n-vertex communication network that supports a broadcast from any one vertex to all other vertices in optimal time dlg ne, given that each message transmission takes one time...
Directed Virtual Path Layouts in (2007)
Stphane Prenns, Unit Inria, Sophia Antipolis, Jean-claude Bermond, Jean-claude Bermond, Nausica Marlin, ...
apport de recherche
Nausica Marlin, David Peleg, Stéphane Pérennès, Jean-claude Bermond, Jean-claude Bermond, Nausica Marlin Y, ...
apport de recherche Directed Virtual Path Layouts
Cyril Gavoille, David Peleg, Ran Raz
We consider the problem of labeling the nodes of a graph in a way that will allow one to compute the distance between any two nodes directly from their labels (without using any additional...
Distance Labeling in Graphs (Extended Abstract) (2007)
Cyril Gavoille, David Peleg, Stéphane Pérennes, Ran Raz
We consider the problem of labeling the nodes of a graph in a way that will allow one to compute the distance between any two nodes directly from their labels (without using any additional...
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....
The Hardness of Minimum Capacity Network Design (2007)
We define the Minimum Capacity Network Design problem (MCND) and present a taxonomy of its variants. We consider all variants s.t. their input does not admit a general compressed form, and prove that...
Cyril Gavoille, Cyril Gavoille, Michal Katz, Michal Katz, Nir A. Katz, Nir A. Katz, ...
We consider the problem of labeling the nodes of an n-node graph G with short labels in such a way that the distance between any two nodes u; v of G can be approximated eciently (in constant time) by...
Tamar Eilam, Tamar Eilam, Cyril Gavoille, Cyril Gavoille, David Peleg, David Peleg
This paper presents a routing strategy called Pivot Interval Routing (PIR), which allows message routing on every weighted n-node network along paths whose stretch (namely, the ratio between their...
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...
Israel Cidon, Shay Kutten, Yishay Mansour, David Peleg
Scheduling packets to be forwarded over a link is an important subtask of the routing process both in parallel computing and in communication networks. This paper investigates the simple class of...
Prosenjit Bose, Evangelos Kranakis, Christos Kaklamanis, Lefteris M. Kirousis, Danny Krizanc, David Peleg
In wireless communication, the signal of a typical broadcast station is transmitted from a broadcast center p and reaches objects at a distance, say, r from it. In addition there is a radius r0, r0...
The resource discovery problem arises in the context of peer to peer (P2P) networks, where at any point of time a peer may be placed at or removed from any location over a general purpose network...
presents a fast distributed algorithm to compute a small k-dominating set D (for any xed k) and its induced graph partition (breaking the graph into radius k clusters centered around the vertices of...
Deterministic Resource Discovery in Distributed Networks * (2007)
Shay Kutten I, David Peleg, Uzi Vishkin
The resource discovery problem was introduced by Harchol-Balter, Leighton and Lewin. They developed a number of algorithms for the problem in the weakly connected directed graph model. This model is...
The resource discovery problem was introduced by Harchol-Balter, Leighton and Lewin. They developed a number of algorithms for the problem in the weakly connected directed graph model. This model is...
Summary. This survey concerns the role of data structures for compactly storing and representing various types of information in a localized and distributed fashion. Traditional approaches to data...
Cyril Gavoille, Michal Katz, Nir A. Katz, Christophe Paul, David Peleg
Abstract. We consider the problem of labeling the nodes of an n-node graph G with short labels in such a way that the distance between any two nodes u; v of G can be approximated eciently (in...
Generating Sparse 2\Gammaspanners (2007)
A k\Gammaspanner of a connected graph G = (V; E) is a subgraph G 0 consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two...
Cyril Gavoille, David Peleg, Eric Sopena
Abstract. A subset of nodes S in a graph G is called k-dominating if, for every node u of the graph, the distance from u to S is at most k. We consider the parameter k (G) dened as the smallest...
Cyril Gavoille, David Peleg, Eric Sopena
A subset of nodes S in a graph G is called k-dominating if, for every node u of the graph, the distance from u to S is at most k. We consider the parameter k (G) dened as the cardinality of the...
Assigning Labels in an Unknown Anonymous Network with a Leader (2007)
Pierre Fraigniaud, Andrzej Pelc, David Peleg, Stephane Perennes
We consider the task of assigning distinct labels to nodes of an unknown anonymous network in a distributed manner. A priori, nodes do not have any identities, except for one distinguished node,...
Deterministic Resource Discovery in Distributed Networks (2007)
Exte Nd Ed, Shay Kutten, David Peleg
Shay Kutten Technion David Peleg Weizmann Institute Uzi Vishkin Univ. of Maryland & Technion ABSTRACT Leighton and Lewin. They developed a number of algorithms for the problem in the weakly...
Average Stretch Analysis of Compact Routing Schemes (2007)
Tamar Eilam, Cyril Gavoille, David Peleg
This paper presents some analytic results concerning the Pivot Interval Routing (PIR) strategy of [8]. That strategy allows message routing on every weighted n-node network along paths whose stretch...
Dynamic Routing Schemes for Graphs with Low Local Density (2007)
This paper studies approximate distributed routing schemes on dynamic communica-tion networks. The paper focuses on dynamic weighted general graphs where the vertices of the graph are fixed but the...
Yuval Emek, Yuval Emek, David Peleg, Liam Roditty, A Near-linear, Time Algorithm, ...
2004 – present:
Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time (2007)
Bilel Derbel, Cyril Gavoille, David Peleg
The paper presents a deterministic distributed algorithm that given an n node unweighted graph constructs an O(n 3/2) edge 3-spanner for it in O(log n) time. This algorithm is then extended into a...
Local Spreading Algorithms for Autonomous Robot Systems (2007)
This paper studies local algorithms for autonomous robot systems, namely, algorithms that use only information of the positions of a bounded number of their nearest neighbors. The paper focuses on...
Local Spreading Algorithms for Autonomous Robot Systems (2007)
Abstract This paper studies local algorithms for autonomous robot systems, namely, algorithms thatuse only information of the positions of a bounded number of their nearest neighbors. The paper
Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements (2006)
Anumber of recent studies concern algorithms for distributed control and coordination in systems of autonomous mobile robots. The common theoretical model adopted in these studies assumes that the...
Constructing Labeling schemes through Universal Matrices (2006)
Amos Korman, David Peleg, Yoav Rodeh
Abstract. Let f be a function on pairs of vertices. An f-labeling scheme for a family of graphs F labels the vertices of all graphs in F such that for every graph G ∈ F and every two vertices u, v...
A tight upper bound on the probabilistic embedding of seriesparallel graphs (2006)
In [EEST05] it is shown that every graph can be probabilistically embedded into a distribution over its spanning trees with expected distortion O(log 2 n log log n), narrowing the gap left by...
Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements (2006)
Abstract. The common theoretical model adopted in recent studies on algorithms for systems of autonomous mobile robots assumes that the positional input of the robots is obtained by perfectly...
Improved approximation for min-sum vertex cover (2006)
Uri Barenholz, Uriel Feige, David Peleg
The paper describes an approximation algorithm for the Min Sum Vertex Cover (MSVC) problem, achieving a constant approximation factor strictly smaller than 2, thus improving on the best currently...
C.: Upper Bounds on Broadcasting Time in UDG Radio Networks with Unknown Topology (2006)
Yuval Emek, Erez Kantor, Andrzej Pelc, David Peleg, Chang Su
The paper considers broadcasting in radio networks, modeled as unit disk graphs (UDG). Network stations are modeled as points in the Euclidean plane, where a station is connected to all stations at...
Convergence of Autonomous Mobile Robots With Inaccurate Sensors and Movements (2006)
A number of recent studies concern algorithms for distributed control and coordination in systems of autonomous mobile robots. The common theoretical model adopted in these studies assumes that the...
Labeling Schemes for Tree Representation (2005)
Cohen, Reuven, Fraigniaud, Pierre, Ilcinkas, David, Korman, Amos, Peleg, David
This paper deals with compact label-based representations for trees. Consider an $n$-node undirected connected graph $G$ with a predefined numbering on the ports of each node. The {\em all-ports}...
Label-Guided Graph Exploration by a Finite Automaton (2005)
Cohen, Reuven, Fraigniaud, Pierre, Ilcinkas, David, Korman, Amos, Peleg, David
A finite automaton, simply referred to as a {\em robot}, has to explore a graph, i.e., visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph or of its...
Labeling Schemes for Tree Representation (2005)
Cohen, Reuven, Fraigniaud, Pierre, Ilcinkas, David, Korman, Amos, Peleg, David
This paper deals with compact label-based representations for trees. Consider an $n$-node undirected connected graph $G$ with a predefined numbering on the ports of each node. The {\em all-ports}...
Label-Guided Graph Exploration by a Finite Automaton (2005)
Cohen, Reuven, Fraigniaud, Pierre, Ilcinkas, David, Korman, Amos, Peleg, David
A finite automaton, simply referred to as a {\em robot}, has to explore a graph, i.e., visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph or of its...
Graph Exploration by a Finite Automaton (2005)
Fraigniaud, Pierre, Ilcinkas, David, Peer, Guy, Pelc, Andrzej, Peleg, David
A finite automaton, simply referred to as a {\em robot}, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of...
Graph Exploration by a Finite Automaton (2005)
Fraigniaud, Pierre, Ilcinkas, David, Peer, Guy, Pelc, Andrzej, Peleg, David
A finite automaton, simply referred to as a {\em robot}, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of...
Amos Korman, Shay Kutten, David Peleg
This paper addresses the problem of locally verifying global properties. Several natural questions are studied, such as “how expensive is local verification? ” and more specifically “how...
Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds (2005)
Zvi Lotker, Boaz Patt-shamir, Elan Pavlov, David Peleg
Abstract. We consider a simple model for overlay networks, where all n processes are connected to all other processes, and each message contains at most O(log n) bits. For this model, we present a...
Reuven Cohen, Amos Korman, Pierre Fraigniaud, David Peleg, David Ilcinkas
This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling...
Reuven Cohen, Amos Korman, Pierre Fraigniaud, David Peleg, David Ilcinkas
This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling...
Graph Exploration by a Finite Automaton (2005)
Reuven Cohen, Pierre Fraigniaud, David Ilcinkas, Amos Korman, David Peleg
A finite automaton, simply referred to as a robot, has to explore a graph, i.e., visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph or of its size. It...
Exploration par un automate fini de réseaux anonymes étiquetés (2005)
Cohen, Reuven, Fraigniaud, Pierre, Ilcinkas, David, Korman, Amos, Peleg, David
Cet article traite de l'exploration d'un réseau par un agent mobile, ou {\em robot}, modélisé par un automate fini. Le robot ne dispose pas de connaissances préalables sur la topologie du...
Exploration par un automate fini de réseaux anonymes étiquetés (2005)
Cohen, Reuven, Fraigniaud, Pierre, Ilcinkas, David, Korman, Amos, Peleg, David
Cet article traite de l'exploration d'un réseau par un agent mobile, ou {\em robot}, modélisé par un automate fini. Le robot ne dispose pas de connaissances préalables sur la topologie du...
Graph Exploration by a Finite Automaton (2004)
Fraigniaud, Pierre, Ilcinkas, David, Peer, Guy, Pelc, Andrzej, Peleg, David
A finite automaton, simply referred to as a {\em robot}, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of...
Graph Exploration by a Finite Automaton (2004)
Fraigniaud, Pierre, Ilcinkas, David, Peer, Guy, Pelc, Andrzej, Peleg, David
A finite automaton, simply referred to as a {\em robot}, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of...
Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems (2004)
This paper considers the convergence problem in autonomous mobile robot systems. A natural algorithm for the problem requires the robots to move towards their center of gravity. Previously it was...
Approximating minimum max-stretch spanning trees on unweighted graphs (2004)
Given a graph G and a spanning tree T of G, we say that T is a tree t-spanner of G if the distance between every pair of vertices in T is at most t times their distance in G. The problem of finding a...
This paper concerns the range assignment problem in static ad-hoc networks on metric spaces. We focus on the bounded-hop strong-connectivity problem (hSC) on general metric spaces for constant h....
Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems (2004)
Abstract. This paper considers the convergence problem in autonomous mobile robot systems. A natural algorithm for the problem requires the robots to move towards their center of gravity. This paper...
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...
Exploration de réseaux par un robot (2004)
Fraigniaud, Pierre, Ilcinkas, David, Peer, Guy, Pelc, Andrzej, Peleg, David
Cet article traite de l'exploration d'un réseau par un agent mobile, ou {\em robot}, modélisé par un automate fini. Le réseau est anonyme, au sens que les nœuds ne disposent pas nécessairement...
Exploration de réseaux par un robot (2004)
Fraigniaud, Pierre, Ilcinkas, David, Peer, Guy, Pelc, Andrzej, Peleg, David
Cet article traite de l'exploration d'un réseau par un agent mobile, ou {\em robot}, modélisé par un automate fini. Le réseau est anonyme, au sens que les nœuds ne disposent pas nécessairement...
Labeling Schemes for Weighted Dynamic Trees (2003)
A Distance labeling scheme is a type of localized network representation in which short labels are assigned to the vertices, allowing one to infer the distance between any two vertices directly from...
Compact and localized distributed data structures (2003)
Cyril Gavoille, Cyril Gavoille, David Peleg, David Peleg
This survey concerns the role of data structures for compactly storing and representing various types of information in a localized and distributed fashion. Traditional approaches to data...
Hotlink enhancement algorithms for web directories (2003)
Ori Gerstel, Shay Kutten, Rachel Matichin, David Peleg
This paper proposes an approach for reducing the search e#ort of a user possessing limited a-priori information, in data arranged hierarchically such as in Yahoo or the Open Directory Project....
Christoph Ambühl, Miriam Di Ianni, Nissan Lev-tov, Angelo Monti, David Peleg, ...
The paper studies the problem of computing a minimal energy cost range assignment in an ad-hoc...
Processor Renaming in Asynchronous Environments. (2002)
Fischer, Lynch and Paterson FLP proved that in a completely asynchronous system weak agreement cannot be achieved even in the presence of a single benign fault. Following the direction proposed in...
Noga Alon, Nathan Linial, Amotz Bar-noy, David Peleg
A radio network is a synchronous network of processors that communicate by trans-mitting messages to their neighbors. A processor receives a message in a given step if and only if it is silent then...
Labeling Schemes for Dynamic Tree Networks (2002)
Amos Korman, David Peleg, Yoav Rodeh
Distance labeling schemes are composed of a marker algorithm for labeling the vertices of a graph with short labels, coupled with a decoder algorithm allowing one to compute the distance between any...
Asynchronous Resource Discovery in Peer to Peer Networks (2002)
The resource discovery problem arises in the context of peer to peer (P2P) networks, where at any point of time a peer may be placed at or removed from any location over a general purpose network...
Distributed MST for Constant Diameter Graphs (2001)
Zvi Lotker, Boaz Patt-shamir, David Peleg
This paper considers the problem of distributively constructing a minimum-weight spanning tree (MST) for thatÇÐÓ�Ò graphs of constant diameter in the bounded-messages model, where each message...
Approximating k-spanner problems for k > 2 (2001)
Given a graph G = (V, E), a subgraph G ′ = (V, H), H ⊆ E is a k-spanner of G if for any pair of vertices u, w ∈ V it satisfies dH(u, w) ≤ k · dG(u, w). The basic k-spanner problem is to find...
Small k-dominating sets in planar graphs with applications (2001)
Cyril Gavoille, David Peleg, Eric Sopena, Eric Sopena
k-Dominating
Small k-dominating sets in planar graphs with applications (2001)
Cyril Gavoille, David Peleg, Eric Sopena
Abstract. A subset of nodes S in a graph G is called k-dominating if, for every node u of the graph, the distance from u to S is at most k. We consider the parameter k (G) dened as the cardinality of...
Distributed MST for Constant Diameter Graphs (2001)
Zvi Lotker, Boaz Patt-shamir, David Peleg
This paper considers the problem of distributively constructing a minimum-weight spanning tree (MST) for graphs of constant diameter in the bounded-messages model, where each message can contain at...
The hardness of approximating spanner problems (2000)
Abstract This paper examines a number of variants of the sparse k-spanner problem, and presents hardnessresults concerning their approximability. Previously, it was known that most k-spanner...
Deterministic distributed resource discovery (2000)
y The resource discovery problem was introduced by Harchol-Balter, Leighton and Lewin. They developed a randomized algorithm (for Akamai Technologies) for the problem in the weakly connected directed...
Distance Labeling in Graphs (2000)
Cyril Gavoille, Davod Peleg, Cyril Gavoille, David Peleg, David Peleg, Ran Raz, ...
We consider the problem of labeling the nodes of a graph in a way that will allow one to compute the distance between any two nodes directly from their labels (without using any additional...
Assigning Labels in Unknown Anonymous Networks (2000)
Pierre Fraigniaud, Andrzej Pelc, David Peleg, Stéphane Pérennes
We consider the task of distributedly assigning distinct labels to nodes of an unknown anonymous network. A priori, nodes do not have any identities (anonymous network) and do not know the topology...
The wakeup problem in synchronous broadcast systems (Extended Abstract) (2000)
L. Gasieniec, Leszek Gasieniec, Andrzej Pelc, David Peleg
] Leszek Gasieniec Department of Computer Science, The University of Liverpool, Liverpool L69 7ZF, United Kingdom. leszek@csc.liv.ac.uk Andrzej Pelc y D epartement d'Informatique, Universit e du...
Assigning labels in unknown anonymous networks (2000)
Pierre Fraigniaud, Andrzej Pelc, David Peleg
We consider the task of distributedly assigning distinct la-bels to nodes of an unknown anonymous network. A priori, nodes do not have any identities (anonymous network) and do not know the topology...
Directed Virtual Path Layouts in ATM Networks (1999)
Bermond, Jean-Claude, Marlin, Nausica, Peleg, David, Pérennès, Stéphane
Motivated by Asynchronous Transfer Mode (ATM) in telecommunication networks, we investigate the problem of designing a directed virtual topology on a directed physical topology, which consists in...
Directed Virtual Path Layouts in ATM Networks (1999)
Bermond, Jean-Claude, Marlin, Nausica, Peleg, David, Pérennès, Stéphane
Motivated by Asynchronous Transfer Mode (ATM) in telecommunication networks, we investigate the problem of designing a directed virtual topology on a directed physical topology, which consists in...
Directed Virtual Path Layouts in ATM Networks (1999)
Bermond, Jean-Claude, Marlin, Nausica, Peleg, David, Pérennès, Stéphane
Motivated by Asynchronous Transfer Mode (ATM) in telecommunication networks, we investigate the problem of designing a directed virtual topology on a directed physical topology, which consists in...
Station layouts in the presence of location constraints (1999)
Prosenjit Bose, Christos Kaklamanis, Lefteris M. Kirousis, Danny Krizanc, David Peleg
Bubbles: Adaptive routing scheme for high-speed dynamic networks (1999)
Shlomi Dolev, Evangelos Kranakis, Danny Krizanc, David Peleg
This paper presents the first dynamic routing scheme for high-speed networks. The scheme is based on a hierarchical bubbles partition of the underlying communication graph. Dynamic routing schemes...
Approximating the weight of shallow steiner trees (1999)
This paper deals with the problem of constructing Steiner trees of minimum weight with diameter bounded by d, spanning a given set of vertices in a graph. Exact solutions or logarithmic ratio...
A survey on interval routing (1999)
Cyril Gavoille, Cyril Gavoille, David Peleg, David Peleg
The compactness of a graph measures the space complexity of its shortest path routing tables. Each outgoing edge of a node x is assigned a (pairwise disjoint) set of addresses, such that the unique...
The Compactness of Interval Routing for Almost All Graphs (1999)
Interval routing is a compact way for representing routing tables on a graph. It is based on grouping together, in each node, destination addresses that use the same outgoing edge in the routing...
Virtual path layouts with low congestion or low diameter in ATM networks (1999)
Jean-claude Bermond, Nausica Marlin, David Peleg
Motivated by Asynchronous Transfer Mode (ATM) in telecommunication networks, we investigate the problem of designing a directed virtual topology on a directed physical topology, which consists in...
Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks (1999)
Extend Ed, Shlomi Dolev, Evangelos Kranakis, Danny Krizanc, David Peleg
) Shlomi Dolev Evangelos Kranakis y Danny Krizanc y David Peleg z Abstract This paper presents the first dynamic routing scheme for high-speed networks. The scheme is based on a hierarchical bubbles...
A near-tight lower bound on the time complexity of distributed MST construction (1999)
David Peleg, Vitaly Rubinovich
Abstract. This paper presents a lower boundof Ω(D + √ n / log n) on the time requiredfor the distributed construction of a minimum-weight spanning tree (MST) in weighted n-vertex networks of...
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,...
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...
A sub-linear time distributed algorithm for minimum-weight spanning trees (1998)
Juan A. Garay, Shay Kutten, David Peleg
This paper considers the question of identifying the parameters governing the behavior of fundamental global network problems. Many papers on distributed network algorithms consider the task of...
The compactness of interval routing for almost all graphs (1998)
Interval routing is a compact way for representing routing tables on a graph. It is based on grouping together, in each node, destination addresses that use the same outgoing edge in the routing...
The compactness of interval routing for almost all graphs (1998)
Cyril Gavoille, Cyril Gavoille, David Peleg, David Peleg
Interval routing is a compact way for representing routing tables on a graph. It is based on grouping together, in each node, destination addresses that use the same outgoing edge in the routing...
Compact routing schemes with low stretch factor (1998)
Tamar Eilam, Cyril Gavoille, David Peleg
This paper presents a routing strategy called Pivot Interval Routing (PIR), which allows message routing on every weighted n-node network along paths whose stretch (namely, the ratio between their...
Directed Virtual Path Layouts in ATM Networks (1998)
Jean-Claude Bermond, Nausica Marlin, David Peleg, Stéphane Perennes
Motivated by Asynchronous Transfer Mode (ATM) in telecommunication networks, we investigate the problem of designing a directed virtual topology on a directed physical topology, which consists in...
The Compactness of Interval Routing for Almost All Graphs (1998)
. Interval routing is a compact way for representing routing tables on a graph. It is based on grouping together, in each node, destination addresses that use the same outgoing edge in the routing...
Directed Virtual Path Layouts in ATM Networks (Extended Abstract) (1998)
Jean-Claude Bermond, Nausica Marlin, David Peleg, Stéphane Perennes
This article investigates the problem of designing virtual dipaths (VPs) in a directed ATM model, in which the flow of information in the two directions of a link are not identical. On top of a given...
The Compactness of Interval Routing for Almost All Graphs (1998)
Cyril Gavoille, Cyril Gavoille, David Peleg, David Peleg
Interval routing is a compact way for representing routing tables on a graph. It is based on grouping together, in each node, destination addresses that use the same outgoing edge in the routing...
Compact Routing Schemes With Low Stretch Factor (1998)
Extend Ed, Tamar Eilam, Cyril Gavoille, David Peleg
) Tamar Eilam Cyril Gavoille y David Peleg z January 8, 1998 Abstract This paper presents a routing strategy called Pivot Interval Routing (PIR), which allows message routing on every weighted n-node...
Directed Virtual Path Layouts in ATM networks (1998)
Jean-claude Bermond, Nausica Marlin, David Peleg
Motivated by Asynchronous Transfer Mode (ATM) in telecommunication networks, we investigate the problem of designing a directed virtual topology on a directed physical topology, which consists in...
Square Meshes are not Always Optimal, (1997)
In this paper we consider mesh connected computers with multiple buses, providing broadcast facilities along rows and columns. A tight bound of theta(n(1/2)) is established for the number of rounds...
The Dense k-subgraph problem (1997)
Uriel Feige, Guy Kortsarz, David Peleg
This paper considers the problem of computing the dense k-vertex subgraph of a given graph, namely, the subgraph with the most edges. An approximation algorithm is developed for the problem, with...
The Compactness of Interval Routing (1997)
The compactness of a graph measures the space complexity of its shortest path routing tables. Each outgoing edge of a node x is assigned a (pairwise disjoint) set of addresses, such that the unique...
How to be an efficient snoop, or the probe complexity of quorum systems (1996)
Abstract. A quorum system is a collection of sets (quorums) every two of which intersect. Quorum systems have been used for many applications in the area of distributed systems, including mutual...
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...
Fault-local distributed mending (1995)
As communication networks grow, existing fault handling tools that involve global measures such as global time-outs or reset procedures become increasingly unaffordable, since their cost grows with...
This paper lays a theoretical foundation for scaling fault tolerant tasks to large and diversified networks, such as the Internet. In such networks, there are always parts of the network that failed....
Approximation algorithms for minimum time broadcast (1995)
This paper deals with the problem of broadcasting in minimum time in the telephone and message-passing models. Approximation algorithms are developed for arbitrary graphs, as well as for several...
A Graph-Theoretic Game and its Application to the k-Server Problem (1995)
Noga Alon, Richard M. Karp, David Peleg, Douglas West
This paper investigates a zero-sum game played on a weighted connected graph G between two players, the tree player and the edge player. At each play, the tree player chooses a spanning tree T and...
Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, David Peleg
A function is distributed among nodes of a graph in a continuous way, i.e., such that the difference between values stored at adjacent nodes is small. The goal is to find a node of maximum value by...
Symmetric Logspace is Closed Under Complement (1995)
Noam Nisan, Abadi Greg, Frederickson John Mitchell, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 st connectivity problem to its complement. This shows that SL = coSL. 1 Introduction This paper deals with the complexity...
On the Weak mod m Representation of Boolean Functions (1995)
Vince Grolmusz, Abadi Greg, Frederickson John Mitchell, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, ...
Let P be a polynomial over the ring of mod m integers. P weakly represents Boolean function f : f0; 1g n ! f0; 1g if there is a subset S ` f0; 1; : : : ; m \Gamma 1g such that f(x) = 0 if and only if...
Crumbling Walls: A Class of High Availability Quorum Systems (1995)
A quorum system is a collection of sets (quorums) every two of which have a nonempty intersection. Quorum systems have been used for a number of applications in the area of distributed systems. The...
Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks (Extended Abstract) (1995)
Shlomi Dolev, Evangelos Kranakis, Danny Krizanc, David Peleg
) Shlomi Dolev Evangelos Kranakis y Danny Krizanc y David Peleg z Abstract This paper presents the first dynamic routing scheme for high-speed networks. The scheme is based on a hierarchical bubbles...
Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions (1995)
Pankaj Agarwal, Joan Feigenbaum, Carsten Lund, Andrew Goldberg, Ketan Mulmuley, ...
We initiate an investigation of probabilistically checkable debate systems (PCDS), a natural generalization of probabilistically checkable proof systems (PCPS). A PCDS for a language L consists of a...
Nils Klarlund, Dexter Kozen, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, ...
Rabin conditions are a general class of properties of infinite sequences that encompass most known automata-theoretic acceptance conditions and notions of fairness. In this paper, we introduce a...
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...
Symmetric Logspace is Closed under Complement (1995)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 s--t connectivity problem to its complement. This shows that SL = coSL.
Greedy packet scheduling (1995)
Israel Cidon, Shay Kutten, Yishay Mansour, David Peleg
Scheduling packets to be forwarded over a link is an important subtask of the routing process both in paxalhl computing and in communication networks. This paper investigates the simple class of...
[ii] Chicago Journal of Theoretical Computer Science 1995-3Rabin Measures (1995)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
Published one article at a time in LATEX source form on the Internet. Pagination
Recovery of ovarian function after laparoscopic detorsion (1995)
Shalev, Eliezer, Bustan, Moshe, Yarom, Ilan, Peleg, David
In an attempt to preserve ovarian function, we managed 58 women with adnexal torsion by laparoscopic detorsion. Follow-up ultrasound examinations were performed on 54 of the women. Follicular...
An approximation algorithm for minimum-cost network design (1994)
This paper considers the problem of designing a minimum cost network meeting a given set of traffic requirements between n sites, using one type of channels of a given capacity, with varying set-up...
Fault-Local Distributed Mending (1994)
As communication networks grow, existing fault handling tools that involve global measures such as global time-outs or reset procedures become increasingly unaffordable, since their cost grows with...
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'...
How to allocate network centers (1993)
Judit Bar-ilan, Guy Kortzars, David Peleg
This paper deals with the issue of allocating and utilizing centers in a distributed network, in its various forms. The paper discusses the significant parameters of center allocation, defines the...
Time-Space Tradeoffs for Set Operations (1993)
This paper considers time-space tradeoffs for various set operations. Denoting the time requirement of an algorithm by T and its space requirement by S, it is shown that TS =\Omega (n 2 ) for set...
The Availability of Quorum Systems (1993)
A quorum system is a collection of sets (quorums) every two of which have a nonempty intersection. Quorum systems have been used for a number of applications in the area of distributed systems. In...
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...
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...
Generating Low-Degree 2-Spanners (1993)
A k\Gammaspanner of a connected graph G = (V; E) is a subgraph G 0 consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two...
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...
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...
Tight Bounds on Minimum Broadcast Networks (1991)
Michelangelo Grigni, David Peleg
A broadcast graph is an n-vertex communication network that supports a broadcast from any one vertex to all other vertices in optimal time dlg ne, given that each message transmission takes one time...
A Graph-Theoretic Game and its Application to the k-Server Problem (Extended Abstract) (1991)
Noga Alon, Richard M. Karp, David Peleg
) Noga Alon Richard M. Karp y David Peleg z Douglas West x July 11, 1991 Abstract This paper investigates a zero-sum game played on a weighted connected graph G between two players, the tree player...
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...
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...
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...
Greedy Packet Scheduling (1990)
Israel Cidon, Shay Kutten, Yishay Mansour, David Peleg
Scheduling packets to be forwarded over a link is an important subtask of the routing process both in parallel computing and in communication networks. This paper investigates the simple class of...
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'...
A radio network is a synchronous network of processors that communicate by transmitting messages to their neighbors, where a processor receives a message in a given step if and only if it is silent...
Christos Kaklamanis, Lefteris M. Kirousis, Danny Krizanc, David Peleg
Abstract. In wireless communication, the signal of a typical broadcast station is transmited from a broadcast center p and reaches objects at a distance, say, R from it. In addition there is a radius...