Library

X
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
    Randomized naming using wait-free shared variables (1998)
    Springer
    Distributed computing 11 (1998), S. 113-124 
    Details
    ISSN: 1432-0452
    Keywords: Key words: Naming problem – Symmetry breaking – Unique process ID – Asynchronous distributed protocols – Fault-tolerance – Shared memory – Wait-free read/write registers – Atomicity – Test-and-set objects – Randomized algorithms – Adaptive adversary
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract. A naming protocol assigns unique names (keys) to every process out of a set of communicating processes. We construct a randomized wait-free naming protocol using wait-free atomic read/write registers (shared variables) as process intercommunication primitives. Each process has its own private register and can read all others. The addresses/names each one uses for the others are possibly different: Processes p and q address the register of process r in a way not known to each other. For $n$ processes and $\epsilon 〉 0$ , the protocol uses a name space of size $(1+\epsilon)n$ and $O(n \log n \log \log n)$ running time (read/writes to shared bits) with probability at least $1-o(1)$ , and $O(n \log^2 n)$ overall expected running time. The protocol is based on the wait-free implementation of a novel $\alpha$ -Test&SetOnce object that randomly and fast selects a winner from a set of q contenders with probability at least $\alpha$ in the face of the strongest possible adaptive adversary.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s004460050045
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Distributed match-making (1988)
    Springer
    Algorithmica 3 (1988), S. 367-391 
    Details
    ISSN: 1432-0541
    Keywords: Locating objects ; Locating services ; Mutual exclusion ; Replicated data management ; Distributed algorithms ; Computational complexity ; Store- and-forward computer networks ; Network topology
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In many distributed computing environments, processes are concurrently executed by nodes in a store- and-forward communication network. Distributed control issues as diverse as name server, mutual exclusion, and replicated data management involve making matches between such processes. We propose a formal problem called “distributed match-making” as the generic paradigm. Algorithms for distributed match-making are developed and the complexity is investigated in terms of messages and in terms of storage needed. Lower bounds on the complexity of distributed match-making are established. Optimal algorithms, or nearly optimal algorithms, are given for particular network topologies.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01762123
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Statistical properties of finite sequences with high Kolmogorov complexity (1994)
    Springer
    Theory of computing systems 27 (1994), S. 365-376 
    Details
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We investigate to what extent finite binary sequences with high Kolmogorov complexity are normal (all blocks of equal length occur equally frequently), and the maximal length of all-zero or all-one runs which occur with certainty.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01192146
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Book
    Book
    ¬An¬ introduction to Kolmogorov complexity and its applications (1993)
    Berlin u.a. :Springer,
    Details
    Title: ¬An¬ introduction to Kolmogorov complexity and its applications
    Author: Li, Ming
    Contributer: Vitányi, Paul
    Publisher: Berlin u.a. :Springer,
    Year of publication: 1993
    Pages: 546 S.
    Series Statement: Texts and Monographs in Computer Science
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...