The impact of time on the session problem

ABSTRACT

The session problem is an abstraction of synchronization problems in distributed systems. It has been used as a test-case to demonstrate the differences in the time needed to solve problems in various timing models, for both shared memory (SM) systems [2] and message-passing (MP) systems [4]. In this paper, the session problem continues to be used to compare timing models quantitatively. The session problem is studied in two new timing models, the periodic and sporadic. Both SM and MP systems are considered. In the periodic model, each process takes steps at a constant unknown rate; different processes can have different rates. In the sporadic model, there exists a lower bound but no upper bound one step time, and message delay is bounded. We show upper and lower bounds on the time complexity of the session problem for these models. In addition, upper and lower bounds on running time are presented for the semi-synchronous SM model, closing an open problem from [4]. Our results suggest a hierarchy of various timing models in terms of time complexity for the session problem.

REFERENCES

• 1: Hagit Attiya , Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Bounds on the time to reach agreement in the presence of timing uncertainty, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.359-369, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103457]
• 2: Eshrat Arjomandi , Michael J. Fischer , Nancy A. Lynch, Efficiency of Synchronous Versus Asynchronous Distributed Systems, Journal of the ACM (JACM), v.30 n.3, p.449-456, July 1983 [doi>10.1145/2402.322387]
• 3: H. Attiya and N. A. Lynch, "Time Bounds for Real-Time Process Control in the Presence of Timing Uncertainty," Proc. l Oth Real- Time Systems $ymp., Dec. 1989, pp. 268-284.
• 4: H. Attiya and M. Mavronicolas, "Efficiency of Semi-Synchronous versus Asynchronous Networks," Proc. ~8th Allerton Conf. on Communicationsj Control and Computing, Oct. 1990~ pp. 578-587.
• 5: B. A. Coan and G. Thomas, "Agreeing on a Leader in Real-Time," Proc. 11th Real. Time Systems $ymp., Dec. 1990.
• 6: B.A. Coan and J. L. Welch, "Transaction Commit in a Realistic Timing Model," Distributed Computing, Vol. 4, 1990, pp. 87-103.
• 7: Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.1, p.77-97, Jan. 1987 [doi>10.1145/7531.7533]
• 8: C. Dwork, N. Lynch and L. Stockmeyer, "Consensus in the Presence of Partial Synchrony," SIAM Journal of Computing, Vol. 12, No. 13, Nov. 1983, pp. 656-666.
• 9: K. Jeffay, "The Real-Time Producer/Consumer Paradigm: A Paradigm for the Efficient, Predictable Real-Time System," University of North Carolina at Chapel Hill, Department of Computer Science, submitted for publication. April 1991.
• 10: K. Jeffay, D. F. Stanat and C. U. Mar{el, "On Optimal, Non-Preemptive Scheduling of Periodic and Sporadic Tasks," Proc. l~th IEEE Real-Time Systems $ymp., Dec. 1991, pp. 129- 139.
• 11: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 12: M. Mavronicolas, "Efficiency of Semi-Synchronous versus Asynchronous Systems: Atomic Shared Memory," TR-03-92, Aiken Computation Lab., Harvard University, Jan. 1992.
• 13: Stephen Ponzio, Consensus in the presence of timing uncertainty: omission and Byzantine failures (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.125-138, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112612]
• 14: Gary L. Peterson , Michael J. Fischer, Economical solutions for the critical section problem in a distributed system (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.91-97, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803398]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Message sending

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Algorithms, Theory, Verification