More Web Proxy on the site http://driver.im/

research-article

Elections in a Distributed Computing System

Author:

H. Garcia-MolinaAuthors Info & Claims

IEEE Transactions on Computers, Volume 31, Issue 1

Pages 48 - 59

https://doi.org/10.1109/TC.1982.1675885

Published: 01 January 1982 Publication History

Abstract

After a failure occurs in a distributed computing system, it is often necessary to reorganize the active nodes so that they can continue to perform a useful task. The first step in such a reorganization or reconfiguration is to elect a coordinator node to manage the operation. This paper discusses such elections and reorganizations. Two types of reasonable failure environments are studied. For each environment assertions which define the meaning of an election are presented. An election algorithm which satisfies the assertions is presented for each environment.

References

[1]

E. R. Berlekamp, Algebraic Coding Theory, New York: McGraw-Hill, 1968.

[2]

E. W. Dijkstra, "Solution of a problem in concurrent programming control," Commun. Ass. Comput. Mach., vol. 8, p. 569, Sept. 1965.

Digital Library

[3]

C. A. Ellis, "Consistency and correctness of dupliicate database systems," in Proc. 6th Symp. Operating Syst. Principles, Nov. 1977, pp. 67-84.

Digital Library

[4]

P. H. Enslow, "What is a distributed data processing system?," Computer, pp. 13-21, Jan. 1978.

Digital Library

[5]

H. Garcia-Molina, "Performance of update algorithms for replicated data in a distributed database," Dep. Comput. Sci., Stanford Univ., Stanford, CA, Rep. STAN-CS-79-744, June 1979.

[6]

J. N. Gray, "Notes on database operating systems," in Advanced Course on Operating System Principles. Munich, West Germany: Technical Univ., July 1977.

Digital Library

[7]

L. Lamport, "A new solution of Dijkstra's concurrent programming problems," Commun. Ass. Comput. Mach., vol. 17, pp. 453-455, Aug. 1974.

Digital Library

[8]

L. Lamport, "Time, clocks, and the ordering of events in a distributed system," Commun. Ass. Comput. Mach., vol. 21, pp. 558-564, July 1978.

Digital Library

[9]

L. Lamport, "The implementation of reliable distributed systems," Comput. Networks, vol. 2, pp. 95-114, 1978.

[10]

B. W. Lampson and H. E. Sturgis, "Crash recovery in a distributed data storage systems," Xerox PARC Rep., 1979.

[11]

G. Le Lann, "Distributed systems-Towards a formal approach," in Information Processing 77, B. Gilchrist, Ed. Amsterdam, The Netherlands: North-Holland, 1977, pp. 155-160.

[12]

D. A. Menasce, G. J. Popeck, and R. R. Muntz, "A locking protocol for resource coordination in disiributed databases," ACM Trans. Database Syst. vol. 5, pp. 103-138, June 1980.

Digital Library

[13]

R. M. Metcalfe and D. R. Boggs, "Ethernet: Distributed packet switching for local computer networks," Commun. Ass. Comput. Mach., vol. 19, pp. 395-404, July 1976.

Digital Library

[14]

D. S. Parker et al., "Detection of mutual inconsistency in distributed systems." in Proc. 5th Berkeley Workshop Distributed Data Management Comput. Networks, Feb. 1981, pp. 172-184.

[15]

M. O. Rabin, "N-process synchronization by 4 log (base 2) N-valued shared variable," in Proc. 21th Annu. Symp. Foundations Comput. Sci., Oct. 1980, pp. 407-410.

Digital Library

[16]

J. B. Rothnie and N. Goodman, "A survey of research and development in distributed database management," in Proc. 3rd VLDB Conf., Tokyo, Japan, 1977, pp. 48-62.

Digital Library

[17]

F. B. Schneider, "Synchronization in distributed programs," Dep. Comput. Sci., Cornell Univ., Ithaca, NY, Tech. Rep. TR79-391, Jan. 1980.

[18]

R. G. Smith, "The contract net protocol: High level communication and control in a distributed problem solver," in Proc. 1st Int. Conf. Distributed Comput. Syst., Huntsville, AL, Oct. 1979, pp. 185-192.

[19]

M. Stonebraker, "Concurrency control and consistency of multiple copies of data in distributed INGRES," IEEE Trans. Software Eng., vol. SE-5, pp. 188-194, May 1979.

Digital Library

[20]

R. H. Thomas, "A majority consensus approach to concurrency control," ACM Trans. Database Syst., vol. 4, pp. 180-209, June 1979.

Digital Library

Cited By

Chu TLaoutaris N(2024)FedQV: Leveraging Quadratic Voting in Federated LearningProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36560068:2(1-36)Online publication date: 29-May-2024
https://dl.acm.org/doi/10.1145/3656006
Di Stefano LLang F(2024)Compositional verification of priority systems using sharp bisimulationFormal Methods in System Design10.1007/s10703-023-00422-162:1-3(1-40)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10703-023-00422-1
Liao YXu YXu HWang LQian CQiao C(2023)Decentralized Federated Learning With Adaptive Configuration for Heterogeneous ParticipantsIEEE Transactions on Mobile Computing10.1109/TMC.2023.333540323:6(7453-7469)Online publication date: 22-Nov-2023
https://dl.acm.org/doi/10.1109/TMC.2023.3335403
Show More Cited By

Elections in a Distributed Computing System
1. Software and its engineering
  1. Software organization and properties
    1. Software system structures

Recommendations

Efficient Rollback-Recovery Technique in Distributed Computing Systems

In this paper we propose a new approach for implementing rollback-recovery in a distributed computing system. A concept of logical ring is introduced for the maintenance of information required for consistent recovery from a system crash. Message ...
A Formal Model of Crash Recovery in a Distributed System

A formal model for atomic commit protocols for a distributed database system is introduced. The model is used to prove existence results about resilient protocols for site failures that do not partition the network and then for partitioned networks. For ...
How hard is control in single-crossing elections?

Election control problems model situations where some entity (traditionally called the election chair) wants to ensure some candidate's victory by either adding or deleting candidates or voters. The complexity of deciding if such control actions can be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 31, Issue 1

January 1982

90 pages

ISSN:0018-9340

Issue’s Table of Contents

Copyright © 1982.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 January 1982

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

111
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chu TLaoutaris N(2024)FedQV: Leveraging Quadratic Voting in Federated LearningProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36560068:2(1-36)Online publication date: 29-May-2024
https://dl.acm.org/doi/10.1145/3656006
Di Stefano LLang F(2024)Compositional verification of priority systems using sharp bisimulationFormal Methods in System Design10.1007/s10703-023-00422-162:1-3(1-40)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10703-023-00422-1
Liao YXu YXu HWang LQian CQiao C(2023)Decentralized Federated Learning With Adaptive Configuration for Heterogeneous ParticipantsIEEE Transactions on Mobile Computing10.1109/TMC.2023.333540323:6(7453-7469)Online publication date: 22-Nov-2023
https://dl.acm.org/doi/10.1109/TMC.2023.3335403
Das RSidhanta S(2023)Live Migration of Containers in the EdgeSN Computer Science10.1007/s42979-023-01871-54:5Online publication date: 24-Jun-2023
https://dl.acm.org/doi/10.1007/s42979-023-01871-5
Guerrero-Contreras GBalderas-Díaz SGarrido JRodríguez-Fórtiz MO’Hare G(2023)Proposal and comparative analysis of a voting-based election algorithm for managing service replication in MANETsApplied Intelligence10.1007/s10489-023-04506-753:16(19563-19590)Online publication date: 9-Mar-2023
https://dl.acm.org/doi/10.1007/s10489-023-04506-7
Di Stefano LLang F(2023)Compositional Verification of Stigmergic Collective SystemsVerification, Model Checking, and Abstract Interpretation10.1007/978-3-031-24950-1_8(155-176)Online publication date: 16-Jan-2023
https://dl.acm.org/doi/10.1007/978-3-031-24950-1_8
Grossi DPelachaud CTaylor MFaliszewski PMascardi V(2022)Social Choice Around the Block: On the Computational Social Choice of BlockchainProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems10.5555/3535850.3536111(1788-1793)Online publication date: 9-May-2022
https://dl.acm.org/doi/10.5555/3535850.3536111
Yang YZhang Q(2022)Research on Security Technologies for Open Reconfigurable Routing and Switching PlatformsProceedings of the 4th International Electronics Communication Conference10.1145/3560089.3560101(74-79)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3560089.3560101
Keller PBöhme RHerlihy MNarula N(2022)Parallel Proof-of-Work with Concrete BoundsProceedings of the 4th ACM Conference on Advances in Financial Technologies10.1145/3558535.3559773(1-15)Online publication date: 19-Sep-2022
https://dl.acm.org/doi/10.1145/3558535.3559773
Silva MTeles ALopes RSilva FViana DCoutinho LGupta NEndler M(2022)Neighborhood-aware Mobile Hub: An Edge Gateway with Leader Election Mechanism for Internet of Mobile ThingsMobile Networks and Applications10.1007/s11036-020-01630-327:1(276-289)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s11036-020-01630-3
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents