Maintaining a dynamic set of processors in a distributed system

Satoshi Fujita, Masafumi Yamashita

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)


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 + 121og2(|V| - 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.

Original languageEnglish
Title of host publicationDistributed Algorithms - 10th International Workshop, WDAG 1996, Proceedings
EditorsOzalp Babaoglu, Keith Marzullo
PublisherSpringer Verlag
Number of pages14
ISBN (Print)9783540617693
Publication statusPublished - 1996
Externally publishedYes
Event10th International Workshop on Distributed Algorithms, WDAG 1996 - Bologna, Italy
Duration: Oct 9 1996Oct 11 1996

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other10th International Workshop on Distributed Algorithms, WDAG 1996

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Maintaining a dynamic set of processors in a distributed system'. Together they form a unique fingerprint.

Cite this