Library

feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Springer
    Distributed computing 6 (1992), S. 121-139 
    ISSN: 1432-0452
    Keywords: Timing properties ; Timing-based algorithms ; Formal specification ; Formal verification ; Assertional reasoning ; Possibilities mappings ; Timed automata ; I/O automata ; Progress functions
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary A new technique for proving timing properties for timing-based algorithms is described; it is an extension of the mapping techniques previously used in proofs of safety properties for asynchronous concurrent systems. The key to the method is a way of representing a system with timing constraints as an automaton whose state includes predictive timing information. Timing assumptions and timing requirements for the system are both represented in this way. A multi-valued mapping from the “assumptions automaton” to the “requirements automaton” is then used to show that the given system satisfies the requirements. One type of mapping is based on a collection of “progress functions” providing measures of progress toward timing goals. The technique is illustrated with two examples, a simple resource manager and a two-process race system.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Springer
    Distributed computing 8 (1995), S. 121-132 
    ISSN: 1432-0452
    Keywords: Atomic snapshot ; Lattice agreement
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary Thesnapshot object is an important tool for constructing wait-free asynchronous algorithms. We relate the snapshot object to thelattice agreement decision problem. It is shown that any algorithm for solving lattice agreement can be transformed into an implementation of a snapshot object. The overhead cost of this transformation is only a linear number of read and write operations on atomic single-writer multi-reader registers. The transformation uses an unbounded amount of shared memory. We present a deterministic algorithm for lattice agreement that usedO (log2 n) operations on 2-processorTest & Set registers, plusO (n) operations on atomic single-writer multi-reader registers. The shared objects are used by the algorithm in adynamic mode, that is, the identity of the processors that access each of the shared objects is determined dynamically during the execution of the algorithm. By a randomized implementation of 2-processorsTest & Set registers from atomic registers, this algorithm implies a randomized algorthm for lattice agreement that uses an expected number ofO (n) operations on (dynamic) atomic single-writer multi-reader registers. Combined with our transformation this yields implementations of atomic snapshots with the same complexity.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 3
    Electronic Resource
    Electronic Resource
    Springer
    Distributed computing 11 (1997), S. 41-57 
    ISSN: 1432-0452
    Keywords: Key words:Conncection management – Handshake – TCP-Memory requirements – Incarnations – Transport layer
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract. A connection between two hosts across a wide-area network may consist of many sessions over time, each called an incarnation. A connection is synchronized using a connection establishment protocol, based on a handshake mechanism, to allow reliable exchange of data. This paper identifies the precise level of handshake needed under different assumptions on the nodes and on the network, using a formal model for connection management. In particular, the following parameters are studied: the size of the memory at the nodes, the information retained between incarnations, and the existence of time constraints on the network. Among the results we obtain are: (1) If both nodes have bounded memory, no incarnation management protocol exists. (2) If the nodes have unbounded memory, then a two-way handshake incarnation management protocol exists. (3) If the nodes have unbounded memory, and the server does not retain connection-specific information between incarnations, then a three-way handshake incarnation management protocol exists. On the other hand, a two-way handshake incarnation management protocol does not exist, even if some global information is retained. (4) If a bound on maximum packet lifetime (MPL) is known, then a two-way handshake incarnation management protocol exists, in which the server does not retain connection-specific information between incarnations.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    Distributed computing 8 (1995), S. 163-169 
    ISSN: 1432-0452
    Keywords: Smoothing networks ; Load balancing ; Producer/consumer
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary It is shown that an acyclic smoothing network (and hence counting network) with fan-outn cannot be constructed from balancers of fan-outb 1,...,b k , if there exists a prime factorp ofn, such thatp does not divideb i , for alli, 1≦i≦k. This holds regardless of the depth, fan-in or size of the network, as long as they are finite. On the positive side, a simple construction ofcyclic counting networks with fan-outn, for arbitraryn, is presented. An acyclic counting network with fan-in and fan-outp2 k , for any integerk≧0, is constructed out of 2-balancers andp-balancers.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 5
    Electronic Resource
    Electronic Resource
    Springer
    Algorithmica 4 (1989), S. 437-446 
    ISSN: 1432-0541
    Keywords: Distributed network ; Distributed algorithm ; Leader election ; Communication complexity ; Chordal ring
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the message complexity of the problem of distributively electing a leader in chordal rings. Such networks consist of a basic ring with additional links, the extreme cases being the oriented ring and the complete graph with a full sense of direction. We present a general election algorithm for these networks, and prove its optimality. As a corollary, we show thatO(logn) chords at each processor suffice to obtain an algorithm that uses at mostO(n) messages; this improves and extends a previous work, where an algorithm, also usingO(n) messages, was suggested for the case where alln-1 chords exist (the oriented complete network).
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 6
    Title: Distributed computing : fundamentals, simulations and advanced topics
    Author: Attiya, Hagit
    Contributer: Welch, Jennifer
    Edition: 2. ed.
    Publisher: Hoboken, NJ :Wiley-Interscience,
    Year of publication: 2004
    Pages: XV, 414 S.
    Series Statement: Wiley series on parallel and distributed computing
    ISBN: 0-471-45324-2
    Type of Medium: Book
    Language: English
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...