目錄
1. 緒論
代理式分散式計算模型透過引入可在節點間移動以進行通訊的移動計算裝置（代理），擴展了傳統的訊息傳遞模式。本文針對 k ≤ n 個代理的情境，首次對該模型中的圖層級任務進行全面研究，探討具有最佳化時間與記憶體複雜度的領導者選舉與最小生成樹建構問題。
2. 代理式模型基礎
代理式模型代表從靜態計算裝置到移動計算裝置的典範轉移，其中代理必須實體移動才能進行通訊，而非透過固定鏈路發送訊息。
2.1 模型比較
表1比較了訊息傳遞模型與代理式模型的基本特性：
| 模型 | 裝置 | 本地計算 | 裝置儲存 | 鄰居通訊 |
|---|---|---|---|---|
| 訊息傳遞 | 靜態 | 無限制 | 無限制 | 訊息 |
| 代理式 | 移動 | 無限制 | 有限 | 重新定位 |
2.2 關鍵差異
代理式模型引入了兩個主要差異：(1) 計算裝置是移動的而非靜態的，(2) 通訊需要實體移動至同一節點而非訊息傳輸。
3. 領導者選舉演算法
本文提出了兩種針對不同代理與節點比例進行最佳化的確定性領導者選舉演算法。
3.1 情況 k < n
針對代理數量少於節點數量的情境，該演算法實現了 $O(D + \sqrt{n})$ 的時間複雜度，其中 D 是圖的直徑，記憶體複雜度則針對移動代理的限制進行了最佳化。
3.2 情況 k = n
當每個節點都包含一個代理時，該演算法基於先前在 DISC 2024 中發表的研究成果，實現了最佳的 $O(D)$ 時間複雜度。
4. 最小生成樹建構
利用領導者選舉的結果，作者開發了確定性演算法，使代理能夠建構圖的最小生成樹。該方法在將傳統 MST 演算法（如 Borůvka 或 Prim 演算法）適應代理式模型限制的同時，最小化了時間與記憶體複雜度。
5. 技術分析
5.1 數學框架
代理式模型可以形式化定義為一個元組 $G = (V, E, A)$，其中 V 代表節點，E 代表邊，A 代表移動代理。通訊限制要求代理 $a_i$ 和 $a_j$ 必須共同位於某個節點 $v \in V$ 才能交換資訊，這從根本上改變了訊息傳遞的成本模型。
5.2 實驗結果
雖然本文側重於理論分析，但與傳統方法相比，這些演算法在記憶體使用方面展現了顯著的改進。時間複雜度結果表明，儘管存在通訊限制，代理式演算法在基礎圖問題上仍能實現與訊息傳遞相當的效能。
6. 分析框架範例
核心洞見： 代理式模型不僅僅是學術演練，它是對分散式計算的根本性重新思考，反映了現實世界系統（如機器人網路和物聯網部署），其中實體移動實現了通訊。與傳統的靜態網路假設相比，這為新興的邊緣計算典範提供了更現實的模型。
邏輯流程： 本文從建立模型的理論基礎到解決基礎圖問題，進行了系統性的建構。從領導者選舉到 MST 建構的進展，展示了基本原語如何實現更複雜的操作，類似於傳統分散式演算法的演進過程。
優勢與缺陷： 主要優勢在於解決了 k < n 的實際限制，這反映了並非每個節點都具備計算能力的真實部署情境。然而，同步假設和無限制的本地計算是顯著的限制——真實的移動系統面臨非同步操作和計算限制。與開創性研究（如 Zhu 等人於 2017 年發表、革新領域轉換的 CycleGAN 論文）相比，本研究奠定了基礎但缺乏實證驗證。
可行洞見： 研究人員應優先將這些結果擴展到非同步環境，並在實體測試平台中進行驗證。機器人技術和物聯網的業界從業者在設計需要實體鄰近性才能通訊的系統時，應考慮代理式模型，因為它比傳統模型提供了更準確的複雜度界限。
7. 未來應用與方向
代理式模型在以下幾個領域具有巨大潛力：
- 機器人網路： 群體機器人技術，其中機器人必須實體會面以交換數據
- 邊緣計算： 透過實體鄰近性進行通訊的移動邊緣裝置
- 災難應變： 基礎設施受損的緊急網路
- 太空探索： 需要會合以進行資料傳輸的行星探測車
未來研究應側重於將模型擴展到非同步環境、納入能量限制，以及開發超越領導者選舉和 MST 的更複雜任務的演算法。
8. 參考文獻
- Kshemkalyani, A. D., Kumar, M., Molla, A. R., & Sharma, G. (2024). Brief Announcement: Agentic Distributed Computing. Proceedings of DISC 2024.
- Zhu, J. Y., Park, T., Isola, P., & Efros, A. A. (2017). Unpaired Image-to-Image Translation using Cycle-Consistent Adversarial Networks. Proceedings of the IEEE international conference on computer vision.
- Lynch, N. A. (1996). Distributed Algorithms. Morgan Kaufmann.
- Peleg, D. (2000). Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics.