We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
Published online by Cambridge University Press: 05 June 2012
In this chapter we investigate how the theory of distributed computing is affected by the assumption that there exists a global time, to which processes have access. A global time frame is part of the physical reality that surrounds us; this reality includes the processes of a distributed system and the design of distributed algorithms may profit from exploiting time. The results of this chapter show that time can be exploited to reduce the communication complexity of distributed algorithms if processing and communication times are bounded.
However, problems that are unsolvable without using time remain unsolvable after its introduction; thus, introducing synchrony improves the compexity but not the computability of distributed systems. This situation differs from the impact of synchronism in networks that are subject to failures; in Chapters 14 and 15 it will be shown that larger classes of failures can be handled deterministically if synchronism is exploited. Synchronism has already been used in Section 3.2 to overcome transmission failures.
In this chapter global time will mainly be studied in an idealized form, namely, where the entire network operates in discrete steps called pulses, as explained in Subsection 12.1.1. Each process performs local computations in each pulse, and it is ensured that a message that is sent in one pulse is received before the next pulse. This globally synchronized operation is also referred to as a lockstep operation. Lockstep operation is fairly easy to implement if clocks are available and an upper bound on transmission delay is assumed; see Subsection 12.1.3.
To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Find out more about the Kindle Personal Document Service.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.
