|
Hirschberg–Sinclair Algorithm
The Hirschberg–Sinclair algorithm is a distributed algorithm designed for leader election problem in a synchronous ring network. It is named after its inventors, Dan Hirschberg Daniel S. Hirschberg is a full professor in Computer Science at University of California, Irvine. His research interests are in the theory of design and analysis of algorithms. He obtained his PhD in Computer Science from Princeton University ... and J. B. Sinclair. The algorithm requires the use of unique IDs (UID) for each process. The algorithm works in phases and sends its UID out in both directions. The message goes out a distance of 2Phase Number hops and then the message heads back to the originating process. While the messages are heading "out" each receiving process will compare the incoming UID to its own. If the UID is greater than its own UID then it will continue the message on. Otherwise if the UID is less than its own UID, it will not pass the information on. At the end of a phase, a p ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Distributed Algorithm
A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in different application areas of distributed computing, such as telecommunications, scientific computing, distributed information processing, and real-time process control. Standard problems solved by distributed algorithms include leader election, consensus, distributed search, spanning tree generation, mutual exclusion, and resource allocation. Distributed algorithms are a sub-type of parallel algorithm, typically executed concurrently, with separate parts of the algorithm being run simultaneously on independent processors, and having limited information about what the other parts of the algorithm are doing. One of the major challenges in developing and implementing distributed algorithms is successfully coordinating the behavior of the independent parts of the algorithm in the face of processor failures and unreliable comm ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Leader Election
In distributed computing, leader election is the process of designating a single process as the organizer of some task distributed among several computers (nodes). Before the task has begun, all network nodes are either unaware which node will serve as the "leader" (or coordinator) of the task, or unable to communicate with the current coordinator. After a leader election algorithm has been run, however, each node throughout the network recognizes a particular, unique node as the task leader. The network nodes communicate among themselves in order to decide which of them will get into the "leader" state. For that, they need some method in order to break the symmetry among them. For example, if each node has unique and comparable identities, then the nodes can compare their identities, and decide that the node with the highest identity is the leader. The definition of this problem is often attributed to LeLann, who formalized it as a method to create a new token in a token ring n ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ring Network
A ring network is a network topology in which each node connects to exactly two other nodes, forming a single continuous pathway for signals through each node – a ring. Data travels from node to node, with each node along the way handling every packet. Rings can be unidirectional, with all traffic travelling either clockwise or anticlockwise around the ring, or bidirectional (as in SONET/SDH). Because a unidirectional ring topology provides only one pathway between any two nodes, unidirectional ring networks may be disrupted by the failure of a single link. A node failure or cable break might isolate every node attached to the ring. In response, some ring networks add a "counter-rotating ring" (C-Ring) to form a redundant topology: in the event of a break, data are wrapped back onto the complementary ring before reaching the end of the cable, maintaining a path to every node along the resulting C-Ring. Such "dual ring" networks include the ITU-T's PSTN telephony systems network ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Dan Hirschberg
Daniel S. Hirschberg is a full professor in Computer Science at University of California, Irvine. His research interests are in the theory of design and analysis of algorithms. He obtained his PhD in Computer Science from Princeton University in 1975. He supervised the PhD dissertation of Lawrence L. Larmore. He is best known for his 1975 and 1977 work on the longest common subsequence problem: Hirschberg's algorithm for this problem and for the related string edit distance problem solves it efficiently in only linear space. He is also known for his work in several other areas, including Distributed Algorithms. In Nancy Lynch's book ''Distributed Algorithms'' she gives details of an algorithm by Hirschberg and J. B. Sinclair for leader election in a synchronous ring. Lynch named this algorithm the HS algorithm HS or Hs can stand for: Businesses and brands * HS Produkt, a Croatian firearms manufacturer * '' Helsingin Sanomat'', a newspaper in Finland * Hawker Siddeley, a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Communications Of The ACM
''Communications of the ACM'' is the monthly journal of the Association for Computing Machinery (ACM). It was established in 1958, with Saul Rosen as its first managing editor. It is sent to all ACM members. Articles are intended for readers with backgrounds in all areas of computer science and information systems. The focus is on the practical implications of advances in information technology and associated management issues; ACM also publishes a variety of more theoretical journals. The magazine straddles the boundary of a science magazine, trade magazine, and a scientific journal. While the content is subject to peer review, the articles published are often summaries of research that may also be published elsewhere. Material published must be accessible and relevant to a broad readership. From 1960 onward, ''CACM'' also published algorithms, expressed in ALGOL. The collection of algorithms later became known as the Collected Algorithms of the ACM. See also * ''Journal of the A ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
