Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2009-05-27
16th ACM Symposium on Theory of Computing, Washington D.C., 1984, 542 - 547
Computer Science
Distributed, Parallel, and Cluster Computing
Scientific paper
Unlimited asynchronism is intolerable in real physically distributed computer systems. Such systems, synchronous or not, use clocks and timeouts. Therefore the magnitudes of elapsed absolute time in the system need to satisfy the axiom of Archimedes. Under this restriction of asynchronicity logically time-independent solutions can be derived which are nonetheless better (in number of message passes) than is possible otherwise. The use of clocks by the individual processors, in elections in a ring of asynchronous processors without central control, allows a deterministic solution which requires but a linear number of message passes. To obtain the result it has to be assumed that the clocks measure finitely proportional absolute time-spans for their time units, that is, the magnitudes of elapsed time in the ring network satisfy the axiom of Archimedes. As a result, some basic subtilities associated with distributed computations are highlighted. For instance, the known nonlinear lower bound on the required number of message passes is cracked. For the synchronous case, in which the necessary assumptions hold a fortiori, the method is -asymptotically- the most efficient one yet, and of optimal order of magnitude. The deterministic algorithm is of -asymptotically- optimal bit complexity, and, in the synchronous case, also yields an optimal method to determine the ring size. All of these results improve the known ones.
No associations
LandOfFree
Distributed elections in an Archimedean ring of processors does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Distributed elections in an Archimedean ring of processors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed elections in an Archimedean ring of processors will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-528473