DMDahlia Malkhi

Dahlia Malkhi

*This is an algorithmically generated author record based on publicly available information.

Dahlia Malkhi has a total of 8 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Optimal Gossip with Direct Addressing

    by Bernhard Haeupler, Dahlia Malkhi

    Gossip algorithms spread information by having nodes repeatedly forward information to a few random contacts. By their very nature, gossip algorithms tend to be distributed and fault tolerant. If done right, they can also be fast and message-efficient. A common model for gossip communication is the random phone call model, in which in each synchronous round each node can PUSH or PULL information to or from a random other node. For example, Karp et al. [FOCS 2000] gave algorithms in this model that spread a message to all nodes in $\Theta(\log n)$ rounds while sending only $O(\log \log n)$ messages per node on average. Recently, Avin and Els\"asser [DISC 2013], studied the random phone call model with the natural and commonly used assumption of direct addressing. Direct addressing allows nodes to directly contact nodes whose ID (e.g., IP address) was learned before. They show that in this setting, one can "break the $\log n$ barrier" and achieve a gossip algorithm running in $O(\sqrt{\log n})$ rounds, albeit while using $O(\sqrt{\log n})$ messages per node. We study the same model and give a simple gossip algorithm which spreads a message in only $O(\log \log n)$ rounds. We also prove a matching $\Omega(\log \log n)$ lower bound which shows that this running time is best possible. In particular we show that any gossip algorithm takes with high probability at least $0.99 \log \log n$ rounds to terminate. Lastly, our algorithm can be tweaked to send only $O(1)$ messages per node on average with only $O(\log n)$ bits per message. Our algorithm therefore simultaneously achieves the optimal round-, message-, and bit-complexity for this setting. As all prior gossip algorithms, our algorithm is also robust against failures. In particular, if in the beginning an oblivious adversary fails any $F$ nodes our algorithm still, with high probability, informs all but $o(F)$ surviving nodes.

  • Efficient distributed approximation algorithms via probabilistic tree embeddings

    by Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan, Kunal Talwar


  • Concise version vectors in WinFS

    by Dahlia Malkhi, Doug Terry


  • Open Access

    Papillon: Greedy Routing in Rings

    by Ittai Abraham, Dahlia Malkhi, Gurmeet Singh Manku

    We study {\sc greedy} routing over $n$ nodes placed in a ring, with the \emph{distance} between two nodes defined to be the clockwise or the absolute distance between them along the ring. Such graphs arise in the context of modeling social networks and in routing networks for peer-to-peer systems. We construct the first network over $n$ nodes in which {\sc greedy} routing takes $O(\log n / \log d)$ hops in the worst-case, with $d$ out-going links per node. Our result has the first asymptotically optimal greedy routing complexity. Previous constructions required $O(\frac{\log^2 n}{d})$ hops.