Compact Deterministic Distributed Dictionaries
K. Gilon, David Peleg · 1993
This paper handles the problem of designing a deterministic dictionary structure in a distributed system. The structure is required to be compact (namely, store only a single copy of each data item) and memory balanced, and to have efficient access protocols. Several structures are presented, achieving near-optimal performance with respect to memory requirements and communication complexity.