RAPAPORT , Ivan

Efficient algorithms for computing routing tables should take advantage of the particular properties arising in large scale networks. Two of them are of particular interest: low (logarithmic) diameter and high clustering coefficient. High clustering coefficient implies the existence of few large induced cycles. Considering this fact, we propose...

We propose a simple interval routing scheme for a graph $G$, based on a Maximal Neighborhood BFS-tree $T$ of $G$. In our scheme a message simply follows the source-destination path in $T$ but, in at most one step, it may take a shortcut. This shortcut is taken when the current node has a neighbor in $G$ which is an ancestor in $T$ of the...

In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed and streaming way. When computing graph-theoretic...

In this work we study the computational power of graph-based models of distributed computing in which each node additionally has access to a global whiteboard. A node can read the contents of the whiteboard and, when activated, can write one message of $O(\log n)$ bits on it. A message is only based on the local knowledge of the node and the...

Nous étudions quelles propriétés d'un réseau peuvent être calculées à partir d'une petite quantité d'informations locales fournie par ses noeuds. Notre modèle est une restriction de CONGEST, un modèle distribué classique. Il est proche du modèle de complexité de communication avec messages simultanés de Babai et al. Chacun des n noeuds --qui ne...

In this paper we ask which properties of a distributed network can be computed from a few amount of local information provided by its nodes. The distributed model we consider is a restriction of the classical CONGEST (distributed) model and it is close to the simultaneous messages (communication complexity) model defined by Babai, Kimmel and...

In this paper we ask which properties of a distributed network can be computed from a few amount of local information provided by its nodes. The distributed model we consider is a restriction of the classical CONGEST (distributed) model and it is close to the simultaneous messages (communication complexity) model defined by Babai, Kimmel and...

In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed way. When computing graph-theoretic properties, nodes...