Центральное различие между ними заключается в том, что сериализуемость является свойством global ; свойство всей истории операций / транзакций. Линеаризуемость является локальной собственностью ; свойство отдельной операции / транзакции. Другое отличие состоит в том, что линеаризуемость включает в себя понятие в реальном времени , чего нет в сериализуемости: точка линеаризации операции должна находиться между временем ее вызова и откликом. (См. Тим Харрис: Транзакционная память, 2ed . См. Слайды Херлихи из Искусство многопроцессорного программирования, раздел о линеаризации , которые доступны здесь , для некоторых примеры и доказательства.
Оба свойства нацелены на одну и ту же цель: последовательная согласованность. Из бумаги Херлихи:
Большая часть работы с базами данных и распределенными системами использует сериализуемость в качестве основного условия корректности для параллельных вычислений. В этой модели транзакция является потоком управления, который применяет конечную последовательность примитивных операций к набору объектов, совместно используемых с другими транзакциями. История является сериализуемой, если она эквивалентна истории, в которой транзакции выполняются последовательно, то есть без чередования. (Неполный) порядок приоритета может быть определен для неперекрывающихся пар транзакций очевидным образом. История строго сериализуема, если порядок транзакций в последовательной истории совместим с порядком их приоритета ...
... Линеаризуемость можно рассматривать как частный случай строгой сериализуемости, когда транзакции ограничены одной операцией, примененной к одному объекту. Тем не менее, это ограничение одной операции имеет далеко идущие практические и формальные последствия, давая линеаризуемым вычислениям отличную разновидность от их сериализуемых аналогов. Непосредственным практическим следствием является то, что механизмы управления параллелизмом, подходящие для сериализуемости, обычно не подходят для линеаризуемости, потому что они вносят ненужные издержки и накладывают ненужные ограничения на параллелизм.
Ссылки:
Харрис, Тим, Джеймс Ларус и Рави Раджвар: Транзакционная память, 2ed . Обобщающие лекции по компьютерной архитектуре. Morgn & Claypool, 2010. ISBN 9781608452354. URL: http://www.morganclaypool.com/doi/abs/10.2200/S00272ED1V01Y201006CAC011?journalCode=cac
Херлихи, Морис и Жанетт Винг: Линеаризуемость: условие корректности для параллельных объектов . ACM Trans. Prog. Lang. и сис. Том 12, № 3, июль 1990 г., стр. 463-492. URL
http://www.cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf
Пападимитриу, Христос: Сериализуемость одновременных обновлений базы данных . Журнал ACM Vol 26. № 4. Октябрь 1979, с. 631-653. URL http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-210.pdf
Херлихи, Морис и Нир Шавит: Искусство многопроцессорного программирования . Elsevier, 2008. ISBN 978-0-12-370591-4. URL: http://www.elsevier.com/wps/find/bookdescription.cws_home/714091/description#description Слайды PPT по линеаризуемости находятся здесь: http://pub.ist.ac.at/courses/ppc10/slides/Linearizability.pptx
Аттия, Хагит и Дженнифер Уэлч: Последовательная согласованность и линеаризуемость . ACM Транзакции на компьютерных системах Vol. 12, No. 2, May 1994, Pages 91-122. URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.133.4969&rep=rep1&type=pdf
Подробнее:
Если вы действительно заботитесь об этом, прочитайте статью с введенными определениями. Для линеаризуемости это Линеаризуемость: условие корректности для параллельных объектов , Herlihy и Wing . Это плотно, но стоит внимания. Обратите внимание, что в сообществе программной транзакционной памяти остается открытым вопрос, является ли линеаризуемость правильной целью / свойством, к которому нужно стремиться.
Сериализуемость - это результат набора операций / "система", которая может быть выражена в виде определенного порядка ("как если бы выполнение было выполнено в определенном порядке ...") всех операций.Линеаризуемость - это свойство одного подмножества операций в системе ... операция / набор операций являются линеаризуемыми, если они кажутся другим операциям, как если бы они произошли в определенный момент (логического) времени по отношению к другим.Каноническая статья здесь Papadimitriou, Сериализуемость одновременных обновлений базы данных .
Подумайте об «атомарной операции», когда вы думаете о «линеаризуемости».Операции (набора) линеаризуются, когда они (кажется) происходят атомарно по отношению к другим частям системы.Распространенная формулировка «создайте иллюзию, что каждая операция вступает в силу мгновенно между ее вызовом и ответом».Формулировка линеаризуемость обусловлена Herlihy , которая подчеркивает, что это локальное свойство, по сравнению с другими видами последовательных свойств согласованности, такими как «сериализуемость», которые являются глобальными.