Distributed Computing (2008)
756 pág.

Distributed Computing (2008)


DisciplinaAlgorítimos Distribuídos32 materiais283 seguidores
Pré-visualização50 páginas
events in a distributed system,
Communications of the ACM, 21(7), 1978, 558\u2013565.
[20] H. F. Li, T. Radhakrishnan, and K. Venkatesh, Global state detection in non-
FIFO networks, Proceedings of the 7th International Conference on Distributed
Computing Systems, 1987, 364\u2013370.
[21] D. Manivannan, R. H. B. Netzer, and M. Singhal, Finding consistent global
checkpoints in a distributed computation, IEEE Transactions of Parallel and
Distributed Systems, June, 1997, 623\u2013627.
[22] F. Mattern, Algorithms for distributed termination detection, Distributed Com-
puting, 2(3), 1987, 161\u2013175.
[23] F. Mattern, Efficient algorithms for distributed snapshots and global virtual
time approximation, Journal of Parallel and Distributed Computing, 18, 1993,
423\u2013434.
[24] B. Miller and J. Choi, Breakpoints and halting in distributed programs, Proceed-
ings of the 8th International Conference on Distributed Computing Systems,
1988, 316\u2013323.
[25] H. B. Robert and J. Xu. Netzer, Necessary and sufficient conditions for consis-
tent global snapshots, IEEE Transactions on Parallel and Distributed Systems,
6(2), 1995, 165\u2013169.
[26] M. Raynal, A. Schiper, and S. Toueg, Causal ordering abstraction and a simple
way to implement it, Information Processing Letters, 39(6), 1991, 343\u2013350.
[27] S. Sarin and N. Lynch, Discarding obsolete information in a replicated database
system, IEEE Transactions on Software Engineering, 13(1), 1987, 39\u201347.
125 References
[28] A. Schiper, J. Eggli, and A. Sandoz, A new algorithm to implement causal
ordering, Proceedings of the 3rd International Workshop on Distributed Algo-
rithms, LNCS 392, Springer Verlag, 1989, pp. 219\u2013232.
[29] M. Spezialetti and P. Kearns, Efficient distributed snapshots, Proceedings of
the 6th International Conference on Distributed Computing Systems, 1986,
382\u2013388.
[30] M. Spezialetti and P. Kearns, Simultaneous regions: a framework for the con-
sistent monitoring of distributed systems, Proceedings of the 9th International
Conference on Distributed Computing Systems, 1989, 61\u201368.
[31] K. Taylor, The role of inhibition in consistent cut protocols, Proceedings of
the 3rd International Workshop on Distributed Algorithms, LNCS 392, 1989,
124\u2013134.
[32] S. Venkatesan, Message-optimal incremental snapshots, Journal of Computer
and Software Engineering, 1(3), 1993, 211\u2013231.
[33] Yi-Min Wang, Maximum and minimum consistent global checkpoints and their
applications, Proceedings of the 14th IEEE Symposium on Reliable Distributed
Systems, Bad Neuenahr, Germany, September 1995, 86\u201395.
[34] Yi-Min Wang, Consistent global checkpoints that contain a given set of local
checkpoints, IEEE Transactions on Computers, 46(4), 1997, 456\u2013468.
C H A P T E R
5 Terminology and basic algorithms
In this chapter, we first study a methodical framework in which distributed
algorithms can be classified and analyzed. We then consider some basic
distributed graph algorithms. We then study synchronizers, which provide the
abstraction of a synchronous system over an asynchronous system. Finally,
we look at some practical graph problems, to appreciate the necessity of
designing efficient distributed algorithms.
5.1 Topology abstraction and overlays
The topology of a distributed system can be typically viewed as an undirected
graph in which the nodes represent the processors and the edges represent
the links connecting the processors. Weights on the edges can represent some
cost function we need to model in the application. There are usually three
(not necessarily distinct) levels of topology abstraction that are useful in
analyzing the distributed system or a distributed application. These are now
described using Figure 5.1. To keep the figure simple, only the relevant end
hosts participating in the application are shown. The WANs are indicated by
ovals drawn using dashed lines. The switching elements inside the WANs,
and other end hosts that are not participating in the application, are not shown
even though they belong to the physical topological view. Similarly, all the
edges connecting all end hosts and all edges connecting to all the switching
elements inside the WANs also belong to the physical topology view even
though only some edges are shown.
\u2022 Physical topology The nodes of this topology represent all the network
nodes, including switching elements (also called routers), in the WAN and
all the end hosts \u2013 irrespective of whether the hosts are participating in the
application. The edges in this topology represent all the communication
links in the WAN in addition to all the direct links between the end hosts.
126
127 5.1 Topology abstraction and overlays
Figure 5.1 Two examples of
topological views at different
levels of abstraction. WAN
WAN
WANWAN
WAN or other network
(a) (b)
participating process(or)
In Figure 5.1(a), the physical topology is not shown explicitly to keep the
figure simple.
\u2022 Logical topology This is usually defined in the context of a particular
application. The nodes represent all the end hosts where the application
executes. The edges in this topology are logical channels (also termed
as logical links) among these nodes. This view is at a higher level of
abstraction than that of the physical topology, and the nodes and edges of
the physical topology need not be included in this view.
Often, logical links are modeled between particular pairs of end hosts
participating in an application to give a logical topology with useful
properties. Figure 5.1(b) shows each pair of nodes in the logical topol-
ogy is connected to give a fully connected network. Each pair of nodes
can communicate directly with each other participant in the application
using an incident logical link at this level of abstraction of the topology.
However, the logical links may also define some arbitrary connectivity
(neighborhood-relation) on the nodes in this abstract view. In Figure 5.1(a),
the logical view provides each node with a partial view of the topology,
and the connectivity provided is some neighborhood connectivity. To com-
municate with another application node that is not a logical neighbor, a
node may have to use a multi-hop path composed of logical links at this
level of abstraction of the topology.
While the fully connected logical topology in Figure 5.1(b) provides
a complete view of the system, updating such a view in a dynamic
system incurs an overhead. Neighborhood-based logical topologies as in
Figure 5.1(a) are easier to manage.
We will consider distributed algorithms on logical topologies in this
book. Peer-to-peer (P2P) networks (see Chapter 18) are also defined by a
logical topology at the application layer. However, the emphasis of P2P
networks is on self-organizing networks with built-in functions, e.g., the
implementation of application layer functions such as object lookup and
location in a distributed manner.
128 Terminology and basic algorithms
\u2022 Superimposed topology This is a higher-level topology that is super-
imposed on the logical topology. It is usually a regular structure such as
a tree, ring, mesh, or hypercube. The main reason behind defining such
a topology is that it provides a specialized path for efficient information
dissemination and/or gathering as part of a distributed algorithm.
Consider the problem of collecting the sum of variables, one from each
node. This can be efficiently solved using n messages by circulating a
cumulative counter on a logical ring, or using n\u22121 messages on a logical
tree. The ring and tree are examples of superimposed topologies on the
underlying logical topology \u2013 which may be arbitrary as in Figure 5.1(a)
or fully connected as in Figure 5.1(b).
We will encounter various examples of these topologies, A superimposed
topology is also termed as a topology overlay. This latter term is becoming
increasingly popular with the spread of