NDLI: Fast protocol transition in a distributed environment (brief announcement)

Please wait, while we are loading the content...

Distributed algorithms in TLA (abstract)

A middleware overview: goals, research issues, and coded examples (abstract)

Data communications vs. distributed computing (abstract)

How computer architecture trends may affect future distributed systems: from infiniBand clusters to inter-processor speculation (abstract)

Towards robust distributed systems (abstract)

Interval routing schemes allow broadcasting with linear message-complexity (extended abstract)

Optimal smoothing schedules for real-time streams (extended abstract)

Average-case analysis of greedy packet scheduling (extended astract)

Sparse communication networks and efficient routing in the plane (extended abstract)

Compact roundtrip routing in directed networks (extended abstract)

Laziness pays! using lazy synchronization mechanisms to improve non-blocking constructions

Long-lived and adaptive atomic snapshot and immediate snapshot (extended abstract)

Bounds on the shared memory requirements for long-lived & adaptive objects (extended abstract)

Adaptive and efficient mutual exclusion (extended abstract)

Assigning labels in unknown anonymous networks (extended abstract)

The wakeup problem in synchronous broadcast systems (extended abstract)

Random oracles in constantipole: practical asynchronous Byzantine agreement using cryptography (extended abstract)

Clock synchronization with faults and recoveries (extended abstract)

k-set agreement with limited accuracy failure detectors

Garbage collection of timestamped data in Stampede

On the interconnection of causal memory systems

Distributed reconfiguration of metamorphic robot chains

1/k phase stamping for continuous shared data (extended abstract)

$Π^{2}$ -- a generic proxy platform for wireless access and mobility in CORBA

High performance adaptive middleware for CORBA-based systems

Efficient atomic broadcast using deterministic merge

Achieving scalability and expressiveness in an Internet-scale event notification service

X-ability: a theory of replication

Debugging distributed programs using controlled re-execution

Self-stabilizing token circulation on asynchronous uniform unidirectional rings

Stable and fault-tolerant object allocation

Resettable vector clocks

Efficient generation of all regular non-dominated coteries

Indulgent algorithms (preliminary version)

Fast deterministic consensus in a noisy environment

Stability of long-lived consensus (extended abstract)

Toward a theory of maximally concurrent programs (shortened version)

A verification technique for self-stabilizing algorithms based on Ljapunov's ”Second Method“ (brief announcement)

Time and message-efficient S-based consensus (brief announcement)

Self-stabilization—beyond the token ring circulation (brief announcement)

Optimal implementation of the weakest failure detector for solving consensus (brief announcement)

Memory consistency and process coordination for SPARC v8 multiprocessors (brief announcement)

Deterministic distributed resource discovery (brief announcement)

Compact routing with stretch factor of less than three (brief announcement)

Specification, implementation and application of randomized regular registers (brief announcement)

Distributed cooperation in the absence of communication (brief announcement)

Average probe complexity of non-dominated coteries (brief announcement)

Fast protocol transition in a distributed environment (brief announcement)

Content Provider	ACM Digital Library
Author	Liu, Xiaoming van Renesse, Robbert
Abstract	Adaptivity is a desired feature of the distributed systems. Because many characteristics of the environment (network topology, active process distribution, etc.) may change from time to time, a good system should be able to adapt itself and perform sufficiently well under different conditions.Modern distributed systems are generally built from a set of components. Such a system has the freedom to adapt itself by switching from using one component to another. Because most components in the distributed systems are running protocols, an agreement must be achieved among the processes when doing the adaptation.The traditional approach to do the protocol switch is by using the two-phase-commit algorithm, in which a coordinator first broadcasts a “prepare” message, and all the other processes pause their work and send back acknowledgments. Each process is buffering messages from its own application at this point. After the coordinator receives all the acknowledgments, it broadcasts a “switch” message, and upon receiving which all the processes resume working using the new configuration. This approach is clean and easy to implement. However, it has two shortcomings: (1) the reconfiguration is not “smooth”, i.e.,, the overhead is large; (2) it is not scalable due to the centralized scheme. We propose a method which allows the protocol switch with very little overhead. It is scalable as well. The method is based on the fact that if two protocols P1 and P2 are derived from the same abstract specification AS, there exist converting functions ƒ and ƒ′ that can convert the local state of a process in one protocol to another. We can then build a hybrid protocol based on P1, P2, ƒ and ƒ′ that can make smooth adaptation at runtime.We briefly describe the generic algorithm of the hybrid protocol in three steps: (1) One process initiates the protocol switch by broadcasting a “switch” message; (2) When a process learns about the switching, it stops the current protocol by starting buffering application messages. It then sends out its information that other processes may need in order to convert their local states; (3) When a process gets all the needed information, it converts its local state to that of the new protocol using the converting function provided. It then starts working using the new protocol immediately. Each configuration is associated with a timestamp, which is tagged to the messages sent in that configuration. When a message with a timestamp greater than the local timestamp arrives, it gets buffered, and is processed after the local conversion finishes. To ensure that there is only one reconfiguration at any time, a token mechanism is being used. The hybrid protocol is smooth, because the protocol switch is not depend on the slowest process as in the two-phase-commit approach. It is efficient because the local state conversion saves many unnecessary memory operations. As an example, we apply our algorithm to two types of atomic broadcast protocols, namely, sequencer (S-)protocol and token (T-)protocol. In the S-protocol, each process has a buffer (Sbuƒ) holding the messages yet to be ordered by the sequencer. In the T-protocol, each process has a buffer (Tbuƒ) holding the messages to be broadcast when the token arrives. When switching from S-protocol to T-protocol, the sequencer sends out the information including the number of the messages from each process that have been ordered so far. Other processes convert by transferring the unordered messages from Sbuƒ to Tbuƒ. When switching from T-protocol to S-protocol, the process with the token sends the ordered information to the sequencer, and all the processes will transfer the messages in Tbuƒ to Sbuƒ by sending the message proposals to the sequencer.We implement the algorithm with our group communication toolkit. The following table shows the performance of the hybrid protocol (HY B) versus that of the two-phase-commit protocol (2pc). In the test, each process broadcasts 100 messages in each round, when a process receives all the messages in this round, it starts a new round. We switch the protocol every 3 rounds. The result being shown (in msec/round) is the average round latency of 100 rounds for 3 processes. The S-protocol and T-protocol data is of no protocol switch and just for the comparison. The algorithm works much better when the number of processes increases.Our algorithm provides a generic way of building efficient and scalable adaptive protocols. We believe it is a step towards the modular approach to adding new functionalities, such as adaptation, to the distributed systems.
File Format	PDF
ISBN	1581131836
DOI	10.1145/343477.362170
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2000-07-16
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Brief announcement: a fast distributed slicing algorithm ∗.

Brief Announcement : A Fast Distributed Slicing Algorithm

Brief Announcement: Towards Robust Medium Access in Multi-Hop Networks

Brief announcement: fast travellers: infrastructure-independent deadlock resolution in resource-restricted distributed systems.

Brief announcement: analysis of a randomized contention-resolution protocol for distributed access

Brief Announcement: Fast and Better Distributed MapReduce Algorithms for k-Center Clustering

Brief announcement: Stateless distributed algorithms for generalized packing linear programs

Brief announcement: queuing or priority queuing? on the design of cache-coherence protocols for distributed transactional memory.

Brief announcement: Super-fast t-ruling sets

Fast protocol transition in a distributed environment (brief announcement)

Similar Documents

Brief announcement: a fast distributed slicing algorithm ∗.

Brief Announcement : A Fast Distributed Slicing Algorithm

Brief Announcement: Towards Robust Medium Access in Multi-Hop Networks

Brief announcement: fast travellers: infrastructure-independent deadlock resolution in resource-restricted distributed systems.

Brief announcement: analysis of a randomized contention-resolution protocol for distributed access

Brief Announcement: Fast and Better Distributed MapReduce Algorithms for k-Center Clustering

Brief announcement: Stateless distributed algorithms for generalized packing linear programs

Brief announcement: queuing or priority queuing? on the design of cache-coherence protocols for distributed transactional memory.

Brief announcement: Super-fast t-ruling sets

Fast protocol transition in a distributed environment (brief announcement)