Achieving parallel communication in distributed systems

Two algorithms are used to achieve parallel communication in distributed systems. The graph coloring algorithm is used to resolve conflicts in the network and the coin-changing algorithm is used to reduce bus idling time. It is shown that by choosing a proper set of coin types (time frames), such as a geometric sequence, the greedy algorithm can always generate an optimal representation for a time requirement for a communication request. The performance evaluation shows that the decrease of network delay depends on the variance of the distribution of communication durations and the expected number of communication processes (ENP) that are being carried out at the same time interval. The higher the variance and the ENP, the greater the decrease of network delay achieved by applying the coin-changing algorithm in a dynamically partitionable bus network