## Abstract

The purpose of compact routing is to provide a labeling of the nodes of a network, and a way to encode the routing tables so that routing can be performed efficiently (e.g., on shortest paths) while keeping the memory-space required to store the routing tables as small as possible. In this paper, we answer a long-standing conjecture by showing that compact routing can also help to perform distributed computations. In particular, we show that a network supporting a shortest path interval routing scheme allows to broadcast with an O(n) message-complexity, where n is the number of nodes of the network. As a consequence, we prove that O(n) messages suffice to solve leader-election for any graph labeled by a shortest path interval routing scheme, improving therefore the O(m + n) previous known bound.

Original language | English |
---|---|

Title of host publication | Proceedings of the Annual ACM Symposium on Principles of Distributed Computing |

Place of Publication | New York |

Publisher | ACM |

Pages | 11-20 |

Number of pages | 10 |

ISBN (Print) | 1581131836 |

DOIs | |

Publication status | Published - 2000 |

Externally published | Yes |

Event | 19th Annual ACM Symposium on Principles of Distributed Computing - Portland, OR, USA Duration: 16 Jul 2000 → 19 Jul 2000 |

### Other

Other | 19th Annual ACM Symposium on Principles of Distributed Computing |
---|---|

City | Portland, OR, USA |

Period | 16/07/00 → 19/07/00 |