A robust protocol for distributed query processing on a local area network

摘要

Fault tolerant distributed databases use replicated data (e.g. record or relation) to handle failures of one or more nodes in a computer network. In this paper, the binary hypercube, a popular model for fault tolerant interconnection networks, has been studied as a model for interconnection in a local area network. It has been shown that in a local area network with 2′ nodes, based on a binary hypercube, where every relation is replicated r times, in the absence of faults, any arbitrary sequence of database operations R1 ⊙ R2 ⊙ … ⊙ Rn (where ⊙ is any binary database operation) may be performed by repeatedly executing r database operations in a distributed fashion using r edge disjoint paths from r selected sites of database operations to r arbitrary sites containing a target relation each. This protocol also solves the problem of materialisation of relations. In the presence of up to r-2 faults, the protocol still guarantees N edge disjoint paths to arbitrary sites. The value of N is determined by the number of faulty nodes. The protocol is also applicable in a generalized architecture called “supercube” where there is no restriction on the number of nodes in the network.