000			04333nam a22004215i 4500
999			_c387306 _d387306
001			387306
003			ES-MaUEC
005			20230312125034.0
006			a||||fo|||| 00| 0
007			cr nn 008mamaa
008			220601s2012 sz | s |||| 0|eng d
020			_a9783031020063
024	7		_a10.1007/978-3-031-02006-3 _2doi
040			_aES-MaUEC _bspa _cES-MaUEC _dES-MaUEC
050		4	_aQA76.9.D5 _b2012 EB
100	1		_aWelch, Jennifer _eautor _4aut _4http://id.loc.gov/vocabulary/relators/aut _9687264
245	1	0	_aLink Reversal Algorithms _cby Jennifer Welch, Jennifer Walter
250			_a1st edition 2012
264		1	_aCham _bSpringer International Publishing _c2012
300			_a1 recurso en línea (IX, 93 páginas)
336			_atexto _btxt _2rdacontent
337			_aelectrónico _bc _2rdamedia
338			_arecurso electrónico _bcr _2rdacarrier
347			_aarchivo de texto _bPDF
490	0		_aSynthesis Lectures on Distributed Computing Theory _x2155-1634
505	0		_aIntroduction -- Routing in a Graph: Correctness -- Routing in a Graph: Complexity -- Routing and Leader Election in a Distributed System -- Mutual Exclusion in a Distributed System -- Distributed Queueing -- Scheduling in a Graph -- Resource Allocation in a Distributed System -- Conclusion.
520			_aLink reversal is a versatile algorithm design technique that has been used in numerous distributed algorithms for a variety of problems. The common thread in these algorithms is that the distributed system is viewed as a graph, with vertices representing the computing nodes and edges representing some other feature of the system (for instance, point-to-point communication channels or a conflict relationship). Each algorithm assigns a virtual direction to the edges of the graph, producing a directed version of the original graph. As the algorithm proceeds, the virtual directions of some of the links in the graph change in order to accomplish some algorithm-specific goal. The criterion for changing link directions is based on information that is local to a node (such as the node having no outgoing links) and thus this approach scales well, a feature that is desirable for distributed algorithms. This monograph presents, in a tutorial way, a representative sampling of the work on link-reversal-based distributed algorithms. The algorithms considered solve routing, leader election, mutual exclusion, distributed queueing, scheduling, and resource allocation. The algorithms can be roughly divided into two types, those that assume a more abstract graph model of the networks, and those that take into account more realistic details of the system. In particular, these more realistic details include the communication between nodes, which may be through asynchronous message passing, and possible changes in the graph, for instance, due to movement of the nodes. We have not attempted to provide a comprehensive survey of all the literature on these topics. Instead, we have focused in depth on a smaller number of fundamental papers, whose common thread is that link reversal provides a way for nodes in the system to observe their local neighborhoods, take only local actions, and yet cause global problems to be solved. We conjecture that future interesting uses of link reversal are yet to be discovered. Table of Contents: Introduction / Routing in a Graph: Correctness / Routing in a Graph: Complexity / Routing and Leader Election in a Distributed System / Mutual Exclusion in a Distributed System / Distributed Queueing / Scheduling in a Graph / Resource Allocation in a Distributed System / Conclusion.
988			_aSynthesis Collection of Technology_2012
650		7	_2embne _9151819 _aAlgoritmos computacionales
650		7	_2embne _9156434 _aProceso distribuido (Informática)
700	1		_aWalter, Jennifer Emily, _eautor _4aut _4http://id.loc.gov/vocabulary/relators/aut _9687263 _d1957-
776	0	8	_iPrinted edition: _z9783031008788
776	0	8	_iPrinted edition: _z9783031031342
856	4	0	_uhttps://go.openathens.net/redirector/universidadeuropea.es?url=https://doi.org/10.1007/978-3-031-02006-3 _zAcceso a este recurso digital (usuarios Universidad Europea de Madrid)
942			_2lcc _cLE
998			_b03/2023 _dz _esc _zSI