{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihzau4vut3xjflevywyenfl44zlictzfmuyhy2tkzmqnp3rxgfwru",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mgw2qf7pzqc2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.12156v1",
  "publishedAt": "2026-03-13T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Michael Elkin Tanya Goldenfeld"
  ],
  "textContent": "**Authors:** Michael Elkin Tanya Goldenfeld\n\nMemory-(in)efficiency is a crucial consideration that oftentimes prevents deployment of state-of-the-art distributed algorithms in real-life modern networks. In the context of the MST problem, roughly speaking, there are three types of algorithms. The algorithm of Gallager-Humblet-Spira and its versions are memory- and message- efficient, but their running time is at least linear in the number of vertices $n$, even when the unweighted diameter $D$ is much smaller than $n$. The algorithm of Garay-Kutten-Peleg and its versions are time-efficient, but not message- or memory-efficient. The more recent algorithms of are time- and message-efficient, but are not memory-efficient. As a result, GHS-type algorithms are much more prominent in real-life applications than time-efficient ones. In this paper we develop a deterministic time-, message- and memory-efficient algorithm for the MST problem. It is also applicable to the more general partwise aggregation problem. We believe that our techniques will be useful for devising memory-efficient versions for many other distributed problems.",
  "title": "Time, Message and Memory-Optimal Distributed Minimum Spanning Tree and Partwise Aggregation"
}