Proposer: M.A. Bonuccelli
With the term distributed system we mean a system with no centralized, shared memory. This definition is very broad: many real life systems, like computer networks, or distributed memory multiprocessors, falling into it. In spite of this generality, it is possible to produce abstract models capturing the essential features shared by all distributed systems, ignoring the unimportant physical details. In this project we address two specific problems, namely packet scheduling and clock synchronization, formulated on general models of distributed systems. This allows to aply the obtained results in a wide variety of situations.
Technology alone is not a panacea: a user's uncontrolled access to the common medium may result in a poor utilization of the common resource, causing a degradation of the overall network performance, thus eliminating the benefits of the costly new adopted solutions. We believe that the realization of high-speed, high performance, cost-effective, reliable and transparent networking and distributed computing requires new approaches, based on sophisticated algorithmic solutions. When such solutions turn out to be impractical, the obtained results can be used as fundamental limits to more practical approaches, and thus contribute to form a foundation of distributed computing. It is the purpose of this proposal to investigate and experimentally evaluate such approaches.
The scheduling problems, subject of the present proposal, occur in the so-called single-hop communication systems. Examples of such systems are those centered around non-blocking switching networks, like crossbar switches or Benes networks [BaB94,BBB87,BBD96,BCW81,BGW91,Bon89,,GBW83,Inu79], when operating in a Time Division Multiplexing (TDM) way, and WDM optical networks based on passive optical star. In these networks, the wide available bandwidth is divided into separate channels, each matching the speed of the electronic terminals, by means of wavelength division multiplexing. The selected function of such terminals is achieved by means of tunable transmitters and/or receivers. Obviously, a given wavelength cannot be used to simultaneously carry more than one transmission. Thus, we can have concurrent transmissions, provided that they do not involve the same transmitter or receiver more than once. When this constraint is not met, the transmissions with common transmitter or receiver are disrupted, and we say that a collision occurs. Collided transmissions are useless and must be discarded and repeated later. Obviously, this is the source of performance degradation, both from a system point of view (the network is used for transmitting messages that must be discarded) and from a users perspective (the messages undergo a longer delay before being successfully received), and so collisions should be avoided. Collisions can be avoided by proper protocols, like polling, or by scheduling of the messages. For a given set of messages, several different schedules exist, having dissimilar effects on the overall system performance.
As usual in TDM systems, we assume that communication takes place in a synchronous way, and is organized into frames . Each frame is divided into equal length time slots, representing the transmission of unitary blocks of information, also called packets. Packet scheduling in this setting is usually called time slot assignment (TSA for short), and has been extensively studied in the past considering particular side constraints, introduced in the basic problem to take into account specific system organizations, like intersatellite links, and special traffic features, like different priority messages or real time packets (e.g., see [BaB94,BBB87,BBD96,BCW81,BGW91,Bon89,,GBW83,Inu79,GH97,PhLi]). Other specific constraints must be taken into account when the system under investigation is a broadcast-and-select optical network. For instance, tuning time is not negligible in present-day optical equipment. Recently, scheduling of transmissions in broadcast-and-select optical networks has received considerable attention, both with negligible and not negligible tuning time assumption [PS94,RoS96,BM96,CCA96,,JMI95,GaG92,RoA95]. Finally, the same problem has recently been observed in information transfer between different memory levels (like main memory and disks) in multiprocessor systems [Jain97]. Generally, the objective is to minimize the schedule length.
An interesting case occurs when requests must be satisfied with no delay and must be scheduled as soon as they are raised. Here an "on-demand" approach is appropriate. Besides, as often happens in on-demand settings, requests may be rejected. This is not allowed in the traditional scheduling problems, and so a new class of problems, called "call control", is emerging.
One choice for such global knowledge can be a common time reference. In [FIS85] the authors prove that a common time reference can be one of the basic features of a distributed system able to agree on further global information, even in the presence of faults.
However, the enforcement of a common time reference has always been a difficult task, and the existing solutions (like the Internet NTP protocol [MIL91]) are rarely applied in practice. In fact, these protocols are quite fragile, since they are mainly based on deterministic hypothesis (while we are living in a non-deterministic world), and are far from being foolproof.
We identify some of the weaknesses of these approaches, and propose the abstract concepts that try to cope with them. Some real scale implementations have also been put forward, in order to test the applicability of the abstract concepts.
The researchers presenting this proposal have been working on its subjects since a long time, and have a considerable experience on them, both in scheduling [1-15], and in clock synchronization [16-18]. In particular, they investigated packet scheduling problems for several possible system configurations, like variable bandwidth or wireless multihop systems, for different packet features, like precedence constrained or hard-real-time packets, and recently on line scheduling. On the synchronization side, probabilistic and deterministic protocols have been proposed and implemented. A list of recent publications on these subjects follows.
 P. Barcaccia, Bonuccelli M.A. "A polynomial time optimal algorithm for time slot assignment in variable bandwidth systems" ACM/IEEE Transactions on Networking, vol. 2, n.3 (June 1994), pp. 247-251.
 Barcaccia, P., M.A. Bonuccelli, M. Di Ianni, "Minimum length scheduling of precedence constrained messages in distributed systems", EUROPAR 96 conference, Lyon (August 1996); published in LNCS n. 1124, pp 594-601.
 P. Barcaccia, M.A. Bonuccelli, M. Di Ianni: "Complexity of minimum length scheduling for precedence constrained messages in distributed systems", in revision, IEEE Transactions on Parallel and Distributed Systems
 Bonuccelli M.A., Leonardi, S., "On scheduling variable length broadcasts in packet radio networks" Telecommunications Systems , vol. 8 , n. 2-4.(December 1997), pp. 211-227;
 Bonuccelli M.A. "Traffic Scheduling in Telecommunication Systems and Network Flow", International Conference on Variational Inequalities and Network Equilinbrium Problems, Erice, Italy, June 1994 - in :Variational Inequalities and Network Equilinbrium Problems, Plenum Press, 1995, pp.9-19.
 Bonuccelli M.A., M.C. Cló "Scheduling of real-time messages in optical broadcast-and-select networks", in revision, IEEE/ACM Transactions on Networking
 M.A. Bonuccelli, M.C. Cló: "EDD Algorithm Performance Guarantee for Periodic Hard- Real-Time Scheduling in Distributed Systems", IEEE IPPS/SPDP 1999 Conference, San Juan, Puerto Rico, April 12 - 16, 1999.
 M.A. Bonuccelli, M.C. Cló: "The Performance Guarantee of Rate Monotonic for Periodic Hard-Real-Time Packet Scheduling of Distributed Systems", submitted to publication, May 1999.
 M.A. Bonuccelli, S. Pelagatti:"Optimal On Demand Packet Scheduling in Single-Hop Multichannel Communication Systems",MAPSP99, Renesse (Netherlands), June 14-17, 1999.
 R. Battiti, A.A. Bertossi, M.A. Bonuccelli: "Assigning codes in wireless networks: bounds and scaling properties", Wireless Networks, in press.
 M.G. Norman, S.Pelagatti, and P.Thanish:" On the complexity of scheduling with communication delay and contention". Parallel Processing Letters, 5(3):331-341, September 1995.
 S.Antonelli and S.Pelagatti: "On the complexity of the mapping problem for massively parallel architectures" International Journal of Foundations of Computer Science, 3(3):379-387, September 1992.
 P.Thanish, M.G.Norman, C.Boares, and S.Pelagatti:" Locality and Scheduling Models for Parallel Computation" In Proc. of IFIP WG 10.3, Working Conference on Programming Environments for Massively Parallel Distributed Systems, Ascona (Switzerland), April 1994. Birkhäuser, Basel, Switzerland.
 S.Antonelli and S.Pelagatti:"Using optimal partitioning strategies for skeleton allocation", To be presented at ParCo'99, Delft, August 1999.
 A. Ciuffoletti, ``Reliability versus cost: design of a probabilistic broadcast algorithm'', Distributed Computing, 1994, n.7, pp 115-127
 A. Ciuffoletti,``Using simple diffusion to synchronize the clocks in a distributed system'', Proc. 14th IEEE International Conference on Distributed Computing Systems, Poznan (Poland), June 1994, pp 484-491.
 G. Alari and A. Ciuffoletti,``Implementing a probabilistic clock synchronization algorithm'',n. 1, vol. 13, Real-Time Systems , July 1997, pp. 25-46
 A. Ciuffoletti,``Uniform Timing of a Multi-Cast Service'', Proc. of 19th IEEE International Conference on Distributed Computing Systems, Austin (Texas - USA), May 1999.
We shall study message and packet scheduling, as well as system synchronization. These two problems are very relevant for achieving high performances and easy of programming in distributed systems.
In particular, we shall propose new models for representing and studying these problems, investigate their computational complexity, propose optimal algorithms and fast sub-optimal heuristics, study the properties of such algorithms and heuristics, and implement them. Specifically:
The tools implemented during the past activity will be used to run real scale experiments.
On a longer horizon we shall study scheduling of interconnected single-hop systems. In this case, scheduling and routing must be solved at once, since they influence each other: an optimal routing can overload intermediate systems, thus leading to very long schedules. On the other hand, an optimal schedule needs a load balancing, which could be achieved at the expenses of unacceptably long paths. LEO's satellite constellations, like the IRIDIUM system, fall into this category of distributed systems. Another problem that will be studied in cooperation with the other sites is call control. This is a special kind of on demand scheduling, in which some requests can be refused. Such a refusal can be necessary in order to maintain a good quality of service for other ongoing communications, and is specially important in mobile ad-hoc systems.
The application of a robust and easy-to-use clock synchronization tool-set will be applied to the design of more complex services, like group membership management, that exhibit ``on demand'' features.
Maurizio A. Bonuccelli received the laurea degree in Computer Science from the University of Pisa in 1975. From 1976 until 1990 he has been associated with the Department of Computer Science, University of Pisa. From 1990 until 1994 he was Professor of Computer Science at the University of Rome "La Sapienza". In november 1994 he returned to the University of Pisa as Professor of Computer Science. During 1981 he took a sabbatical leave visiting IBM T.J. Watson Res. Center, Yorktown Heights, NY, working in the computer communications group. Later, he spent september 1993 at ICSI, Berkeley, CA, where he was associated to the TENET group. He has been involved in the program or steering committee of several international conferences and workshops. Recently, he organized the workshop on Nomadic Computing (satellite workshop of IPPS'97, Geneva, Switzerland), and the Workshop on Algorithmic Aspects of Communication (satellite workshop of ICALP'97, Bologna, Italy), and was program vice chair of IEEE/ACM Mobicom'97 Conference, Budapest, Hungary. He is chairman of the steering committee of the international workshop series Discrete Algorithms for Mobility, and memebr of the steerign committee of the international workshop series Wireless Mobile Multimedia. He is International Conference Coordinator of ACM SIGMOBILE, and is in the editorial board of the international journals Telecommunication Systems and ACM/Baltzer Mobile Networks and Applications (MONET). His research interests are on algorithmic and complexity aspects, as well as combinatorial problems, for design and management of sequential, parallel and distributed systems. Currently, he is involved in the investigation of resource allocation problems arising from computer networks, with a particular interest in packet scheduling for single-hop communication media.
R1) P. Barcaccia, M.A. Bonuccelli: "A polynomial time optimal algorithm for time slot assignment in variable bandwidth systems" ACM-IEEE Transactions on Networking , vol. 2, n.3 (June 1994), pp. 247-251 ;
R2) A.A. Bertossi, M.A. Bonuccelli: "Code assignment for hidden terminal interference avoidance in multihop packet radio networks", ACM-IEEE Transactions on Networking , vol. 3, n.4 (August 1995), pp. 441-449 ;
R3) M.A. Bonuccelli, S. Leonardi: "On scheduling variable length broadcasts in packet radio networks" Telecommunications Systems , vol. 8 , nos. 2-4.(December 1997), pp. 211-227;
R4) M.A. Bonuccelli, M.C. Cló: "EDD Algorithm Performance Guarantee for Periodic Hard-Real-Time Scheduling in Distributed Systems", IEEE IPPS/SPDP 1999 Conference , San Juan, Puerto Rico, April 12 - 16, 1999.
R5) R. Battiti, A.A. Bertossi, M.A. Bonuccelli: "Assigning codes in wireless networks: bounds and scaling properties", Wireless Networks, accepted for publication
Augusto Ciuffoletti was born on August 20th, 1956.
In 1980 he graduated in Computer Science with a Diploma di Laurea discussing a thesis on the specification of distributed fault-tolerant systems.
Since 1988 he has been ricercatore (Research Associate) at the University of Pisa, in the Dipartimento di Informatica.
His research contribution focuses on the control of distributed systems: starting from the early topic of the implementation of the fault tolerance in distributed systems, with a special interest paid to backward recovery patterns [C84], he later moved to the study of self-stabilizing algorithms, as a peculiar instance of a fault tolerant behavior. The application of these ideas brought to the design of algorithms based on information diffusion [C94a], and of some real scale experiments on distributed clock synchronization [C94b], [C96], [C99].
Besides the publications mentioned above, the results of his research activity are reported in 20 papers that appeared on international journals and conferences.
A more detailed curriculum and the complete list of publications is at URL
Susanna Pelagatti received the Ph.D in Computer Science from the University of Pisa in 1993. From March 1993 to March 1994 she has worked as post-doc at the Department of Computer Science (Univ. Edinburgh). Since 1994, she has been working at the Dipartimento di Informatica in Pisa first as a post-doc and then (since Feb 1995) as Assistent Professor. Her research interests are on parallel programming environments and scheduling in distributed and parallel systems. She authored a research monography on structured parallel programming and 25 papers appeared in international journals and conferences. Currently, she is involved in the development of methodologies and tools for structured parallel programming and in the investigation of scheduling problems arising in single and multi-hop comunication media.
R1) S. Pelagatti. Structured development of parallel programs. Taylor and Francis, London, Novembre 1997.
R2) B. Bacci, M. Danelutto, S. Pelagatti, and M. Vanneschi. SkIE: a heterogeneous environment for HPC applications. To appear on Parallel Computing.
R3) B. Bacci, M. Danelutto, S. Orlando, S. Pelagatti, and M. Vanneschi. Pl: A structured high level programming language and its structured support. Concurrency: Practice and Experience, 7(3):225-255, May 1995.
R4) S. Pelagatti. Compiling and supporting skeletons on MPP. In J. Darlington, editor, Proc. of the Third Working Conference on Massively Parallel Programming Models, pages 140-150, Los Alamitos, CA, 1998. IEEE Computer Society Press.
R5) M.A. Bonuccelli, S. Pelagatti:"Optimal On Demand Packet Scheduling in Single-Hop Multichannel Communication Systems",MAPSP99, Renesse (Netherlands), June 14-17, 1999.
Maria Claudia Cló received the Laurea degree in Mathematics from the University of Modena in 1991, and the PhD degree in Computer Science from the University of Pisa in 1998. Currently, she holds a Post-Doctoral fellowship at the Department of Computer Science of the University of Pisa. She worked on performance evaluation related queueing networks, before starting her current area of research, namely packet scheduling.
R1) S. Balsamo, M. C. Cló, L. Donatiello:"Cycle time distribution of cyclic networks with blocking" QUEUEING NETWORKS WITH FINITE CAPACITY, ed. R.O. Onvural and I.F. Akyildiz, Elsevier North Holland, 1993;
R2) M. C. Cló:"MVA Algorithm for Product-Form Cyclic Queueing Networks with RS Blocking" in the Proceedings of Third International Workshop on Queueing Networks with Finite Capacity, Ilkley, West Yorkshire, UK, 6-7 luglio 1995
R3) S. Balsamo, M. C. Cló:"Convolution Algorithm for Product-Form Queueing Networks with Blocking" in the Proceedings of Third International Workshop on Queueing Networks with Finite Capacity, Ilkley, West Yorkshire, UK, 6-7 luglio 1995;
R4) M. A. Bonuccelli, M. C. Cló:"EDD Algorithm Performance Guarantee for Periodic Hard-Real-Time Scheduling in Distributed Systems" 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing San Juan, Puerto Rico, 12-16 april 1999.
R5) M. A. Bonuccelli, M. C. Cló:"Scheduling of Real Time Messages in Optical Broadcast-and-Select Networks", in revision, IEEE/ACM Transactions on Networking
Denis Trystram, INPG Grenoble (France), Peter Thanish, Univ. Edinburgh (UK), A.A. Bertossi Univ. of Trento (Italy), R. Battiti, Univ. of Trento (Italy), M. Di Ianni, Univ. Perugia (Italy), I. Chlamtac, University of Texas at Dallas (USA), V. Syrotiuk, University of Texas at Dallas (USA), S. Basagni, University of Texas at Dallas (USA), J. Capone, Arizona State University (USA), A. Fereira, INRIA Sophia Antipolis (France)