Dağıtık sistemlerde nedensel sıralı mesaj dağıtım algoritmaları ve yeni bir yaklaşım

Abstract

Dağıtık sistemler fiziksel olarak birbirinden ayrı işlem birimlerinin belli bir iletişim ağı kullanarak bir arada çalışmasına olanak sağlayan yapılardır. Bu yapılar genel olarak ortak bir hafıza alanı kullanmazlar ve birbirleri ile mesaj aktarımı (?message passing?) yöntemi ile haberleşirler [1]. Bu sistemlerde mesaj iletiminde oluşan gecikmeler sonlu olsa da tahmin edilebilir değildir ve iletilen mesajların sırasının bozulmasına neden olabilir. Bu durumda olaylar arasındaki neden-sonuç sıraları da bozulabilir ve sistemde mantıksal hatalar oluşmaya başlayabilir.Dağıtık sistemlerde bu problemi çözmek için, ortak bir sistem saati ile tüm sistem birimlerinin eş zamanlı kılınması ve mesajların neden-sonuç ilişkileri gözetilerek sıralanmaya çalışılması gibi çeşitli yaklaşımlar önerilmiştir. Nedensel sıralı mesajlaşma (NSM) algoritmaları, ortak bir sistem saatine bağlı kalmadan mesajları neden-sonuç ilişkisine göre düzenlemeyi esas alır. Yapılan deneyler bu tür algoritmaların ortak sistem saatlerinin kullanıldığı çözümlere göre daha iyi performans sağladığını göstermiştir [2]. Ancak NSM algoritmalarının mesajlar üzerinde taşıdıkları kontrol bilgileri bazı durumlarda oldukça büyüyebilmekte ve ağ üzerinde gereksiz veri yüküne neden olabilmektedir. Bu tez çalışması bünyesinde geliştirilen Merkezi Kontrol Dağıtık Mesajlaşma (MKDM) yaklaşımı ile mesajların birimler arasında doğrudan akmasına izin verilmekle birlikte, mesaj yönetimini sağlamakla görevli yönetici bir birime de mesajı tanımlayan basit bir kontrol bilgisi gönderilerek mesajların sıralanmasını sağlanmaktadır.Tez kapsamında kullandıkları kontrol bilgisi boyutu bakımından en uygun (?optimal?) NSM algoritmaları olan Modified-Schiper-Eggli-Sandoz (MSES) ve Kshemkalyani-Singhal (KS) algoritmaları ile MKDM algoritmasının teorik ve deneysel analizleri yapılmış, MKDM algoritmasının farklı simülasyon modelleri için diğer algoritmalara göre daha ölçeklenebilir ve daha yüksek performans sağlayan algoritma olduğu gözlenmiştir.

Distributed systems are composed of distinct processes that do not have a global time or a shared memory. A typical system realizes interoperability of processes by transferring messages (messages passing) via a communication network [1]. In a large communication network, latency in message transmission is unpredictable and the order of messages may change. So cause and effect relation between messages may not be preserved and logical errors may happen in the system. Therefore special algorithms are required to preserve the harmony of ?time synchronization? and ?data synchronization? in distributed systems to ensure that the right message is received at the right time.Message ordering techniques based on global time allows processes to run on the same time clock and puts time info called ?time-stamp? in each message to order messages. On the other hand, causal order message delivery algorithms do not use global time but use control information both in messages and in processes. This control information is used by the processes to evaluate the causal dependencies of messages. In experiments, optimal casual order algorithms give better performance results than time-stamp techniques [2]. On the other hand, under some situations, causality based methods may require large control information to be appended to the message which can cause latency in network. In this study, a new approach called Central Control Distributed Messaging (CCDM) is proposed. In CCDM, there is a central process to manage message ordering. Simulators send their messages directly to the destinations and also send control information about messages to the central process.In this study two optimal causal order algorithms called Modified-Schiper-Eggli-Sandoz(MSES), Kshemkalyani-Singhal(KS) and our method CCDM are theoretically and experimentally analyzed in a simulation environment which can simulates a distributed system.