A note on reliable full-duplex transmission over half-duplex links

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A note on reliable full-duplex transmission over half-duplex links

Full text

Pdf (271 KB)

Source

Communications of the ACM archive
Volume 12 , Issue 5 (May 1969) table of contents

Pages: 260 - 261

Year of Publication: 1969

ISSN:0001-0782

Authors

K. A. Bartlett	National Physical Lab., Teddington, England
R. A. Scantlebury	National Physical Lab., Teddington, England
P. T. Wilkinson	National Physical Lab., Teddington, England

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 85, Citation Count: 92

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/362946.362970 What is a DOI?

Warning: The download time has expired please click on the item to try again.

ABSTRACT

A simple procedure for achieving reliable full-duplex transmission over half-duplex links is proposed. The scheme is compared with another of the same type, which has recently been described in the literature. Finally, some comments are made on another group of related transmission procedures which have been shown to be unreliable under some circumstances.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	W. C. Lynch, Computer Systems: Reliable full-duplex file transmission over half-duplex telephone line, Communications of the ACM, v.11 n.6, p.407-410, June 1968 [doi>10.1145/363347.363366]
	2	Bartlett, K. A. Transmission control in a local data network. Proc. IFIP Cong. 1968 (to be published).

CITED BY 92

	Rance Cleaveland , Joachim Parrow , Bernhard Steffen, The concurrency workbench: a semantics-based tool for the verification of concurrent systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.1, p.36-72, Jan. 1993
	E. M. Clarke , E. A. Emerson , A. P. Sistla, Automatic verification of finite-state concurrent systems using temporal logic specifications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.2, p.244-263, April 1986
	G. M. Brown , M. G. Gouda , R. E. Miller, Block acknowledgement: redesigning the window protocol, ACM SIGCOMM Computer Communication Review, v.19 n.4, p.128-135, Sep. 1989
	Da-Wei Wang , L. D. Zuck, Tight bounds for the sequence transmission problem, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.73-83, June 1989, Edmonton, Alberta, Canada
	Ana R. Cavalli, A method of automatic proof for the specification and verification of protocols, ACM SIGCOMM Computer Communication Review, v.14 n.2, p.100-106, June 1984
	Ewan Tempero , Richard Ladner, Tight bounds for weakly bounded protocols, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.205-218, August 22-24, 1990, Quebec City, Quebec, Canada
	C. H. Chow , S. S. Lam, PROSPEC: An Interactive Programming Environment for Designing and Verifying Communication Protocols, IEEE Transactions on Software Engineering, v.14 n.3, p.327-338, March 1988
	Andrew A. Hanish , Tharam S. Dillon, Communication protocol design to facilitate re-use based on the object-oriented paradigm, Mobile Networks and Applications, v.2 n.3, p.285-301, Dec. 1997
	Beverly Sanders, A predicate transformer approach to knowledge and knowledge-based protocols (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.217-230, August 19-21, 1991, Montreal, Quebec, Canada
	Daniel Brand , Pitro Zafiropulo, On Communicating Finite-State Machines, Journal of the ACM (JACM), v.30 n.2, p.323-342, April 1983
	C. J. Funk , W. G. Bulgren, An improved full-duplex retransmission technique, Proceedings of the annual conference, p.27-34, August 27-29, 1973, Atlanta, Georgia, United States
	Yehuda Afek , Eli Gafni, Bootstrap network resynchronization (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.295-307, August 19-21, 1991, Montreal, Quebec, Canada
	K. L. Calvert , S. S. Lam, Deriving a protocol converter: a top-down method, ACM SIGCOMM Computer Communication Review, v.19 n.4, p.247-258, Sep. 1989
	H P Lin, Modeling a transport layer protocol using first-order logic, ACM SIGCOMM Computer Communication Review, v.16 n.3, p.92-100, Aug. 5, 1986
	Ewan D. Tempero , Richard E. Ladner, Recoverable sequence transmission protocols, Journal of the ACM (JACM), v.42 n.5, p.1059-1090, Sept. 1995
	Ronald Fagin , Yoram Moses , Joseph Y. Halpern , Moshe Y. Vardi, Knowledge-based programs, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.153-163, August 20-23, 1995, Ottowa, Ontario, Canada
	Roberto Baldoni, A Positive Acknowledgment Protocol for Causal Broadcasting, IEEE Transactions on Computers, v.47 n.12, p.1341-1350, December 1998
	Yishay Mansour , Baruch Schieber, The intractability of bounded protocols for on-line sequence transmission over non-FIFO channels, Journal of the ACM (JACM), v.39 n.4, p.783-799, Oct. 1992
	Yehuda Afek , Hagit Attiya , Alan Fekete , Michael Fischer , Nancy Lynch , Yishay Mansour , Dai-Wei Wang , Lenore Zuck, Reliable communication over unreliable channels, Journal of the ACM (JACM), v.41 n.6, p.1267-1297, Nov. 1994
	Gleb N. Naumovich , Lori A. Clarke , Leon J. Osterweil, Verification of communication protocols using data flow analysis, ACM SIGSOFT Software Engineering Notes, v.21 n.6, p.93-105, Nov. 1996
	Y. Mansour , B. Schieber, The intractability of bounded protocols for non-FIFO channels, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.59-72, June 1989, Edmonton, Alberta, Canada
	Shlomi Dolev , Amos Israeli , Shlomo Moran, Resource bounds for self stabilizing message driven protocols, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.281-293, August 19-21, 1991, Montreal, Quebec, Canada
	Gerard J. Holzmann , Margaret H. Smith, A practical method for verifying event-driven software, Proceedings of the 21st international conference on Software engineering, p.597-607, May 16-22, 1999, Los Angeles, California, United States
	Joseph Y. Halpern, A little knowledge goes a long way: simple knowledge-based derivations and correctness proofs for a family of protocols, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.269-280, August 10-12, 1987, Vancouver, British Columbia, Canada
	E. M. Clarke , E. A. Emerson , A. P. Sistla, Automatic verification of finite state concurrent system using temporal logic specifications: a practical approach, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.117-126, January 24-26, 1983, Austin, Texas
	Miguel García Hoffmann, Hardware implementation of communication protocols: A formal approach, Proceedings of the 7th annual symposium on Computer Architecture, p.253-263, May 06-08, 1980, La Baule, United States
	R. A. Scantlebury, A model for the local area of a data communication network objectives and hardware organization, Proceedings of the first ACM symposium on Problems in the optimization of data communications systems, p.183-204, October 13-16, 1969, Pine Mountain, Georgia, United States
	Paul V. Mockapetris, Analysis of reliable multicast algorithms for local networks, ACM SIGCOMM Computer Communication Review, v.13 n.4, p.150-157, October 1983
	S. Aggarwal , C. Courcoubetis , P. Wolper, Adding liveness properties to coupled finite-state machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.2, p.303-339, April 1990
	Jayadev Misra, A Simple, Object-Based View of Multiprogramming, Formal Methods in System Design, v.20 n.1, p.23-45, January 2002
	Da-Wei Wang , Lenore Zuck, Real-time sequence transmission problem, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.111-123, August 19-21, 1991, Montreal, Quebec, Canada
	Joseph Y. Halpern , Lenore D. Zuck, A little knowledge goes a long way: knowledge-based derivations and correctness proofs for a family of protocols, Journal of the ACM (JACM), v.39 n.3, p.449-478, July 1992
	Wei Jen Yeh , Michal Young, Compositional reachability analysis using process algebra, Proceedings of the symposium on Testing, analysis, and verification, p.49-59, October 08-10, 1991, Victoria, British Columbia, Canada
	Pramod V. Koppol , Richard H. Carver , Kuo-Chung Tai, Incremental Integration Testing of Concurrent Programs, IEEE Transactions on Software Engineering, v.28 n.6, p.607-623, June 2002
	Mohammed G. Gouda , Chung-Kuo Chang, Proving liveness for networks of communicating finite state machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.1, p.154-180, Jan. 1986
	Micah Adler , Faith Fich, The complexity of end-to-end communication in memoryless networks, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.239-248, May 04-06, 1999, Atlanta, Georgia, United States
	Alan Fekete , Nancy Lynch , Yishay Mansour , John Spinelli, The impossibility of implementing reliable communication in the face of crashes, Journal of the ACM (JACM), v.40 n.5, p.1087-1107, Nov. 1993
	Baruch Awerbuch , Oded Godlreich , Amir Herzberg, A quantitative approach to dynamic networks, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.189-203, August 22-24, 1990, Quebec City, Quebec, Canada
	Wuxu Peng , S. Puroshothaman, Data flow analysis of communicating finite state machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.3, p.399-442, July 1991
	Patrice Godefroid , David E. Long, Symbolic Protocol Verification with Queue BDDs, Formal Methods in System Design, v.14 n.3, p.257-271, May 1999
	L. Pouzin, Basic elements of a network data link control procedure (NDLC), ACM SIGCOMM Computer Communication Review, v.5 n.1, p.6-23, January 1975
	Mohamed Jmaiel , Peter Pepper, Development of communication protocols using algebraic and temporal specifications, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.42 n.6, p.737-764, 21 August 2003
	Gérard Cécé , Alain Finkel, Verification of programs with half-duplex communication, Information and Computation, v.202 n.2, p.166-190, 1 November, 2005
	Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003
	Z Bavel , J Grzymala-Busse , Y Hsia , R Mancisidor-Landa, Tier automation representation of communication protocols, ACM SIGCOMM Computer Communication Review, v.16 n.3, p.138-147, Aug. 5, 1986
	Gérard Cécé , Alain Finkel , S. Purushothaman Iyer, Duplication, insertion and lossiness errors in unreliable communication channels, ACM SIGSOFT Software Engineering Notes, v.19 n.5, p.35-43, Dec. 1994
	T. T. Lee , M. Y. Lai, A Relational Algebraic Approach to Protocol Verification, IEEE Transactions on Software Engineering, v.14 n.2, p.184-193, February 1988
	Z. Bavel , J. W. Gfrzymala-Busse , Y-T. Hsia, New communication protocols from old, ACM SIGCOMM Computer Communication Review, v.17 n.5, p.136-150, Oct./Nov. 1987
	Eli Gafni , Yehuda Afek, End-to-end communication in unreliable networks, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.131-148, August 15-17, 1988, Toronto, Ontario, Canada
	Ichiro Suzuki , Harngdar Lu, Temporal Petri Nets and Their Application to Modeling and Analysis of a Handshake Daisy Chain Arbiter, IEEE Transactions on Computers, v.38 n.5, p.696-704, May 1989
	Ichiro Suzuki, Formal Analysis of the Alternating Bit Protocol by Temporal Petri Nets, IEEE Transactions on Software Engineering, v.16 n.11, p.1273-1281, November 1990
	Robert E. Kahn , William R. Crowther, Flow control in a resource-sharing computer network, Proceedings of the ACM second symposium on Problems in the optimizations of data communications systems, p.108-116, January 1971
	Shlomi Dolev , Jennifer L. Welch, Crash Resilient Communication in Dynamic Networks, IEEE Transactions on Computers, v.46 n.1, p.14-26, January 1997
	Martin Campbell-Kelly, Data communications at the national physical laboratory (1965-1975), IEEE Annals of the History of Computing, v.9 n.3-4, p.221-247, Jan. 1988
	Alan S. Wenban , John W. O'Leary , Geoffrey M. Brown, Codesign of Communication Protocols, Computer, v.26 n.12, p.46-52, December 1993
	Marco Bernardo, Symbolic semantic rules for producing compact STGLAs from value passing process descriptions, ACM Transactions on Computational Logic (TOCL), v.5 n.3, p.436-469, July 2004
	Shamimabi Paurobally , Jim Cunningham , Nicholas R. Jennings, Ensuring consistency in the joint beliefs of interacting agents, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia
	G. J. Holzmann , M. H. Smith, An Automated Verification Method for Distributed Systems Software Based on Model Extraction, IEEE Transactions on Software Engineering, v.28 n.4, p.364-377, April 2002
	Dirk Bull , Pieter de Villiers, Using SPIN to verify protocols at the implementation level, Proceedings of the 2002 annual research conference of the South African institute of computer scientists and information technologists on Enablement through technology, September 16-18, 2002, Port Elizabeth, South Africa
	A critical study of different flow control methods in computer networks, ACM SIGCOMM Computer Communication Review, v.9 n.3, p.23-32, July 1979
	Bernard Berthomieu , Michel Diaz, Modeling and Verification of Time Dependent Systems Using Time Petri Nets, IEEE Transactions on Software Engineering, v.17 n.3, p.259-273, March 1991
	Jaco Geldenhuys , Antti Valmari, More efficient on-the-fly LTL verification with Tarjan's algorithm, Theoretical Computer Science, v.345 n.1, p.60-82, 21 November 2005
	Gregor V. Bochmann, Communication protocols and error recovery procedures, ACM SIGOPS Operating Systems Review, v.9 n.3, p.45-50, July 1975
	Giacomo Bucci , Enrico Vicario, Compositional Validation of Time-Critical Systems Using Communicating Time Petri Nets, IEEE Transactions on Software Engineering, v.21 n.12, p.969-992, December 1995
	Sylvie Delaët , Sébastien Tixeuil, Tolerating transient and intermittent failures, Journal of Parallel and Distributed Computing, v.62 n.5, p.961-981, May 2002
	Jeffrey J. P. Tsai , Eric Y. T. Juan , Avinash Sahay, Model and Algorithm for Efficient Verification of High-Assurance Properties of Real-Time Systems, IEEE Transactions on Knowledge and Data Engineering, v.15 n.2, p.405-422, February 2003
	Yehuda Afek , Geoffrey M. Brown, Self-stabilization over unreliable communication media, Distributed Computing, v.7 n.1, p.27-34, November 1993
	Satoshi Yamane, Automatic effective verification method for distributed and concurrent systems using timed language inclusion, Engineering of distributed control systems, Nova Science Publishers, Inc., Commack, NY, 2001
	Antti Valmari, Composition and abstraction, Modeling and verification of parallel processes, Springer-Verlag New York, Inc., New York, NY, 2001
	Pierre Wolper, Expressing interesting properties of programs in propositional temporal logic, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.184-193, January 01, 1986, St. Petersburg Beach, Florida
	Bernd Finkbeiner , Sriram Sankaranarayanan , Henny B. Sipma, Collecting Statistics Over Runtime Executions, Formal Methods in System Design, v.27 n.3, p.253-274, November 2005
	Jonathan Billington , Guy Edward Gallasch , Laure Petrucci, Fast verification of the class of stop-and-wait protocols modelled by coloured Petri nets, Nordic Journal of Computing, v.12 n.3, p.251-274, September 2005
	Natalia López , Manuel Núñez , Ismael Rodríguez, Specification, testing and implementation relations for symbolic-probabilistic systems, Theoretical Computer Science, v.353 n.1, p.228-248, 14 March 2006
	Pierre Fraigniaud , Cyril Gavoille, Header-size lower bounds for end-to-end communication in memoryless networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.10, p.1630-1638, 14 July 2006
	Bernard Boigelot , Patrice Godefroid, Symbolic Verification of Communication Protocols with Infinite StateSpaces using QDDs, Formal Methods in System Design, v.14 n.3, p.237-255, May 1999
	J. Billington , G. R. Wheeler , M. C. Wilbur-Ham, PROTEAN: A High-Level Petri Net Tool for the Specification and Verification of Communication Protocols, IEEE Transactions on Software Engineering, v.14 n.3, p.301-316, March 1988
	Lawrence G. Roberts, Extensions of packet communication technology to a hand held personal terminal, Proceedings of the November 16-18, 1971, fall joint computer conference, November 16-18, 1971, Las Vegas, Nevada
	Agata Janowska , Paweł Janowski, Slicing of Timed Automata with Discrete Data, Fundamenta Informaticae, v.72 n.1-3, p.181-195, January 2006
	F. Cicirelli , A. Furfaro , L. Nigro, An Approach to Protocol Modeling and Validation, Proceedings of the 39th annual Symposium on Simulation, p.261-268, April 02-06, 2006
	E. Allen Emerson , Chin-Laung Lei, Modalities for model checking (extended abstract): branching time strikes back, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.84-96, January 14-16, 1985, New Orleans, Louisiana, United States
	L. J. Steggles , P. Kosiuczenko, A Formal Model for SDL Specifications Based on Timed Rewriting Logic, Automated Software Engineering, v.7 n.1, p.61-90, March 2000
	Sven Ubik, Possibilities of using protocol converters for NIR system construction, ACM SIGCOMM Computer Communication Review, v.27 n.2, p.37-48, Apr. 1997
	J. Dähler , P. Gerber , H.-P. Gisiger , A. Kündig, A graphical tool for the design and prototyping of distributed systems, ACM SIGSOFT Software Engineering Notes, v.12 n.3, p.25-36, July 1987
	Kai Engelhardt , Yoram Moses, Single-bit messages are insufficient for data link over duplicating channels, Information Processing Letters, v.107 n.6, p.235-239, August, 2008
	J. M. McQuillan , W. R. Crowther , B. P. Cosell , D. C. Walden , F. E. Heart, Improvements in the design and performance of the ARPA network, Proceedings of the December 5-7, 1972, fall joint computer conference, part II, December 05-07, 1972, Anaheim, California
	William T. Overman , Stephen D. Crocker , Vittal Kini, A multiprocessor description language, Proceedings of the May 4-7, 1981, national computer conference, May 04-07, 1981, Chicago, Illinois
	Emil Sekerinski, An Algebraic Approach to Refinement with Fair Choice, Electronic Notes in Theoretical Computer Science (ENTCS), 214, p.51-79, June, 2008
	Octavian Udrea , Cristian Lumezanu , Jeffrey S. Foster, Rule-based static analysis of network protocol implementations, Information and Computation, v.206 n.2-4, p.130-157, February, 2008
	Andrzej Zbrzezny , Agata Półrola, SAT-Based Reachability Checking for Timed Automata with Discrete Data, Fundamenta Informaticae, v.79 n.3-4, p.579-593, August 2007
	Y. Yang , A. Mannani , P. Gohari, Implementation of supervisory control using extended finite-state machines, International Journal of Systems Science, v.39 n.12, p.1115-1125, December 2008
	Pawel Gburzynski , Bozena Kaminska , Ashikur Rahman, On reliable transmission of data over simple wireless channels, Journal of Computer Systems, Networks, and Communications, 2009, p.1-14, January 2009
	Tim Lewis , Russell J. Haines, Formal verification to enhance evolution of protocols, Proceedings of the 11th Annual conference on Genetic and evolutionary computation, July 08-12, 2009, Montreal, Québec, Canada