ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

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
    Geometric applications of a matrix-searching algorithm (1987)
    Springer
    Algorithmica 2 (1987), S. 195-208 
    Details
    ISSN: 1432-0541
    Keywords: All-farthest neighbors ; Monotone matrix ; Convex polygon ; Wire routing ; Inscribed polygons ; Circumscribed polygons
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract LetA be a matrix with real entries and letj(i) be the index of the leftmost column containing the maximum value in rowi ofA.A is said to bemonotone ifi 1 〉i 2 implies thatj(i 1) ≥J(i 2).A istotally monotone if all of its submatrices are monotone. We show that finding the maximum entry in each row of an arbitraryn xm monotone matrix requires Θ(m logn) time, whereas if the matrix is totally monotone the time is Θ(m) whenm≥n and is Θ(m(1 + log(n/m))) whenm〈n. The problem of finding the maximum value within each row of a totally monotone matrix arises in several geometric algorithms such as the all-farthest-neighbors problem for the vertices of a convex polygon. Previously only the property of monotonicity, not total monotonicity, had been used within these algorithms. We use the Θ(m) bound on finding the maxima of wide totally monotone matrices to speed up these algorithms by a factor of logn.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840359
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    A lower bound on the period length of a distributed scheduler (1993)
    Springer
    Algorithmica 10 (1993), S. 383-398 
    Details
    ISSN: 1432-0541
    Keywords: Distributed systems ; Schedulers ; Synchronizers ; Channel access protocols
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Ad-scheduling of a graphG is a sequence of rounds, each consisting of some of the nodes of the graph, such that the distance between any two nodes participating in the same round is greater thand. Ad-scheduler is a protocol that determines ad-scheduling ofG. A 1-scheduler is applicable to process scheduling in a resource-sharing system, and to proper communication scheduling of the half-duplex model in communication networks. A 2-scheduler can be used as a collision-free protocol for radio networks. In this paper a simpled-scheduler is analyzed. We first discuss basic properties of this scheduling, and give a complete characterization of this scheduling for trees and cycles. We study the period length of this scheduling, and the main result is a worst-case exponential lower bound for this length.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01769705
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    A correction algorithm for token-passing sequences in mobile communication networks (1989)
    Springer
    Algorithmica 4 (1989), S. 329-341 
    Details
    ISSN: 1432-0541
    Keywords: Round-robin token-passing ; Mobile communication ; Euclidean Traveling Salesman tours ; Approximation algorithms ; Incremental corrections
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a distributed approximation algorithm for the Traveling Salesman Problem (TSP) in networks that use a broadcast, multiaccess communication channel. The application for which the algorithm was originally designed is maintaining a short token-passing path (which means low scheduling overhead) in radio networks with mobile nodes. The algorithm is adaptive in the sense that it shifts gradually between performing a slight correction of an existing tour and recomputing one “from scratch.” It can thus be viewed as a generalization, or extension, of conventional TSP algorithms. The proposed algorithm guarantees the same worst-case tour length as the one guaranteed by any conventional “from scratch” algorithm, yet it is capable of taking advantage of certain node layouts (e.g., geographically clustered nodes) to reduce the cost of computing the path. The correction algorithm is suitable for dynamic graphs with slowly changing edge weights, and for which a Traveling Salesman tour (optimal or approximate) has previously been computed and is “deteriorating” with time due to the weight changes. The algorithm can be used to “refresh” the tour whenever it deteriorates beyond a given level, and thus maintain a reasonable average tour length at relatively low computation and communication costs. For a Euclidean graph withn nodes laid out in a bounded area with diameterD, the maximal length of the tour produced by the algorithm is proportional toD√n, like the maximal length of an optimal tour in that graph (the two differ by a factor of 2 at the worst case).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01553895
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Self-stabilization of dynamic systems assuming only read/write atomicity (1993)
    Springer
    Distributed computing 7 (1993), S. 3-16 
    Details
    ISSN: 1432-0452
    Keywords: Self-stabllization ; Read/write atomicity ; Protocol combination
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary Three self-stabilizing protocols for distributed systems in the shared memory model are presented. The first protocol is a mutual-exclusion prootocol for tree structured systems. The second protocol is a spanning tree protocol for systems with any connected communication graph. The thrid protocol is obtianed by use offair protoco combination, a simple technique which enables the combination of two self-stabilizing dynamic protocols. The result protocol is a self-stabilizing, mutualexclusion protocol for dynamic systems with a general (connected) communication graph. The presented protocols improve upon previous protocols in two ways: First, it is assumed that the only atomic operations are either read or write to the shared memory. Second, our protocols work for any connected network and even for dynamic network, in which the topology of the network may change during the excution.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02278851
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Distributed algorithms for constructing a minimum-weight spanning tree in a broadcast network (1987)
    Springer
    Distributed computing 2 (1987), S. 139-148 
    Details
    ISSN: 1432-0452
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Two distributed algorithms are presented for a network using a common communication channel (e.g. radio) in which all nodes are within signal range and in line of sight of each other: (a) an algorithm to compute all $$\left( {\begin{array}{*{20}c} N \\ 2 \\ \end{array} } \right)$$ internode distances (in terms of propagation delays) in the network. the algorithm requires only 2 messages per node, and provides each node with the distances to all other nodes. (b) An algorithm for constructing a minimum-weight spanning tree (MST) in such a network. This algorithm starts out with the information provided by (a) and ends with each node possessing the explicit knowledge of the full MST. The algorithm requires at most log2 N messages per node. The internal processing in each node needsO(N logN) time andO(N) space. All messages required by (a) and (b) contain at most one edge weight plus 2 log2 N bits. Some possible applications of the algorithms are: position-location, tuning acknowledgement time-out mechanisms, tuning the scheduling functions of access protocols that are sensitive to individual internode propagation delays, and selecting performance effective transmission sequences for round robin access protocols.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01782774
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Closed schedulers: a novel technique for analyzing asynchronous protocols (1995)
    Springer
    Distributed computing 8 (1995), S. 203-210 
    Details
    ISSN: 1432-0452
    Keywords: Closed schedulers ; Asynchronous protocols ; Admissible runs
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary Analyzing distributed protocols in various models often involves a careful analysis of the set ofadmissible runs, for which the protocols should behave correctly. In particular, the admissible runs assumed by at-resilient protocol are runs which are fair for all but at mostt processors. In this paper we defineclosed sets of runs, and suggest a technique to prove impossibility results fort-resilient protocols, by restricting the corresponding sets of admissible runs to smaller sets, which are closed, as follows: For each protocolPR and for each initial configurationc, the set of admissible runs ofPR which start fromc defines a tree in a natural way: the root of the tree is the empty run, and each vertex in it denotes a finite prefix of an admissible run; a vertexu in the tree has a sonv iffv is also a prefix of an admissible run, which extendsu by one atomic step. The tree of admissible runs described above may contain infinite paths which are not admissible runs. A set of admissible runs isclosed if for every possible initial configurationc, each path in the tree of admissible runs starting fromc is also an admissible run. Closed sets of runs have the simple combinatorial structure of the set of paths of an infinite tree, which makes them easier to analyze. We introduce a unified method for constructing closed sets of admissible runs by using a model-independent construction of closedschedulers, and then mapping these schedulers to closed sets of runs. We use this construction to provide a unified proof of impossibility of consensus protocols.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02242738
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Initial failures in distributed computations (1989)
    Springer
    International journal of parallel programming 18 (1989), S. 255-276 
    Details
    ISSN: 1573-7640
    Keywords: Asynchronous protocols ; crash failures ; initial failures ; winning strategy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We investigate the possibility of solving problems in completely asynchronous message passing systems where a number of processes may fail prior to execution. By using game-theoretical notions, necessary and sufficient conditions are provided for solving problems is such a model with an without a termination requirement. An upper bound on the message complexity for solving any problem in the model is given, as well as a simple design concept for constructing a solution to any solvable problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01407859
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Possibility and impossibility results in a shared memory environment (1996)
    Springer
    Acta informatica 33 (1996), S. 1-20 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract.  We focus on unreliable asynchronous shared memory model which support only atomic read and write operations. For such a model we provide a necessary condition for the solvability of problems in the presence of multiple undetectable crash failures. Also, by using game-theoretical notions, a necessary and sufficient condition is provided, for the solvability of problems in the presence of multiple undetectable initial failures (i.e., processes may fail only prior to the execution). Our results imply that many problems such as consensus, choosing a leader, ranking, matching and sorting are unsolvable in the presence of a single crash failure, and that variants of these problems are solvable in the presence of a single crash failure, and that variants of these problems are solvable in the presence of t−1 crash failures but not in the presence of t crash failures. We show that a shared memory model can simulate various message passing models, and hence our impossibility results hold also for those message passing models. Our results extend and generalize previously known impossibility results for various asynchronous models.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s002360050034
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    facet.materialart.
    Unknown
    A correction algorithm for token-passing sequences in mobile communication networks (1989)
    Springer
    Details
    Publication Date: 1989-06-01
    Print ISSN: 0178-4617
    Electronic ISSN: 1432-0541
    Topics: Computer Science , Mathematics
    Published by Springer
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    PAPER CURRENT
  • 10
    facet.materialart.
    Unknown
    A lower bound on the period length of a distributed scheduler (1993)
    Springer
    Details
    Publication Date: 1993-11-01
    Print ISSN: 0178-4617
    Electronic ISSN: 1432-0541
    Topics: Computer Science , Mathematics
    Published by Springer
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    PAPER CURRENT
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...