|
Maekawa's Algorithm
Maekawa's algorithm is an algorithm for mutual exclusion on a distributed system. The basis of this algorithm is a quorum-like approach where any one site needs only to seek permissions from a subset of other sites. Algorithm Terminology * A ''site'' is any computing device which runs the Maekawa's algorithm * For any one request of entering the critical section: ** The ''requesting site'' is the site which is requesting to enter the critical section. ** The ''receiving site'' is every other site which is receiving the request from the requesting site. * ''ts'' refers to the local time stamp of the system according to its logical clock Algorithm Requesting site: * A requesting site P_i sends a message \text(ts, i) to all sites in its quorum set R_i. Receiving site: * Upon reception of a \text(ts, i) message, the receiving site P_j will: ** If site P_j does not have an outstanding \text message (that is, a \text message that has not been released), then site P_j sends a \text(j) ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mutual Exclusion
In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions. It is the requirement that one thread of execution never enters a critical section while a concurrent thread of execution is already accessing said critical section, which refers to an interval of time during which a thread of execution accesses a shared resource or shared memory. The shared resource is a data object, which two or more concurrent threads are trying to modify (where two concurrent read operations are permitted but, no two concurrent write operations or one read and one write are permitted, since it leads to data inconsistency). Mutual exclusion algorithm ensures that if a process is already performing write operation on a data object ritical sectionno other process/thread is allowed to access/modify the same object until the first process has finished writing upon the data object ritical sectionand released the object fo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Distributed System
A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another from any system. Distributed computing is a field of computer science that studies distributed systems. The components of a distributed system interact with one another in order to achieve a common goal. Three significant challenges of distributed systems are: maintaining concurrency of components, overcoming the lack of a global clock, and managing the independent failure of components. When a component of one system fails, the entire system does not fail. Examples of distributed systems vary from SOA-based systems to massively multiplayer online games to peer-to-peer applications. A computer program that runs within a distributed system is called a distributed program, and ''distributed programming'' is the process of writing such programs. There are many different types of implementations for t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Quorum
A quorum is the minimum number of members of a deliberative assembly (a body that uses parliamentary procedure, such as a legislature) necessary to conduct the business of that group. According to ''Robert's Rules of Order Newly Revised'', the "requirement for a quorum is protection against totally unrepresentative action in the name of the body by an unduly small number of persons." In contrast, a plenum is a meeting of the full (or rarely nearly full) body. A body, or a meeting or vote of it, is quorate if a quorum is present (or casts valid votes). The term ''quorum'' is from a Middle English wording of the commission formerly issued to justices of the peace, derived from Latin ''quorum'', "of whom", genitive plural of ''qui'', "who". As a result, ''quora'' as plural of ''quorum'' is not a valid Latin formation. In modern times a quorum might be defined as the minimum number of voters needed for a valid election. In ''Robert's Rules of Order'' According to Robert, each as ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Logical Clock
A logical clock is a mechanism for capturing chronological and causal relationships in a distributed system. Often, distributed systems may have no physically synchronous global clock. In many applications (such as distributed GNU make), if two processes never interact, the lack of synchronization is unobservable and in these applications it is enough for the processes to agree on the event ordering (i.e., logical clock) rather than the wall-clock time. The first logical clock implementation, the Lamport timestamps, was proposed by Leslie Lamport in 1978 (Turing Award in 2013). Local vs global time In logical clock systems each process has two data structures: ''logical local time'' and ''logical global time''. Logical local time is used by the process to mark its own events, and logical global time is the local information about global time. A special protocol is used to update logical local time after each local event, and logical global time when processes exchange data. [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lamport's Bakery Algorithm
Lamport's bakery algorithm is a computer algorithm devised by computer scientist Leslie Lamport, as part of his long study of the formal correctness of concurrent systems, which is intended to improve the safety in the usage of shared resources among multiple threads by means of mutual exclusion. In computer science, it is common for multiple threads to simultaneously access the same resources. Data corruption can occur if two or more threads try to write into the same memory location, or if one thread reads a memory location before another has finished writing into it. Lamport's bakery algorithm is one of many mutual exclusion algorithms designed to prevent concurrent threads entering critical sections of code concurrently to eliminate the risk of data corruption. Algorithm Analogy Lamport envisioned a bakery with a numbering machine at its entrance so each customer is given a unique number. Numbers increase by one as customers enter the store. A global counter display ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ricart–Agrawala Algorithm
The Ricart–Agrawala algorithm is an algorithm for mutual exclusion on a distributed system. This algorithm is an extension and optimization of Lamport's Distributed Mutual Exclusion Algorithm, by removing the need for ack messages. It was developed by computer scientists Glenn Ricart and Ashok Agrawala. Algorithm Terminology * A ''site'' is any computing device which runs the Ricart-Agrawala Algorithm * The ''requesting site'' is the site which is requesting to enter the critical section. * The ''receiving site'' is every other site which is receiving a request from the requesting site. Algorithm Requesting Site * Sends a message to all sites. This message includes the site's name, and the current timestamp of the system according to its logical clock (''which is assumed to be synchronized with the other sites'') Receiving Site * Upon reception of a request message, immediately sending a timestamped ''reply'' message if and only if: :* the receiving process is not curre ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Raymond's Algorithm
Raymond's Algorithm is a lock based algorithm for mutual exclusion on a distributed system. It imposes a logical structure (a K-ary tree) on distributed resources. As defined, each node has only a single parent, to which all requests to attain the token are made. Algorithm Nodal properties # Each node has only one parent to whom received requests are forwarded # Each node maintains a FIFO queue of requests each time that it sees the token; # If any node is forwarding privilege to other node and has non-empty queue then it forwards a request message along Algorithm # If a node ''i'' (not holding the token) wishes to receive the token in order to enter into its critical section, it sends a request to its parent, node ''j''. #* If node ''j'' FIFO is empty, node ''j'' shifts ''i'' into its FIFO queue; ''j'' then issues a request to its parent, ''k'', that it desires the token #* If node ''j'' FIFO queue is ''not'' empty, it simply shifts ''i'' into the queue # When node ''k'' ha ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
