This paper discusses a powerful priority mechanism that can be used on a physical communication medium supporting multiple, independent, logical data links. This scheme allows a high priority message to immediately interrupt a lower priority message which is in the process of being transmitted, and yet will not require the retransmission of the first part of the lower priority message; hence, the term graceful preemption. Graceful preemption may be extended to furnish multiple priority levels similar to existing processor interrupt structures which implement multiple levels. This protocol may serve a single processor which handles several different processes, or several independent stations that share a common bus. Hence, priority levels can be enforced without the need for a centralized bus “master” or “arbitrator” unit. As an example, the application of graceful preemption to the Integrated Services Digital Network (ISDN) link access procedure, LAPD, is discussed.