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