Mapping Data in Peer-to-Peer Systems: Semantics and Algorithmic Issues

Kementsietsidis, A.; Arenas, M.; Miller, R. J.
Kementsietsidis, A
Arenas, M
Miller, R
SIGMOD, 2003
Citations range: 
100 - 499
Kementsietsidis2003MappingDatainPeertoPeer.pdf207.66 KB

We consider the problem of mapping data in peer-topeer
data-sharing systems. Such systems often rely on
the use of mapping tables listing pairs of corresponding
values to search for data residing in different peers.
In this paper, we address semantic and algorithmic issues
related to the use of mapping tables. We begin by
arguing why mapping tables are appropriate for data
mapping in a peer-to-peer environment. We discuss alternative
semantics for these tables and we present a
language that allows the user to specify mapping tables
under different semantics. Then, we show that by treating
mapping tables as constraints (called mapping constraints)
on the exchange of information between peers
it is possible to reason about them. We motivate why
reasoning capabilities are needed to manage mapping
tables and show the importance of inferring new mapping
tables from existing ones. We study the complexity
of this problem and we propose an efficient algorithm
for its solution. Finally, we present an implementation
along with experimental results that show that mapping
tables may be managed efficiently in practice.