Unison in Distributed Networks

Shimon Even () and Sergio Rajsbaum
Additional contact information
Shimon Even: Technion- Israel Institute of Technology, Computer Science Department
Sergio Rajsbaum: Technion- Israel Institute of Technology, Computer Science Department

A chapter in Sequences, 1990, pp 479-487 from Springer

Abstract: Abstract In this paper we report some results concerning our study of the performance of an asynchronous distributed network under the conduct of a simple synchronizer: Each processor holds back the next step of the computation until all necessary inputs have arrived. Reported here are results concerning the performance of a synchronous network in which initialization is not simultaneous, as compared with a synchronous network in which initialization is simultaneous. It is shown that the performance is not seriously damaged and that eventually the network maintains the same rate of computation. The model consists of a finite directed graph (V,E), where each vertex is a processor and each edge is a communication link. There exists a global clock whose beats are heard by all processors at the same time. The time of message transmission does not exceed the time between clock beats. Processing time is assumed to be zero. The computation starts when one or more processors wake up spontaneously. A newly awake processor sends wake-up messages on all its out-going edges. On a beat, a processor performs a computational step and sends output-messages on all its out-going edges, but if some input on an incoming edge is missing, the processor skips the beat, i.e. performs no computational step and sends no output. If on a beat all processors send a message, and all have sent the same number of messages, we say. that the network is in unison. The main result of this paper is that when the graph is strongly connected, unison is always reached. We show that it takes at most 2 ∣ V ∣ beats to reach it, and that no more than ∣ V ∣ /2 messages will accumulate in an edge. These bounds are tight.

Keywords: Buffer Size; Communication Link; Outgoing Edge; Directed Network; Directed Cycle (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4612-3352-7_38

Ordering information: This item can be ordered from
http://www.springer.com/9781461233527

DOI: 10.1007/978-1-4612-3352-7_38

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().