Коммуникационная сложность (протокола) (communication complexity)- функция, выражающая зависимость максимального количества битов информации, пересылаемых в процессе выполнения распределенного алгоритма от длины записи исходных данных. К. с. - показатель эффективности реализации криптографических протоколов.
