Kapasite kısıtlı çizge teorisi problemleri içindağıtık ve öz-kararlı algoritmalar

Bir dağıtık sistemi oluşturan birimlerden birinde ya da bu birimlerin birbirleriyle iletişim kurdukları bağlantıda bir hatanın meydana gelmesi, sistemin çalışmasında istenmeyen etkiler oluşturabilir. Dağıtık algoritmaların doğası gereği işlem birimlerinin sınırlı (yerel) bilgiye sahip olmaları ve hesaplama kuvveti yönünden birbirlerinden bağımsız olmaları, söz konusu hataların tespit edilip çözülmesini zorlaştırır. Hatayı sistemin kullanıcısının gözlemlemesini önleyecek şekilde örtmeyi hedefleyen hata-toleranslı mekanizmalar hesaplama kaynakları yönünden oldukça masraflıdır. Öte yandan, birimlerin istenmeyen davranışının belirli bir süre için kabul edilebildiği sistemlerde, sistemin öngörülebilir bir süre içinde hatasız ve istenen bir konfigürasyona ulaşması garanti ediliyorsa, hatayı gizleme koşulu esnetilebilir. Öz-kararlılık, önemli bir maskelemesiz hata toleransı kavramıdır. Bir özkararlı algoritma, sistemin istenmeyen bir konfigürasyonda bulunması halinde etkinleştirilip çalıştırılan ve nihayetinde sistemi hiçbir kuralın aktif olmadığı öz-kararlı olarak adlandırılan bir konfigürasyona ulaştıran bir dizi kuraldan oluşur. Bu tez, bazı kapasite kısıtlı çizge teorisi problemleri için geliştirilmiş olan öz-kararlı algoritmalardan oluşur. Klasik çizge teorisi problemlerinin gerçek dünya uygulamaları genelde kapasite kısıtı içermesine rağmen bu problemlerin kapasite kısıtlı versiyonları öz-kararlılık literatüründe hak ettiği kadar dikkat çekmemiştir. Biz bu çalış- mada problemlerin kapasite kısıtlı versiyonlarına odaklanıyoruz. Özellikle kapasite kısıtlı eşleme (b-eşleme), kapasite kısıtlı en küçük kapsayan ağaç ve kapasite kısıtlı çizge bölme problemleriyle ilgilenip bu problemler için özgün öz-kararlı algoritmalar öneriyoruz. Ayrıca bu algoritmaların doğruluk, kapalılık ve yakınsama özelliklerini ispatlıyoruz.