Article

Free access

Time-adaptive algorithms for synchronization

Authors:

Rajeev Alur,

Hagit Attiya,

Gadi TaubenfeldAuthors Info & Claims

STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing

Pages 800 - 809

https://doi.org/10.1145/195058.195464

Published: 23 May 1994 Publication History

PDF eReader

References

[1]

R. Alur and G. Taubenfeld. Results about fast mutual exclusion. In Proc. o} the 13th IEEE Real-Time Systems Syrup, pp. 12-21, 1992.

Crossref

Google Scholar

[2]

R. Alur and G. Taubenfeld. How to share an object: A fast timing-based solution. In Proc. of the 5th IEEE Syrup. on Parallel and Distributed Processing, pp. 470-477, 1993.

Digital Library

Google Scholar

[3]

H. Attiya, C. Dwork, N. Lynch and L. Stockmeyer. Bounds on the time to reach agreement in the presence of timing uncertainty. In Proc. of the 23rd A CM Syrup. on Theory of Computing, pp. 359-369, 1991. To appear in Journal of the A CM.

Digital Library

Google Scholar

[4]

D. Dolev, C. Dwork, and L. Stockmeyer. On the minimal synchronism needed for distributed consensus. Journal of the ACM, 34(1):77-97, 1987.

Digital Library

Google Scholar

[5]

E. W. Dijkstra. Solution of a problem in concurrent programming control. Communications of the A CM, 8(9):569, 1965.

Digital Library

Google Scholar

[6]

C. Dwork, N. Lynch, and L. Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288-323, 1988.

Digital Library

Google Scholar

[7]

M. Fischer, N. Lynch, and M. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the A CM, 32(2):374-382, 1985.

Digital Library

Google Scholar

[8]

M. Herlihy. Wait-free synchronization. A CM Trans. on Programming Languages and System, s, 11(1):124- 149, 1991.

Digital Library

Google Scholar

[9]

A. Herzberg and S. Kutten. Efficient detection of message forwarding faults. In Proc. of the 8th A CM Syrup. on Principles of Distributed Computing, pp. 339-353, 1989.

Digital Library

Google Scholar

[10]

M. Loui and H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Reseats:h, 4:163-183, 1987.

Google Scholar

[11]

L. Lamport. A fast mutual exclusion algorithm. ACM Trans. on Computer Systems, 5(1):1-11, 1987.

Digital Library

Google Scholar

[12]

N. Lynch and N. Shavit. Timing-based mutual exclusion. In Proc. of the 13th IEEE Real-'.l ime Systems Syrup, pp. 2-11, 1992.

Crossref

Google Scholar

[13]

M. Pease, R. Shostak, and L. Lamport. }teaching agreement in the presence of faults. Journal of the ACM, 27(2):228-234, 1980.

Digital Library

Google Scholar

Cited By

View all

Permiashkin D(2023)On Solving Concurrent Process Problem in Process-Oriented ProgramsVestnik NSU. Series: Information Technologies10.25205/1818-7900-2023-21-2-5-1721:2(5-17)Online publication date: 5-Oct-2023
https://doi.org/10.25205/1818-7900-2023-21-2-5-17
Henzinger TKopke P(2005)Verification methods for the divergent runs of clock systemsFormal Techniques in Real-Time and Fault-Tolerant Systems10.1007/3-540-58468-4_173(351-372)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-58468-4_173
Anderson JKim YHerman T(2003)Shared-memory mutual exclusionDistributed Computing10.1007/s00446-003-0088-616:2-3(75-110)Online publication date: 1-Sep-2003
https://dl.acm.org/doi/10.1007/s00446-003-0088-6
Show More Cited By

Index Terms

Time-adaptive algorithms for synchronization

Recommendations

Adaptive Internal Clock Synchronization
SRDS '08: Proceedings of the 2008 Symposium on Reliable Distributed Systems

Existing clock synchronization algorithms assume a bounded clock reading error. This, in turn, results in an inflexible design that typically requires node crashes whenever the given bound might be violated. We propose a novel, adaptive internal clock ...
Adaptive time synchronization for wireless sensor networks with self-calibration
ICC'09: Proceedings of the 2009 IEEE international conference on Communications

Time synchronization is important for wireless sensor networks because it facilitates cooperation among nodes and helps raise power efficiency. Time synchronization protocols like TPSN, RBS and FTSP have provided great schemes to fulfill fast ...
Rate-adaptive time synchronization for long-lived sensor networks
SIGMETRICS '05: Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

Time synchronization is critical to sensor networks at many layers of its design and enables better duty-cycling of the radio, accurate localization, beamforming and other collaborative signal processing. While there has been significant work in sensor ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing

May 1994

822 pages

ISBN:0897916638

DOI:10.1145/195058

Chairmen:
F. Tom Leighton
Massachusetts Institue of Technology, Cambridge
,
Michael Goodrich
Johns Hopkins Univ., Baltimore, MD

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 May 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC94

Sponsor:

SIGACT

STOC94: Symposium on Theory of Computing

May 23 - 25, 1994

Quebec, Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
314
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)8

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Permiashkin D(2023)On Solving Concurrent Process Problem in Process-Oriented ProgramsVestnik NSU. Series: Information Technologies10.25205/1818-7900-2023-21-2-5-1721:2(5-17)Online publication date: 5-Oct-2023
https://doi.org/10.25205/1818-7900-2023-21-2-5-17
Henzinger TKopke P(2005)Verification methods for the divergent runs of clock systemsFormal Techniques in Real-Time and Fault-Tolerant Systems10.1007/3-540-58468-4_173(351-372)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-58468-4_173
Anderson JKim YHerman T(2003)Shared-memory mutual exclusionDistributed Computing10.1007/s00446-003-0088-616:2-3(75-110)Online publication date: 1-Sep-2003
https://dl.acm.org/doi/10.1007/s00446-003-0088-6
Aspnes JLeighton FShor P(1997)Lower bounds for distributed coin-flipping and randomized consensusProceedings of the twenty-ninth annual ACM symposium on Theory of computing10.1145/258533.258649(559-568)Online publication date: 4-May-1997
https://dl.acm.org/doi/10.1145/258533.258649
Ramamurthy SMoir MAnderson JBurns JMoses Y(1996)Real-time object sharing with minimal system supportProceedings of the fifteenth annual ACM symposium on Principles of distributed computing10.1145/248052.248098(233-242)Online publication date: 1-May-1996
https://dl.acm.org/doi/10.1145/248052.248098
Alur RTaubenfeld G(1996)Fast timing-based algorithmsDistributed Computing10.1007/s00446005002010:1(1-10)Online publication date: 1-Jul-1996
https://dl.acm.org/doi/10.1007/s004460050020
Alur RHenzinger T(1994)Finitary fairnessProceedings Ninth Annual IEEE Symposium on Logic in Computer Science10.1109/LICS.1994.316087(52-61)Online publication date: 1994
https://doi.org/10.1109/LICS.1994.316087

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Adaptive Internal Clock Synchronization

Adaptive time synchronization for wireless sensor networks with self-calibration

Rate-adaptive time synchronization for long-lived sensor networks