人口協定中的資訊收集問題

Abstract

人口協定（Population Protocols）是一種理論上的分散式計算模型，著重於不可區分且匿名的運算單元之間的隨機互動。有別於傳統的人口協定，我們探討一種情境：每個運算單元都持有一筆唯一且不可變的資料，目標是在僅使用有限儲存空間的情況下，每筆資料皆被所有運算單元讀取與處理一次。我們在兩種網路拓撲下探討此問題：完全圖與環狀圖。在完全圖中，我們設計了一種以輪次為基礎的協定，使得所有運算單元能以每人使用 k 個額外儲存空間的方式，精確地處理所有資料。此協定在高機率下能於 O(n log n/k) 平行時間內完成，實現時間與空間間的可調節折衷。在環狀拓撲中，我們提出一種決定性協定，運用著色與令牌傳遞機制。儘管環狀結構的連通性有限，此協定仍能保證每個運算單元皆精確處理所有資料，並在高機率下於 O(n log n) 平行時間內完成，且僅需一個額外儲存空間。此結果達成漸近最優的空間複雜度與近似最優的時間複雜度。

Population protocols [3] are a theoretical model of distributed computation that emphasize random interactions among indistinguishable, anonymous agents. Unlike conventional population protocols, we consider a setting in which each agent holds a unique, immutable data value and aims to read and process all such values exactly once while storing only a limited number of them. We address this problem under two network topologies: the complete graph and the ring. In the complete graph, we present a round-based protocol that enables all agents to process each data value exactly once, using only k additional storage slots per agent. The protocol completes in O(n log n/k)parallel time with high probability, achieving a tunable trade-off between time and space. In the ring topology, we propose a deterministic protocol utilizing a coloring and token-passing mechanism. Despite the limited connectivity of the ring structure, our protocol guarantees that each agent processes all unique data values exactly once, completing in O(n log n) parallel time with high probability using only one additional storage slot per agent. This achieves asymptotically optimal space complexity and nearly optimal time complexity.