| Maintaining a Dynamic Set of Processors in a Distributed System (2007) | |||||||||||||||||
Abstract | |||||||||||||||||
| . Consider a distributed system consisting of a set V of processors, and assume that every pair of processors can directly communicate with each other. A processor structure is proposed, for implementing a dynamic set U ` V of processors in the distributed system. The dynamic set supports the following three operations: Insert inserts the caller (i.e., the processor executing this operation) in U , Delete removes the caller from U , and Find searches for a processor in U . To evaluate the efficiency of the implementation, an amortized analysis of the message complexity of operations is performed; the amortized number of messages per each operation is 8 + 12 log 2 (jV j \Gamma 1), in the worst case. The dynamic set is applicable to many important problems, including the load balancing problem, and the proposed processor structure is used to solve the mutual exclusion problem, and to construct a more complex dynamic set of processors like FIFO queue. Keywords: processor structure, data ... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||