Randomized greedy hot-potato routing

Costas Busch, Maurice Herlihy, Roger Wattenhofer

Research output: Contribution to conferencePaperpeer-review

16 Scopus citations


We present a novel greedy hot-potato routing algorithm for the 2-dimensional n×n mesh or torus. This algorithm uses randomization to adjust packet priorities. For any permutation problem or random destination problem, it ensures that each packet reaches its destination in asymptotically optimal expected O(n) steps, and all packets reach their destinations in O(n ln n) steps with high probability, an improvement over the previously-known deterministic upper bound of O(n2) for greedy algorithms. For a general batch problem, with high probability all packets reach their destination nodes in at most O(m ln n) steps, where m = min(mr, mc), where mr and mc are respectively the maximum number of packets targeted to a single row or column.

Original languageEnglish (US)
Number of pages9
StatePublished - 2000
Externally publishedYes
Event11th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
Duration: Jan 9 2000Jan 11 2000


Conference11th Annual ACM-SIAM Symposium on Discrete Algorithms
CitySan Francisco, CA, USA

ASJC Scopus subject areas

  • Software
  • Mathematics(all)


Dive into the research topics of 'Randomized greedy hot-potato routing'. Together they form a unique fingerprint.

Cite this