-
David E. Culler,
Richard M. Karp,
David Patterson,
Abhijit Sahay,
Eunice E. Santos,
Klaus Erik Schauser,
Ramesh Subramonian,
and Thorsten von Eicken.
LogP: a practical model of parallel computation.
Communications of the ACM,
39(11):78--85,
1996.
[PDF
]
Keywords:
LogP.
@Article{CullerKarpPattersonLogP96,
author = {David E. Culler and Richard M. Karp and David Patterson and Abhijit Sahay and Eunice E. Santos and Klaus Erik Schauser and Ramesh Subramonian and Thorsten {von Eicken}},
title = {{LogP}: a practical model of parallel computation},
journal = {Communications of the ACM},
volume = {39},
number = {11},
year = {1996},
issn = {0001-0782},
pages = {78--85},
publisher = {ACM Press},
keywords = {LogP},
pdf = {PAPERS/CullerKarpPattersonLogP96.pdf}
}
-
S. A. M. Makki and George Havas.
Distributed algorithms for depth-first search.
Information Processing Letters,
60(1):7--12,
1996.
[PDF
]
Keywords:
Distributed system,
Depth-first search,
Distributed algorithm,
communication graph.
| Abstract: |
We present distributed algorithms for constructing a depth-first search tree for a communication network which are more efficient than previous methods. Our algorithms require 2|V| − 2 messages and units of time in the worst case, where |V| is the number of sites in the network, and as little as |V| messages and time units in the best case. The actual number of messages and time units depends on the network topology and possibly on the routing chosen. We can interpret this to mean that the number of messages and time units is |V|(1 + r) in the worst case, where 0 \leq r < 1 and the value of r depends on the topology and the routing. In a best case for the simplest algorithm, for example when the underlying network has a ring topology, r = 0 and our basic algorithm requires |V| messages and time units, regardless of routing. We extend the basic algorithm to achieve the same best case bound for other topologies. The worst case bound, which has r = 1 − 2/|V|, applies if the network topology is a tree. The improvement over the best of previous algorithms is achieved by dynamic backtracking, with a minor increase in message length. |
@Article{MakkiHavasDFS96,
author = {S. A. M. Makki and George Havas},
title = {Distributed algorithms for depth-first search},
journal = {Information Processing Letters},
volume = {60},
number = {1},
year = {1996},
pages = {7--12},
publisher = {Elsevier North-Holland, Inc.},
keywords = {Distributed system; Depth-first search; Distributed algorithm; communication graph},
pdf = {PAPERS/MakkiHavasDFS96.pdf},
abstract = {We present distributed algorithms for constructing a depth-first search tree for a communication network which are more efficient than previous methods. Our algorithms require $2|V| − 2$ messages and units of time in the worst case, where $|V|$ is the number of sites in the network, and as little as $|V|$ messages and time units in the best case. The actual number of messages and time units depends on the network topology and possibly on the routing chosen. We can interpret this to mean that the number of messages and time units is $|V|(1 + r)$ in the worst case, where $0 \leq r < 1$ and the value of $r$ depends on the topology and the routing. In a best case for the simplest algorithm, for example when the underlying network has a ring topology, $r = 0$ and our basic algorithm requires $|V|$ messages and time units, regardless of routing. We extend the basic algorithm to achieve the same best case bound for other topologies. The worst case bound, which has $r = 1 − 2/|V|$, applies if the network topology is a tree. The improvement over the best of previous algorithms is achieved by dynamic backtracking, with a minor increase in message length.}
}
-
Alexander A. Stepanov.
Generic Programming.
Lecture Notes in Computer Science,
1181:40,
1996.
@Article{Stepanov96:GP,
author = "Alexander A. Stepanov",
title = "Generic Programming",
journal = "Lecture Notes in Computer Science",
volume = "1181",
year = "1996",
pages = "40",
coden = "LNCSD9",
ISSN = "0302-9743",
bibdate = "Fri Aug 22 11:59:49 MDT 1997",
acknowledgement= ack-nhfb,
}